Указания исполнителю. Организация карт в представлении позиции, а также способ хранения старых позиций решающим образом определяют уровень эффективности программы. Если позиция является текущей или находится в стеке, то для нее должно быть известно состояние всех стопок и соответствующих им столбиков, а также счетных стопок. Позиция в стеке должна содержать, кроме того, список еще не проверенных ходов. Для ускорения поиска возможных ходов нужно иметь вектор состояния для всех карт, в котором должны быть такие признаки карты: лежит ли она рубашкой вверх, находится ли уже в счете, лежит ли рубашкой вниз внутри столбика (какого именно?), лежит ли рубашкой вниз в низу столбика (какого именно?). Быть может, вы сумеете придумать другую структуру данных, обеспечивающую быстрое нахождение возможных ходов. В любом случае при запоминании старой позиции часть информации, как уже использованную, можно отбросить, экономя таким образом память.
Здесь потребуется два специальных алгоритма. Во-первых, как реализовать тасование карт в ЭВМ? Вот процедура, предложенная Кнутом. Пусть rand52 — функция, генерирующая случайные целые числа, равномерно распределенные в отрезке от 1 до 52. Поместите все карты в массив карта длины 52; как в нем расположены карты вначале — не имеет значения. После этого для i от 1 до 52 поменяйте местами элементы карта[i] и карта[rand52], каждый раз заново обращаясь к функции rand52. Одного такого тасования будет достаточно.
Во-вторых, как находить старые позиции? Это классическая задача поиска в растущей базе данных. Очевидным решением тут представляется хеш-таблица, где ключом поиска служит вся позиция. Поскольку полное сравнение двух позиций на равенство, скорее всего, обойдется слишком дорого, то разумно, по-видимому, будет применить виртуальный хеш-код. Пространство, отведенное для хранения старых позиций, может переполняться, поэтому вы должны уметь время от времени освобождать его. Наилучший способ освобождения памяти состоит, пожалуй, в том, чтобы иметь при каждой позиции счетчик, показывающий, сколько раз к ней обращались, и отбрасывать каждый раз те позиции, которые участвовали реже всего. Другой способ, который можно использовать и в сочетании с первым, — хранить список всех старых позиций и всякий раз, когда ищется какая-либо позиция, перемещать ее в голову списка. Когда придет время отбросить часть позиций, то кандидатами на уничтожение будут позиции в хвосте списка, поскольку к ним дольше всего не было обращений. Принятый вами способ отбрасывания старых позиций окажет влияние на выбор стратегии поиска, и наоборот. Заметим, что, хотя алгоритм отбрасывания старых позиций и не влияет на правильность программы анализа пасьянсов, тем не менее он может существенно ее замедлить.
Инструментовка. Эта задача требует средств для удобной работы со структурами данных умеренной сложности. В интересах эффективности выделение и освобождение памяти не следует доверять системе, так что Снобол, видимо, не подойдет. Претендентами могут быть языки Алгол W, Паскаль, PL/I, Лисп и даже Кобол. Вы сможете оценить достоинства структур данных, определяемых программистом, если попытаетесь решить эту задачу сначала на одном из упомянутых выше языков, а потом еще раз на языке типа Фортран или XPL, в которых сложные структуры данных приходится представлять при помощи параллельных массивов.
Длительность исполнения. Одному исполнителю на 3 недели.
Развитие темы. Наиболее очевидное расширение задачи — применить этот метод анализа к другим пасьянсам. Осуществление этой идеи не связано с какими-либо трудностями, если только во время игры не происходит тасования карт. На свете существуют сотни пасьянсов, и ни один из них, насколько нам известно, не подвергался мало-мальски серьезному анализу. На этой задаче можно также изучать зависимости общего числа исследуемых позиций от объема памяти и критерия отбрасывания старых позиций. Иначе говоря, чем исследовать пасьянс при помощи методов поиска, используем задачу о пасьянсе для изучения методов поиска.
Гибсон (Gibson W. В.). How to Play Winning Solitaire. Frederick Fell, New York, NY, 1964.
Это единственная из известных автору книг о данном пасьянсе.
Кнут (Knuth D. E.). The Art of Computer Programming, Volume 3/Sorting and Searching. Addison-Wesley, Reading, MA, 1973. [Имеется перевод: Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск.— М.: Мир, 1978.] Снова ссылка на книгу Кнута. На этот раз в гл. 6 вы сможете прочитать все о методах поиска, в частности о поиске по хеш-таблице. Разумеется, если вы внимательно изучите всю главу, то, возможно, обнаружите и лучший метод поиска.