В режиме «Задачи» приложения «Peg Solitaire» при каждой «Новой игре» создаётся доска другой формы. И всё же любую такую доску всегда можно решить. В этой статье рассказано, как это устроено.
Если делать обычным способом, неизвестно, решается ли доска
Если форму лунок и расстановку шариков выбирать наугад, получится много досок, которые не решаются. Чтобы проверить, решается ли доска, нужно перебрать все ходы, а когда шариков много, это занимает время.
Поэтому приложение использует способ, при котором задачу строят от ответа в обратную сторону.
Прыжок в обратную сторону
Один ход в Peg Solitaire — это «шарик перепрыгивает через соседний шарик в пустую лунку и снимает тот, через который перепрыгнул». Если сделать его в обратную сторону, получится
шарик возвращается в пустую лунку через одну, а в пустую лунку между ними кладут один шарик
Каждый ход в обратную сторону добавляет один шарик.
Начинаем с одного главного шарика
Ходы в обратную сторону накладывают друг на друга, начиная с доски, где остался только главный шарик (то есть с пройденной доски). Посмотрим на маленьком примере.
Сначала доска, на которой есть только главный шарик.
Первый раз: главный шарик возвращается на две лунки вверх, а между ними кладут шарик.
Второй раз: положенный между ними шарик возвращается на две лунки влево, а между ними кладут шарик.
Третий раз: главный шарик возвращается на две лунки вправо, а между ними кладут шарик.
Так получилась задача на четыре шарика.
Ходы, пройденные в обратную сторону, и есть ответ
Если сделать построенные ходы с конца, в обычном направлении, получится готовый ответ. В примере выше, если оставить в качестве лунок доски только использованные лунки и сделать из этого задачу, она решается так.
- Ход 1 e1→c1
- Ход 2 a2→c2
- Ход 3 c1→c3
- После хода 3 Осталось: 1
Последовательность, построенная в обратную сторону, начата с пройденной доски, поэтому если пройти её в обычном направлении, останется только главный шарик. Поэтому у каждой задачи гарантированно есть хотя бы одно решение.
Что приложение добавляет
К этому способу приложение добавляет несколько приёмов.
- Повторное использование лунок: при выборе хода в обратную сторону приложение охотнее выбирает ходы, снова использующие уже задействованные лунки. Ходы получаются переплетёнными, и задача реже оказывается просто цепочкой по прямой.
- Подгонка формы доски: у половины готовых досок добавляют лунки, чтобы форма стала симметричной слева направо. У остальных добавляют на краю доски одну-две пустые лунки, чтобы изменить форму. Исходное решение при этом можно сделать как есть, поэтому решаемость не меняется.
- Одна и та же задача из одного зерна: задачу создают из числа, которое называется «зерно», поэтому из одного зерна и одной сложности получается одинаковая задача и на iPhone, и на Android.
Проверяем сложность и пересоздаём, если не подходит
У построенной в обратную сторону задачи ответ есть всегда. Но только поэтому она может оказаться слишком лёгкой или слишком трудной.
Поэтому приложение смотрит на созданную задачу: сколько в ходе решения ходов, после которых главный шарик уже не оставить (ходов-ловушек). Задачу пересоздают до 24 раз, пока доля ходов-ловушек не попадёт в диапазон от ★1 до ★5 (диапазоны — в статье о сложности).
Даже для задач ★5 «Гроссмейстер» (27–32 шарика) создание занимает в среднем около 0,6 секунды на Mac, который используется для разработки. Кроме того, для каждой сложности заранее создано по три задачи, а использованные дозаказываются в фоне, так что игроку почти не приходится ждать.
Решение не обязательно одно
Последовательность, построенная в обратную сторону, — это одно из решений. У той же доски часто есть и другие. Доски «Тренировки с главным шариком» со страницы, где можно играть тоже созданы по этой идее, и у доски на 16 шариков больше трёх миллионов способов решения (сколько существует решений).
«Подсказка» в приложении помнит решение, по которому задача создавалась, поэтому, пока вы идёте по его пути, она сразу называет следующий ход. Если вы свернули с пути, другой путь ищет программа, которая подбирает решения (решение на компьютере).
