Решение Peg Solitaire можно найти на компьютере. «Подсказка» в приложении «Peg Solitaire» и проверка решений для этого сайта используют программы с одной и той же идеей. Здесь просто рассказано, как это устроено.

Пробуем все ходы по очереди

Самый прямой способ — выбрать один из возможных ходов, сделать его, снова выбрать один из возможных ходов и сделать, и так далее. Если зашли в тупик, вернуться на один ход и выбрать другой, ещё не опробованный ход.

  1. Выбрать один из возможных ходов на текущей доске и сделать его.
  2. Если остался один шарик, решение найдено.
  3. Если возможных ходов не осталось, вернуться на один ход и попробовать другой.
  4. Если все ходы опробованы, вернуться ещё на один ход.

Такой способ называется поиском в глубину. Это то же самое, что делает человек, пробуя ходы и нажимая «Отменить», только повторяемое с огромной скоростью.

Не проверять одну и ту же позицию много раз

В Peg Solitaire одна и та же позиция часто получается и при другом порядке ходов. На английской доске в 33 лунки способов сыграть до седьмого хода больше 220 тысяч, а получающихся позиций около 22 тысяч (сколько существует решений).

Поэтому позиции, про которые уже выяснилось, что они тупиковые, запоминают, и если встречают их снова, сразу возвращаются. Только это сильно сокращает объём проверки.

Программа, которой мы пользовались для этого сайта, нашла решение на английской доске в 33 лунки, где игра начинается с центра и шарик остаётся в центре, мгновенно (меньше 0,1 секунды). Но так бывает не всегда. Когда мы искали так же, изменив второй ход, это заняло около 9 секунд. Время сильно зависит от того, с какого хода начать пробовать.

Отсекаем ветви, не просматривая вперёд

Ещё один приём — если стало ясно, что из этой позиции цель недостижима при любой игре, дальше не проверять. Это называется отсечением ветвей.

В приложении ветви отсекаются двумя способами.

  • Трёхцветная раскраска: если раскрасить доску по диагонали в три цвета, с каждым ходом чётность числа шариков всех трёх цветов меняется на противоположную. Поэтому лунки, в которых из текущей позиции можно оставить последний шарик, определяются одним расчётом (статья о трёхцветной раскраске).
  • Строка и столбец главного шарика: главный шарик ходит сразу на две лунки, поэтому чётность строки и столбца его лунки не меняется (как оставить главный шарик последним).

Если на доске не осталось ни одной лунки, удовлетворяющей обоим условиям, главный шарик последним не оставить. Такая позиция определяется как нерешаемая без просмотра ходов вперёд.

В «Подсказке» приложения

«Подсказка» приложения ищет следующий ход, который из текущей позиции ведёт к цели, и подсвечивает его золотыми кольцами.

  • Решение задачи запоминается заранее: доски «Задач» строятся прыжками в обратную сторону, поэтому решение, по которому доска создавалась, известно (как создаются задачи, которые всегда решаются). Позиции на пути этого решения запоминаются как «решаемые», так что ответ даётся сразу. Если вы свернули с пути, но в ходе поиска выходите на путь решения, поиск можно остановить.
  • Объём проверки ограничен: за одну подсказку проверяется не больше 1,5 миллиона позиций или 3 секунд. На большой доске за это время ответ может и не найтись.
  • Сообщение, на сколько ходов вернуться: если из текущей позиции цель уже недостижима или за предел ответ не найден, приложение проверяет позиции, до которых можно вернуться кнопкой «Отменить», и сообщает, на сколько ходов вернуться, например «Вернитесь на 3, чтобы получилось». Позиции для возврата проверяются, каждый раз сужая круг вдвое, поэтому даже при большом числе ходов ответ находится быстро.

Подсказки для тех, кто решает сам

Приёмы компьютера годятся и для человека.

  • Запоминайте тупиковые формы: форма, на которой вы один раз потерпели неудачу, окажется неудачной, даже если прийти к ней в другом порядке.
  • Думайте от цели: лунки, в которых можно оставить последний шарик, известны с самого начала. Если заранее решить, к какой лунке стремиться, ходы выбирать проще (как оставить шарик в центре).
  • Возвращайтесь и пробуйте: как в поиске в глубину, если сомневаетесь, вернуться немного назад и попробовать другой ход — правильный способ.