Python-решение для игры Йога (Peg Solitaire, Brainvita)

Йога (английский солитер, Peg Solitaire или Brainvita) — классическая головоломка. На доске 7×7 с центральным крестом из 33 фишек, необходимо оставить как можно меньше фишек на поле, совершая прыжки через соседние фишки (которые при этом удаляются). В начале игры центральная фишка удаляется, так появляется место для прыжка фишек. Самый результативный вариант, когда после последнего хода остаётся только одна фишка на поле. Алгоритм ниже, за 31 ход достигает этой цели. Всего же вариантов этой игры порядка ~10¹⁶ (квадриллион).

Открываем Jupyter notebook...

Пишем код

# Импорт библиотек
from collections import deque
import sys
sys.setrecursionlimit(10000)

class Solitaire:
····def __init__(self):

········# Определяем валидные позиции на поле 7x7
········self.valid_positions = [(0, 2), (0, 3), (0, 4),
············(1, 2), (1, 3), (1, 4),
············(2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6),
············(3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6),
············(4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6),
············(5, 2), (5, 3), (5, 4),
············(6, 2), (6, 3), (6, 4)]

········# Создаём маппинг: (row, col) -> номер позиции
········self.pos_to_idx = {pos: idx for idx, pos in enumerate(self.valid_positions)}
········self.idx_to_pos = {idx: pos for idx, pos in enumerate(self.valid_positions)}

········# Предвычисляем все возможные ходы для каждой позиции
········self.moves = self._precompute_moves()

····def _precompute_moves(self):
········"""Предвычисляем все возможные ходы: откуда -> через кого -> куда"""
········moves = []
········directions = [(0, 2), (0, -2), (2, 0), (-2, 0)] # прыжки на 2 клетки
········for (r, c), start_idx in self.pos_to_idx.items():
············for dr, dc in directions:
················mid_r, mid_c = r + dr//2, c + dc//2
················end_r, end_c = r + dr, c + dc

················# Проверяем, что все позиции валидны
················if (mid_r, mid_c) in self.pos_to_idx and (end_r, end_c) in self.pos_to_idx:
····················mid_idx = self.pos_to_idx[(mid_r, mid_c)]
····················end_idx = self.pos_to_idx[(end_r, end_c)]
····················moves.append((start_idx, mid_idx, end_idx))
········return moves

····def state_to_tuple(self, board):
········"""Преобразуем состояние в кортеж для хеширования"""
········return tuple(board[idx] for idx in range(33))

····def solve(self, max_solutions=1):
········"""Поиск решения методом DFS с мемоизацией"""
········# Начальное состояние: все фишки есть, кроме центральной (№16)
········board = [1] * 33
········board[16] = 0 # убираем центральную фишку

········# Стек для DFS: (состояние, последовательность ходов)
········stack = [(board[:], [])]
········visited = {self.state_to_tuple(board)}
········solutions = []
········while stack and len(solutions) < max_solutions:
············board, moves_seq = stack.pop()
············pegs_left = sum(board)

············# Проверяем условие победы
············if pegs_left == 1:
················solutions.append((moves_seq, board))
················continue

············# Генерируем все возможные ходы
············for start, mid, end in self.moves:
················if board[start] == 1 and board[mid] == 1 and board[end] == 0:

····················# Делаем ход
····················new_board = board[:]
····················new_board[start] = 0
····················new_board[mid] = 0
····················new_board[end] = 1
····················state_key = self.state_to_tuple(new_board)
····················if state_key not in visited:
························visited.add(state_key)
························new_move = (start, mid, end)
························stack.append((new_board, moves_seq + [new_move]))
········return solutions

····def print_board(self, board):
········"""Визуализация поля с номерами позиций"""
········grid = [['.' for _ in range(7)] for _ in range(7)]

········# Заполняем номера позиций
········for idx, (r, c) in self.idx_to_pos.items():
············if board[idx] == 1:
················grid[r][c] = f"{idx:2d}"
············else:
················grid[r][c] = " "
········print("\nТекущее состояние поля:")
········print(" 0 1 2 3 4 5 6")
········for r in range(7):
············row_str = f"{r} " + " ".join(f"{grid[r][c]:>2}" for c in range(7))
············print(row_str)
········print(f"Фишек на поле: {sum(board)}\n")

····def print_solution(self, moves):
········"""Вывод решения с визуализацией каждого хода"""
········board = [1] * 33
········board[16] = 0
········print("-"*50)
········print("Начальное состояние (центральная фишка удалена):")
········self.print_board(board)
········for step, (start, mid, end) in enumerate(moves, 1):

············# Выполняем ход
············board[start] = 0
············board[mid] = 0
············board[end] = 1
············print(f"Ход №{step}:")
············print(f"фишка из [{start:2d}] прыгает через [{mid:2d}] → в [{end:2d}]")
············print(f"Удалена фишка [{mid:2d}]")
············self.print_board(board)
········print("-"*50)
········print(f"Результат: осталась {sum(board)} фишка(и) на позиции(ях): {[i for i, v in enumerate(board) if v == 1]}")

# Запуск решения
if __name__ == "__main__":
····game = Solitaire()
····print("Поиск оптимального решения игры...")
····print("Начальное состояние: 32 фишки, центральная позиция №16 пуста\n")
····solutions = game.solve(max_solutions=1)
····if solutions:
········moves, final_board = solutions[0]
········print(f"\n✅ Найдено решение. Ходов: {len(moves)}. (Фишек удалено:
len(moves)})!\n")
········game.print_solution(moves)

········# Статистика
········print(f"Всего ходов: {len(moves)}")
········print(f"Конечное количество фишек: {sum(final_board)}")
····else:
········print("\n❌ Решение не найдено (попробуйте увеличить лимит поиска)")

Вывод кода в консоль

Запуск кода. Начальное состояние

Первый ход

Вотрой ход

Далее идут ходы с третьего по тридцатый.

Последний ход и результаты

😺Код на GitHub: https://gist.github.com/MikyPo/d1e5e16e6376f3e4172fa7a904c355d5