Brainvita_solution

brainvita_solution.py

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"-----\nФишек на поле: {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❌ Решение не найдено (попробуйте увеличить лимит поиска)")