У Peg Solitaire не одно решение. Так сколько всего существует последовательностей ходов, которые оставляют один шарик? Будем считать, начиная с маленьких досок.

Как считаем

В этой статье за одно решение считается одна последовательность ходов, оставляющая один шарик.

  • Те же ходы, сделанные в другом порядке, считаются отдельным решением.
  • Решения, которые отличаются только зеркальным отражением слева направо, тоже считаются отдельно.

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

Треугольная доска в 15 лунок: 29760

На треугольной доске в 15 лунок, где игра начинается с пустой самой верхней лунки, последовательностей ходов, оставляющих один шарик, 29760.

Если менять лунку, которую оставляют пустой в начале, число решений тоже меняется. Если пуста середина стороны, их больше всего — 85258, а если пуста внутренняя лунка, то меньше — 1550 (подробнее — в статье о решении треугольной доски).

Английская доска в 33 лунки: считается, что больше 4 × 10 в 16-й степени

Решений, которыми на английской доске в 33 лунки, начав с центра, оставляют один шарик в центре, по расчётам больше 4 × 10 в 16-й степени. Это число на много порядков больше, чем на треугольной доске.

Почему их так много? Я посчитал, сколько разных позиций бывает после каждого хода.

ХодПоследовательности ходовПозицииСводя повороты
1441
212122
360608
440029639
529601338171
6246005648719
7221072218422757

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

  • Для первого хода четыре варианта, но все они при повороте совпадают (статья о первом ходе).
  • С каждым ходом число позиций растёт примерно в 4–5 раз.
  • Начиная с четвёртого хода в одну и ту же позицию можно прийти разными путями. К седьмому ходу число последовательностей ходов больше числа позиций более чем в 10 раз.

Число решений для маленьких задач

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

ДоскаРешений
8 шариков19
12 шариков679
16 шариков3336232

Чем больше шариков, тем сильнее растёт число решений. Значит ли это, что доски с большим числом шариков проще?

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

ДоскаПервые ходыХоды, ведущие к решению
8 шариков64
12 шариков63
16 шариков96

На любой доске есть ходы-ловушки: сделав такой ход, главный шарик уже не оставить. Даже если решений много, но по пути много ловушек, играть на такой доске трудно.

Сложность в приложении определяют «ходы-ловушки»

В режиме «Задачи» приложения «Peg Solitaire» сложность тоже определяется этой идеей. Приложение смотрит, какая доля ходов в ходе решения не позволяет достичь цели (доля ходов-ловушек), и пересоздаёт доску, пока доля не попадёт в диапазон сложности от ★1 до ★5. Число шариков и размер доски тоже заданы для каждой сложности.

Число шариков для каждой сложности указано в статье «Как играть».