Большинство задач поиска в пространстве состояний, проанализированных в этой главе, имеют длинную историю, отраженную в литературе, и являются менее тривиальными, чем может показаться на первый взгляд. Задача с миссионерами и каннибалами, используемая в упр. 3.9, была подробно проанализирована Амарелем [24]. До него эту задачу ввели в проблематику искусственного интеллекта Саймон и Ньюэлл [1420], и в проблематику исследования операций — Беллман и Дрейфус [96]. Работы наподобие проведенных Ньюэллом и Саймоном над программами Logic Theorist [1127] и GPS [1129] привели к тому, что алгоритмы поиска считались основным оружием в арсенале исследователей искусственного интеллекта 1960-х годов, а сами процессы решения задач стали рассматриваться в качестве канонической проблемы искусственного интеллекта. К сожалению, в то время в области автоматизации этапа формулировки задачи было предпринято слишком мало усилий. Более современная трактовка подхода к представлению и абстрагированию задач, включая применение программ искусственного интеллекта, которые (отчасти) сами выполняют эти функции, изложена в книге Кноблока [807].

Задача игры в восемь — это "младшая сестра" задачи игры в пятнадцать, которая была изобретена знаменитым американским разработчиком игр Сэмом Ллойдом [955] в 1870-х годах. Игра в пятнадцать быстро приобрела в Соединенных Штатах огромную популярность, которую можно сравнить лишь с более современной сенсацией, вызванной изобретением кубика Рубика. Она также быстро привлекла внимание математиков [739], [1486]. Редакторы American Journal of Mathematics заявили: "Игра в пятнадцать в последние несколько недель занимает все внимание американской публики, и можно с уверенностью сказать, что ею интересуются девять из десяти людей всех полов и возрастов и всех общественных положений. Но не это побудило нас, редакторов, включить статьи, посвященные этой теме, в наш журнал American Journal of Mathematics, а тот факт, что..." (далее следует краткое описание аспектов игры в пятнадцать, представляющих интерес с точки зрения математики). Исчерпывающий анализ игры в восемь был проведен с помощью компьютера Шо-филдом [1363]. Ратнер и Уормут [1268] показали, что общая версия игры (не в пятнадцать, а в лхл-1) принадлежит к классу NP-полных задач.

Задача с восемью ферзями была впервые опубликована анонимно в немецком шахматном журнале Schach в 1848 году; позднее ее создание приписали некоему Максу Беззелю. Она была повторно опубликована в 1850 году и на этот раз привлекала внимание выдающегося математика Карла Фридриха Гаусса, который попытался перечислить все возможные решения, но нашел только 72. Наук (Nauck) опубликовал все 92 решения позднее, в том же 1850 году. Нетто [1121] обобщил эту задачу до п ферзей, а Абрамсон и Янг [2] нашли алгоритм с оценкой О(п).