"Сапер": от игры к задачам

Большинство читателей, вероятно, играли в "Сапера" (он же "Minesweeper"), ведь эта игрушка входит в стандартный комплект поставки Windows. "Сапер" относится к тем простеньким играм, вроде "Tetris" или "Lines", в которые люди иной раз играют часами, чему сами же и удивляются. Это - верный признак гениальности игры. Такие игры иногда порождают целые классы занимательных задач, и "Сапер" не является исключением. Но прежде чем перейти к задачам, напомню правила игры.

Имеется прямоугольное минное поле, поделенное на закрытые клетки. Одни клетки пусты, в другие заложены мины. Любую клетку можно открыть или пометить как содержащую мину. Можно пометить и пустую клетку. Если открыть клетку с миной, то игра сразу заканчивается (сапер ошибается один раз). Открыв пустую клетку, вы увидите в ней цифру (от единицы до восьмерки), равную числу мин, находящихся в восьми клетках, которые окружают открытую вами клетку. (Если открытая пустая клетка окружена клетками, также не содержащими мин, то эти пустые клетки открываются автоматически.) Цель игры - за минимальное время правильно пометить все мины и открыть все остальные клетки.

Найти все мины на поле -цель "саперных" задач первого типа. На рисунках 1-8 изображены минные поля, некоторые клетки которых уже открыты. Попробуйте найти все мины на рисунках. Число слева над игровым полем показывает, сколько всего мин размещено на поле.

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

Алгоритм решения таких задач может быть простым, например:

Открыть клетку A.

Если A=2, то пометить клетку B (как содержащую мину), иначе пометить клетку С.

Но алгоритм может быть и крайне сложным, многократно разветвляющимся. Составить алгоритм нетрудно. Можно просто, как в самой игре, разыгрывать позицию, при этом лишь нужно следить за возможными разветвлениями. Но лучшим решением будет кратчайший алгоритм, а найти его, особенно в позициях, где еще много закрытых клеток, бывает очень нелегко. Тем не менее, попробуйте найти кратчайший алгоритм решения задач на рис. 9 и 10. Первая - простая, вторая уже посложнее.

Другой класс "саперных" задач - вероятностные задачи. Обычно в них требуется найти вероятность того, что в какой-либо клетке в данной позиции находится мина. При решении таких задач учитывается число и расположение уже обнаруженных мин, а также число еще закрытых клеток поля (не стану приводить общую формулу - найдите, пожалуйста, сами). Попробуйте вычислить вероятность того, что на рисунках 11-14 в клетке X находится мина.

Но бывают и другие вероятностные задачи, например: дано поле 8х8 клеток с десятью минами, открывается клетка в левом верхнем углу. Найдите вероятность того, что в этой клетке стоит единица (двойка, тройка, ноль). А когда найдете, проверьте, учитывали ли вы то, что самая первая открываемая клетка никогда не содержит мину?

Нашли? А теперь попробуйте вычислить вероятность того, что в поле размером MхN и числом мин, равным K, в угловой клетке стоит цифра R=0, 1, 2, 3. И с этим справились? Ну тогда найдите общую формулу вычисления вероятности той или иной цифры на первой открываемой клетке минного поля: дано поле MхN, К - число мин на поле, L - число клеток, смежных с открываемой.

А вот другой тип "саперных" задач: попробуйте так расставить мины на поле 8х8 (в общем случае - MхN), чтобы в каждой клетке стояла цифра от 1 до 8 (не 0). Сколько мин минимально для этого потребуется? А максимально? Сколько существует способов расстановки?

И еще один тип задач: как следует расставить десять мин на поле 8х8, чтобы сумма всех цифр, стоящих на свободных клетках, была равна, например, сорока? А пятидесяти, шестидесяти, какому-либо другому числу? Какова минимальная сумма? А максимальная? И как при этом расставить мины?

Вот еще две несложные задачи.

Найдите наименьшую возможную конфигурацию открытых клеток, закрытых клеток и помеченных мин, в которой невозможно определить, под какой клеткой мина (этакий геймстоппер, когда в игре попадается - очень раздражает).

Дано поле 10х10 клеток. Открыта вся верхняя строка. Во всех клетках - единицы. Какова вероятность нахождения мины во второй сверху строке в четвертом столбце?

И наконец задание для программистов: составить программу, которая играла бы в "Сапер" и как можно реже проигрывала. Сделать это непросто, полный перебор тут не годится, надо программировать эвристики, чем больше - тем лучше.

Удачи в решении!

* * *

Дополнение Константина Кнопа

Эта статья пришла по почте и напечатана почти без исправлений, хотя у меня сильно чесались руки добавить еще несколько задач на эту же тему. Решив не вставлять их в авторский текст, я все-таки хочу их привести.

1. В игре (скажем, на поле 8х8) часто бывает так, что о некоторых клетках достоверно известно, есть там мины или нет, а о других клетках можно только догадываться. Чему равно наибольшее количество клеток, о которых нельзя ничего сказать достоверно? (Делать ходы нельзя, можно анализировать только начальную информацию.) В частности, бывает ли геймстоппер с самого начала?

2. Напишите программу для игры "Сапер вдвоем": игрок делает ходы до тех пор, пока не нарвется на мину, а затем ходит второй игрок, и так далее. Выигрывает тот, кто откроет последнюю мину.