В обычном пасьянсе карты просто тасуют и раздают, поэтому среди раскладов попадаются такие, что не решаются никак (Какой процент раскладов пасьянса выигрывается). В приложении Пасьянс «Клондайк» расклады для «Новой игры» заранее решает компьютер, и используются только те, что удалось решить до конца. Здесь мы просто расскажем, как это устроено.

1. Тасуем и раздаём

Сначала 52 карты хорошо тасуют и раздают так же, как в обычном пасьянсе. Пока это обычный расклад, и неизвестно, решается ли он.

2. Пробуем ходы по очереди

Затем компьютер пытается решить расклад. Это похоже на путь на ощупь по лабиринту.

  1. Записать все ходы, которые можно сделать в текущей позиции.
  2. Выбрать один из них, самый перспективный, и сделать его.
  3. В новой позиции снова повторить пункты 1 и 2.
  4. Когда ходов не остаётся, вернуться в предыдущую позицию и выбрать другой ход, который ещё не пробовали.
  5. Когда все 52 карты лежат на базовых стопках, последовательность ходов и есть «решение».

Компьютер решает, зная, какие карты закрыты. Человек играет иначе, но чтобы проверить, что «у расклада есть решение», этого достаточно.

Сначала пробуем перспективные ходы

Порядок, в котором пробуют ходы, строится по тем же соображениям, что и у людей. Например, сначала пробуют ходы, которые открывают закрытую карту, и ходы, которые отправляют на базовые стопки карты с маленькими числами. Так решение чаще находится быстрее. Но отложенные ходы не выбрасывают, при необходимости их тоже пробуют.

Одну позицию не проверяют дважды

Колоду можно проходить много раз, поэтому в одну и ту же позицию можно вернуться не раз. Поэтому приложение запоминает уже проверенные позиции и не идёт дальше, если снова в такую попадает.

3. Задаём пределы

У некоторых раскладов позиций для проверки очень много. Поэтому в приложении для одного расклада заданы пределы: 0,5 секунды, 50 тысяч позиций и 512 ходов.

Результатов три.

РезультатИспользовать?
Решение найденоДа
Всё перепробовали, решения нетНет
Достигнут пределНет

Расклад, где «достигнут предел», может на самом деле решаться, но мы не смогли это проверить, поэтому не используем. Важно различать «не решается» и «не удалось проверить до конца».

Когда на iPhone испытали набор из 100 определённых раскладов, при пределе 0,5 секунды решение нашлось у 41. Если увеличить предел до 2 секунд, получалось те же 41, и число не менялось.

4. Воспроизводим решение с начала и проверяем

Найденное решение ещё раз воспроизводят ход за ходом, начиная с раздачи, и проверяют.

  • Все ли 52 карты на месте и нет ли одинаковых карт.
  • Можно ли каждый ход сделать по правилам.
  • Лежат ли в конце все 52 карты на базовых стопках.

Только то, что прошло все проверки, используют как «расклад, который можно решить». В приложении с самого начала есть 100 таких проверенных раскладов. Новые расклады тоже понемногу создаются и копятся, пока приложение открыто, чтобы не мешать игре. Для этого связь не нужна.

Что гарантируется

Приложение гарантирует, что «из позиции сразу после раздачи решение есть». В зависимости от ходов, выбранных по дороге, можно и зайти в тупик. Тогда можно вернуться кнопкой «Отмена» к развилке или начать заново кнопкой «Заново», и путь к победе всегда найдётся (Что делать, если пасьянс зашёл в тупик).

Решения, которые нашёл компьютер, включают обходные ходы и не самые короткие. О числе ходов в решениях рассказано в статье За сколько ходов можно выиграть.