У Peg Solitaire не одно решение. Так сколько всего существует последовательностей ходов, которые оставляют один шарик? Будем считать, начиная с маленьких досок.
Как считаем
В этой статье за одно решение считается одна последовательность ходов, оставляющая один шарик.
- Те же ходы, сделанные в другом порядке, считаются отдельным решением.
- Решения, которые отличаются только зеркальным отражением слева направо, тоже считаются отдельно.
Число подсчитал компьютер, перебрав все ходы. Одни и те же позиции встречаются много раз, поэтому если запоминать результат для уже посчитанной позиции, считать можно быстрее.
Треугольная доска в 15 лунок: 29760
На треугольной доске в 15 лунок, где игра начинается с пустой самой верхней лунки, последовательностей ходов, оставляющих один шарик, 29760.
Если менять лунку, которую оставляют пустой в начале, число решений тоже меняется. Если пуста середина стороны, их больше всего — 85258, а если пуста внутренняя лунка, то меньше — 1550 (подробнее — в статье о решении треугольной доски).
Английская доска в 33 лунки: считается, что больше 4 × 10 в 16-й степени
Решений, которыми на английской доске в 33 лунки, начав с центра, оставляют один шарик в центре, по расчётам больше 4 × 10 в 16-й степени. Это число на много порядков больше, чем на треугольной доске.
Почему их так много? Я посчитал, сколько разных позиций бывает после каждого хода.
| Ход | Последовательности ходов | Позиции | Сводя повороты |
|---|---|---|---|
| 1 | 4 | 4 | 1 |
| 2 | 12 | 12 | 2 |
| 3 | 60 | 60 | 8 |
| 4 | 400 | 296 | 39 |
| 5 | 2960 | 1338 | 171 |
| 6 | 24600 | 5648 | 719 |
| 7 | 221072 | 21842 | 2757 |
«Последовательности ходов» — число способов сыграть до этого хода, «позиции» — число получившихся форм доски, «сводя повороты» — число позиций, если те, что при повороте или отражении становятся одинаковыми, считать за одну.
- Для первого хода четыре варианта, но все они при повороте совпадают (статья о первом ходе).
- С каждым ходом число позиций растёт примерно в 4–5 раз.
- Начиная с четвёртого хода в одну и ту же позицию можно прийти разными путями. К седьмому ходу число последовательностей ходов больше числа позиций более чем в 10 раз.
Число решений для маленьких задач
Я посчитал и для трёх досок «Тренировки с главным шариком» со страницы, где можно играть. Везде считается число решений, которые оставляют красный главный шарик последним.
| Доска | Решений |
|---|---|
| 8 шариков | 19 |
| 12 шариков | 679 |
| 16 шариков | 3336232 |
Чем больше шариков, тем сильнее растёт число решений. Значит ли это, что доски с большим числом шариков проще?
Не обязательно. Если на той же доске посчитать, сколько из возможных первых ходов оставляют продолжение к решению, получится так.
| Доска | Первые ходы | Ходы, ведущие к решению |
|---|---|---|
| 8 шариков | 6 | 4 |
| 12 шариков | 6 | 3 |
| 16 шариков | 9 | 6 |
На любой доске есть ходы-ловушки: сделав такой ход, главный шарик уже не оставить. Даже если решений много, но по пути много ловушек, играть на такой доске трудно.
Сложность в приложении определяют «ходы-ловушки»
В режиме «Задачи» приложения «Peg Solitaire» сложность тоже определяется этой идеей. Приложение смотрит, какая доля ходов в ходе решения не позволяет достичь цели (доля ходов-ловушек), и пересоздаёт доску, пока доля не попадёт в диапазон сложности от ★1 до ★5. Число шариков и размер доски тоже заданы для каждой сложности.
Число шариков для каждой сложности указано в статье «Как играть».
