В режиме «Задачи» приложения «Peg Solitaire» при каждой «Новой игре» создаётся доска другой формы. И всё же любую такую доску всегда можно решить. В этой статье рассказано, как это устроено.

Если делать обычным способом, неизвестно, решается ли доска

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

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

Прыжок в обратную сторону

Один ход в Peg Solitaire — это «шарик перепрыгивает через соседний шарик в пустую лунку и снимает тот, через который перепрыгнул». Если сделать его в обратную сторону, получится

шарик возвращается в пустую лунку через одну, а в пустую лунку между ними кладут один шарик

Каждый ход в обратную сторону добавляет один шарик.

Начинаем с одного главного шарика

Ходы в обратную сторону накладывают друг на друга, начиная с доски, где остался только главный шарик (то есть с пройденной доски). Посмотрим на маленьком примере.

Сначала доска, на которой есть только главный шарик.

Первый раз: главный шарик возвращается на две лунки вверх, а между ними кладут шарик.

Второй раз: положенный между ними шарик возвращается на две лунки влево, а между ними кладут шарик.

Третий раз: главный шарик возвращается на две лунки вправо, а между ними кладут шарик.

Так получилась задача на четыре шарика.

Ходы, пройденные в обратную сторону, и есть ответ

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

  1. Ход 1 e1→c1
  2. Ход 2 a2→c2
  3. Ход 3 c1→c3
  4. После хода 3 Осталось: 1

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

Что приложение добавляет

К этому способу приложение добавляет несколько приёмов.

  • Повторное использование лунок: при выборе хода в обратную сторону приложение охотнее выбирает ходы, снова использующие уже задействованные лунки. Ходы получаются переплетёнными, и задача реже оказывается просто цепочкой по прямой.
  • Подгонка формы доски: у половины готовых досок добавляют лунки, чтобы форма стала симметричной слева направо. У остальных добавляют на краю доски одну-две пустые лунки, чтобы изменить форму. Исходное решение при этом можно сделать как есть, поэтому решаемость не меняется.
  • Одна и та же задача из одного зерна: задачу создают из числа, которое называется «зерно», поэтому из одного зерна и одной сложности получается одинаковая задача и на iPhone, и на Android.

Проверяем сложность и пересоздаём, если не подходит

У построенной в обратную сторону задачи ответ есть всегда. Но только поэтому она может оказаться слишком лёгкой или слишком трудной.

Поэтому приложение смотрит на созданную задачу: сколько в ходе решения ходов, после которых главный шарик уже не оставить (ходов-ловушек). Задачу пересоздают до 24 раз, пока доля ходов-ловушек не попадёт в диапазон от ★1 до ★5 (диапазоны — в статье о сложности).

Даже для задач ★5 «Гроссмейстер» (27–32 шарика) создание занимает в среднем около 0,6 секунды на Mac, который используется для разработки. Кроме того, для каждой сложности заранее создано по три задачи, а использованные дозаказываются в фоне, так что игроку почти не приходится ждать.

Решение не обязательно одно

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

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