SpyLOG Rambler's Top100

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

КОНСТАНТИН ВЕТЛУГИН,
Опубликовано: 27.4.1998


© 2002, Издательский дом «КОМПЬЮТЕРРА» | http://www.computerra.ru/
Журнал «Компьютерра» | http://www.computerra.ru/
Этот материал Вы всегда сможете найти по его постоянному адресу: http://www.computerra.ru/offline/1998/244/1261/

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

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

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

mine1width=20mine2width=20mine3

mine4width=20mine5width=20mine6

mine7width=20mine8

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

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

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

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

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

mine9width=20mine10

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

mine11width=20mine12

mine13width=20mine14

Но бывают и другие вероятностные задачи, например: дано поле 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. Напишите программу для игры "Сапер вдвоем": игрок делает ходы до тех пор, пока не нарвется на мину, а затем ходит второй игрок, и так далее. Выигрывает тот, кто откроет последнюю мину.


Телефон редакции: (095) 232-2263
E-mail редакции: site@computerra.ru
По вопросам размещения рекламы обращаться к Алене Шагиной или Ирине Лашковой по телефону +7 (095) 232-2263 или электронной почте reclama@computerra.ru