БАЛДА

Игрок 1 0
Ход: Игрок 1
Игрок 2 0
Составленное слово: -

Использованные слова:

Правила

  1. Игра начинается со слова из 5 букв в центре поля
  2. Игроки по очереди добавляют по одной букве в пустую клетку, соседнюю с заполненной
  3. После добавления буквы нужно составить слово, выбирая соседние клетки
  4. Слово должно включать только что добавленную букву
  5. Нельзя использовать слова, которые уже были названы
  6. Очки = количество букв в слове
  7. Побеждает игрок с большим количеством очков

Математическая задачка от Балды: сколько всего слов может существовать на доске n×n?

Подробнее (спойлер: много)

Доска моделируется как решётчатый граф Pn×Pn, где рёбра соединяют соседние по горизонтали/вертикали клетки. Каждая допустимая последовательность букв — это простой путь (self‑avoiding walk), т. е. путь без повторного посещения клеток. Задача: подсчитать все такие пути.

ДоскаКол-во путей
1×11
2×228
3×3653
4×428 512
5×53 060 417
6×6873 239 772
7×7687 430 009 069

Эти значения получены перебором. Кто придумает, как посчитать для 8×8 и дальше за разумное время - прошу в репозиторий kidavspb/BALDA