В данной лабораторной работе вам предстоит разработать полнофункциональную игру «Сапёр» (Minesweeper) для командной строки и создать автоматизированный решатель, способный её проходить.
Проект охватывает три ключевых этапа:
- Создание игрового движка: разработка надежной основы для игры, используя классы и списки для моделирования игрового поля.
- Реализация детерминированного решателя: написание модуля, который делает логически безупречные выводы, используя множества и словари для эффективной обработки ограничений.
- Разработка вероятностного модуля: создание алгоритма, который принимает обоснованные решения в ситуациях неопределенности, применяя рекурсивный перебор для анализа всех возможных состояний.
Разработка вероятностного модуля: Вы создадите алгоритм, который принимает обоснованные решения в ситуациях неопределенности, применяя рекурсивный перебор для анализа всех возможных состояний.
Формализация правил: Игра «Сапёр» представляет собой прямоугольную сетку размером n×m, под некоторыми ячейками которой скрыты мины. Цель игрока — открыть все ячейки, не содержащие мин. При открытии ячейки, под которой нет мины, отображается число от 0 до 8. Это число указывает на точное количество мин, находящихся в восьми соседних ячейках. Если в соседних ячейках мин нет (число 0), то все они открываются автоматически. Игра считается выигранной, когда все безопасные ячейки открыты. Поражение наступает при открытии ячейки с миной.
Вычислительная сложность: Задача определения, является ли данная конфигурация поля «Сапёра» разрешимой, является co-NP-полной. Это означает, что не существует известного эффективного (полиномиального по времени) алгоритма, который мог бы гарантированно решить любую конфигурацию. Этот факт объясняет, почему ваш решатель должен быть многоуровневым: он должен уметь не только делать быстрые логические выводы, но и быть готовым к ситуациям, когда детерминированная логика заходит в тупик, и единственным выходом остаётся сделать обоснованное, но рискованное предположение.
- Разработка эмулятора игры: Создать интерактивное консольное приложение, позволяющее пользователю играть в «Сапёр».
- Реализация детерминированного решателя: Написать модуль, который применяет базовые и продвинутые логические правила для нахождения гарантированно безопасных и заминированных ячеек.
- Применение методов CSP: Смоделировать задачу как проблему удовлетворения ограничений (Constraint Satisfaction Problem, CSP) для решения сложных конфигураций.
- Разработка вероятностного решателя: Реализовать модуль, который вычисляет точные вероятности нахождения мин и делает наиболее безопасное предположение.
- Анализ производительности: Провести эмпирический анализ эффективности разработанного решателя.
На этом этапе вы создадите ядро игры, уделив особое внимание правильному проектированию структур данных.
Требования к именованию: Вся логика игрового движка должна находиться в файле minesweeper_engine.py.
Модель ячейки: Вам необходимо создать класс Cell для хранения состояния каждой ячейки. Для этой цели идеально подходит dataclasses из стандартной библиотеки Python. Класс должен содержать как минимум следующие атрибуты:
is_mine: boolis_revealed: boolis_flagged: booladjacent_mines: int (от 0 до 8)
Модель игрового поля: Игровое поле должно быть представлено как вложенный список: list[list[Cell]]. Такая структура обеспечивает интуитивно понятный доступ к любой ячейке по её координатам (row, col).
Генерация поля: Вам следует реализовать функцию generate_board(rows, cols, num_mines, first_click_coords). Важным требованием является обеспечение гарантированно безопасного первого хода. Расстановка мин должна происходить после первого хода игрока, исключая ячейку, на которую был сделан ход, из списка кандидатов для размещения мины.
Предварительный расчет смежности: После расстановки мин необходимо выполнить однократный проход по всей сетке для вычисления значения adjacent_mines для каждой ячейки. Этот предварительный расчет (пре-кэширование) является важной оптимизацией.
Требования к именованию: Основной исполняемый файл для взаимодействия с пользователем должен называться play_minesweeper.py.
Разработка интерфейса командной строки (CLI): После каждого хода программа должна выводить на экран актуальное состояние игрового поля. Используйте следующие символы:
#— неоткрытая ячейкаF— флаг*— мина (после проигрыша)0-8— открытая безопасная ячейка
Обработка действий пользователя: Программа должна корректно обрабатывать команды в формате:
open <row> <col>(илиo <row> <col>): Открывает ячейку.flag <row> <col>(илиf <row> <col>): Устанавливает/снимает флаг.
Каскадное открытие: Если открытая ячейка имеет 0 соседних мин, все её 8 соседей должны быть автоматически открыты. Рекурсивная реализация этого механизма может привести к ошибке RecursionError. Вам необходимо реализовать итеративный алгоритм, используя очередь (collections.deque) для поиска в ширину (BFS). Это продемонстрирует ваше умение выбирать подходящие структуры данных для решения классических алгоритмических задач.
Определение состояний завершения игры: Реализуйте логику, которая проверяет условия победы (все безопасные ячейки открыты) и поражения (открыта ячейка с миной).
Требования к именованию: Вся логика решателя должна находиться в файле solver.py в классе Solver.
Описание: Этот модуль имитирует наиболее очевидные стратегии. Ваш алгоритм должен циклически сканировать все открытые ячейки и применять два простых правила до тех пор, пока можно сделать хотя бы один гарантированный ход.
Правило 1 (Все мины): Если число в ячейке N равно количеству неоткрытых соседей, все эти соседи — мины.
Правило 2 (Все безопасны): Если число в ячейке N равно количеству флагов среди соседей, все остальные неоткрытые соседи безопасны.
Требования к реализации:
Вам необходимо реализовать метод solve_step(self, board: list[list[Cell]]) -> tuple[set[tuple[int, int]], set[tuple[int, int]]].
Метод принимает на вход текущее состояние игрового поля.
Он должен возвращать кортеж из двух множеств:
- Множество set координат (row, col), которые гарантированно безопасны для открытия.
- Множество set координат (row, col), где гарантированно находятся мины (для установки флагов).
Метод должен применять Правила 1 и 2 итеративно, пока не перестанет находить новые ходы.
Теоретическая справка: Часто базовый решатель заходит в тупик. Такие ситуации эффективно моделируются как Проблема Удовлетворения Ограничений (CSP).
- Переменные: Каждая закрытая ячейка на границе с открытыми является булевой переменной (1 — мина, 0 — безопасно).
- Ограничения: Каждая открытая ячейка с числом N создает линейное ограничение: сумма значений соседних переменных должна равняться N минус количество уже найденных мин.
Алгоритм (Правило подмножеств):
Если набор переменных одного ограничения является подмножеством набора переменных другого, можно вычесть одно уравнение из другого и получить новое, более простое ограничение.
Пример:
Ограничение 1: x1 + x2 = 1
Ограничение 2: x1 + x2 + x3 = 2
Вычитая (1) из (2), получаем: x3 = 1. Это означает, что x3 — мина.
Требования к реализации:
Вам необходимо расширить логику метода solve_step.
Реализуйте внутренний метод _generate_constraints, который анализирует поле и формирует список ограничений. Каждое ограничение удобно представить как кортеж: (frozenset[tuple[int, int]], int), где frozenset — неизменяемое множество координат переменных, а int — количество мин среди них.
Реализуйте метод _apply_subset_rule, который итерирует по всем парам ограничений и выводит новые факты.
Если в результате применения правила подмножеств были найдены новые безопасные ячейки или мины, добавьте их в соответствующие множества, которые возвращает solve_step.
Описание: Когда детерминированный решатель не может сделать ход, необходимо сделать наиболее безопасное предположение. Для этого нужно вычислить точную вероятность нахождения мины для каждой неоткрытой ячейки.
Требования к именованию: Логика должна быть реализована в методе make_probabilistic_move(self, board: list[list[Cell]]) -> tuple[int, int]. Метод должен возвращать координаты (row, col) ячейки с наименьшей вероятностью мины.
Алгоритм:
- Идентификация независимых областей: Разделите все пограничные ячейки на независимые группы. Две ячейки связаны, если они входят в одно ограничение. Для этой задачи идеально подходит структура данных Система непересекающихся множеств (Union-Find) или стандартный обход графа (BFS/DFS).
- Перебор конфигураций: Для каждой независимой области найдите все возможные расстановки мин, которые удовлетворяют всем ограничениям. Это классическая задача, которая решается с помощью рекурсивного алгоритма с возвратом (backtracking).
- Подсчет вероятностей: Для каждой ячейки Xi в области вычислите вероятность по формуле P(Xi=1) = Общее количество валидных решений / Количество валидных решений, где Xi = 1 Этот метод основан на подсчете всех "возможных миров", совместимых с имеющимися данными.
- Выбор хода: Проанализируйте вероятности для всех пограничных ячеек и верните координаты той, у которой вероятность быть миной минимальна.
По завершении работы вы должны предоставить:
- Работоспособное консольное приложение «Сапёр» (
play_minesweeper.py). - Модуль с логикой игры (
minesweeper_engine.py). - Класс Solver (
solver.py), который последовательно применяет все три уровня логики.
| Описание | Баллы |
|---|---|
| Структуры данных и состояние: Корректная реализация Cell, генерация поля, безопасный первый ход, предрасчет. | 3 |
| CLI и игровая логика: Текстовый интерфейс, обработка команд, итеративное каскадное открытие. | 3 |
| Базовый решатель: Корректная реализация solve_step с базовыми правилами. | 3 |
| Продвинутый решатель (CSP): Реализация правила подмножеств в solve_step. | 6 |
| Вероятностный решатель: Реализация make_probabilistic_move с поиском областей, backtracking и расчетом вероятностей. | 5 |
is_revealed: bool
is_flagged: bool
adjacent_mines: int (от 0 до 8)
Модель игрового поля: Игровое поле должно быть представлено как вложенный список: list[list[Cell]]. Такая структура обеспечивает интуитивно понятный доступ к любой ячейке по её координатам (row, col).
Генерация поля: Вам следует реализовать функцию generate_board(rows, cols, num_mines, first_click_coords). Важным требованием является обеспечение гарантированно безопасного первого хода. Расстановка мин должна происходить после первого хода игрока, исключая ячейку, на которую был сделан ход, из списка кандидатов для размещения мины.
Предварительный расчет смежности: После расстановки мин необходимо выполнить однократный проход по всей сетке для вычисления значения adjacent_mines для каждой ячейки. Этот предварительный расчет (пре-кэширование) является важной оптимизацией.
Подзадача: Интерфейс командной строки и игровая логика (3 балла) Требования к именованию: Основной исполняемый файл для взаимодействия с пользователем должен называться play_minesweeper.py.
Разработка интерфейса командной строки (CLI): После каждого хода программа должна выводить на экран актуальное состояние игрового поля. Используйте следующие символы:
F — флаг
- — мина (после проигрыша)
0-8 — открытая безопасная ячейка
Обработка действий пользователя: Программа должна корректно обрабатывать команды в формате:
open (или o ): Открывает ячейку.
flag (или f ): Устанавливает/снимает флаг.
Каскадное открытие: Если открытая ячейка имеет 0 соседних мин, все её 8 соседей должны быть автоматически открыты. Рекурсивная реализация этого механизма может привести к ошибке RecursionError. Вам необходимо реализовать итеративный алгоритм, используя очередь (collections.deque) для поиска в ширину (BFS). Это продемонстрирует ваше умение выбирать подходящие структуры данных для решения классических алгоритмических задач.
Определение состояний завершения игры: Реализуйте логику, которая проверяет условия победы (все безопасные ячейки открыты) и поражения (открыта ячейка с миной).
Часть II - Детерминированный решатель (9 баллов) Требования к именованию: Вся логика решателя должна находиться в файле solver.py в классе Solver
Подзадача: Базовый решатель (3 балла) Описание: Этот модуль имитирует наиболее очевидные стратегии. Ваш алгоритм должен циклически сканировать все открытые ячейки и применять два простых правила до тех пор, пока можно сделать хотя бы один гарантированный ход.
Правило 1 (Все мины): Если число в ячейке N равно количеству неоткрытых соседей, все эти соседи — мины.
Правило 2 (Все безопасны): Если число в ячейке N равно количеству флагов среди соседей, все остальные неоткрытые соседи безопасны.
Требования к реализации:
Вам необходимо реализовать метод solve_step(self, board: list[list[Cell]]) -> tuple[set[tuple[int, int]], set[tuple[int, int]]].
Метод принимает на вход текущее состояние игрового поля.
Он должен возвращать кортеж из двух множеств:
Множество set координат (row, col), которые гарантированно безопасны для открытия.
Множество set координат (row, col), где гарантированно находятся мины (для установки флагов).
Метод должен применять Правила 1 и 2 итеративно, пока не перестанет находить новые ходы.
Подзадача: Продвинутый решатель на основе CSP (6 баллов) Теоретическая справка: Часто базовый решатель заходит в тупик. Такие ситуации эффективно моделируются как Проблема Удовлетворения Ограничений (CSP).
Переменные: Каждая закрытая ячейка на границе с открытыми является булевой переменной (1 — мина, 0 — безопасно).
Ограничения: Каждая открытая ячейка с числом N создает линейное ограничение: сумма значений соседних переменных должна равняться N минус количество уже найденных мин.
Алгоритм (Правило подмножеств):
Если набор переменных одного ограничения является подмножеством набора переменных другого, можно вычесть одно уравнение из другого и получить новое, более простое ограничение.
Пример:
Ограничение 1: x1 + x2 = 1
Ограничение 2: x1 + x2 + x3 = 2
Вычитая (1) из (2), получаем: x3 = 1. Это означает, что x3 — мина.
Требования к реализации:
Вам необходимо расширить логику метода solve_step.
Реализуйте внутренний метод _generate_constraints, который анализирует поле и формирует список ограничений. Каждое ограничение удобно представить как кортеж: (frozenset[tuple[int, int]], int), где frozenset — неизменяемое множество координат переменных, а int — количество мин среди них.
Реализуйте метод _apply_subset_rule, который итерирует по всем парам ограничений и выводит новые факты.
Если в результате применения правила подмножеств были найдены новые безопасные ячейки или мины, добавьте их в соответствующие множества, которые возвращает solve_step.
Часть III - Вероятностный решатель (5 баллов)
Подзадача - обоснованные предположения (5 баллов) Описание: Когда детерминированный решатель не может сделать ход, необходимо сделать наиболее безопасное предположение. Для этого нужно вычислить точную вероятность нахождения мины для каждой неоткрытой ячейки.
Требования к именованию: Логика должна быть реализована в методе make_probabilistic_move(self, board: list[list[Cell]]) -> tuple[int, int]. Метод должен возвращать координаты (row, col) ячейки с наименьшей вероятностью мины.
Алгоритм:
Идентификация независимых областей: Разделите все пограничные ячейки на независимые группы. Две ячейки связаны, если они входят в одно ограничение. Для этой задачи идеально подходит структура данных Система непересекающихся множеств (Union-Find) или стандартный обход графа (BFS/DFS).
Перебор конфигураций: Для каждой независимой области найдите все возможные расстановки мин, которые удовлетворяют всем ограничениям. Это классическая задача, которая решается с помощью рекурсивного алгоритма с возвратом (backtracking).
Подсчет вероятностей: Для каждой ячейки Xi в области вычислите вероятность по формуле P(Xi=1) = Общее количество валидных решений / Количество валидных решений, где Xi = 1 Этот метод основан на подсчете всех "возможных миров", совместимых с имеющимися данными.
Выбор хода: Проанализируйте вероятности для всех пограничных ячеек и верните координаты той, у которой вероятность быть миной минимальна.
Заключение и требования к сдаче
Ожидаемые результаты По завершении работы вы должны предоставить:
Работоспособное консольное приложение «Сапёр» (play_minesweeper.py).
Модуль с логикой игры (minesweeper_engine.py).
Класс Solver (solver.py), который последовательно применяет все три уровня логики.
Критерии оценки Описание
Баллы
Структуры данных и состояние: Корректная реализация Cell, генерация поля, безопасный первый ход, предрасчет.
3
CLI и игровая логика: Текстовый интерфейс, обработка команд, итеративное каскадное открытие.
3
Базовый решатель: Корректная реализация solve_step с базовыми правилами.
3
Продвинутый решатель (CSP): Реализация правила подмножеств в solve_step.
6
Вероятностный решатель: Реализация make_probabilistic_move с поиском областей, backtracking и расчетом вероятностей.
5