«Сапёр» известен как игра-бонус на компьютере, но о нём говорили и в математике, и в исследованиях по информатике. Ключевое слово — «NP-полная задача».
«Сапёр» — NP-полная задача
Около 2000 года математик Ричард Кей показал, что следующая задача, связанная с «Сапёром», относится к трудным задачам, которые называют «NP-полными».
Дано поле с числами. Есть ли хотя бы одна расстановка мин, не противоречащая этим числам?
Вопрос «Безопасна ли эта клетка?», который мы задаём во время обычной игры, тесно связан с этой задачей.
Что такое NP-полнота
Если сказать просто, NP-полная задача обладает такими свойствами.
- Проверить ответ легко. Если вам покажут одну расстановку мин, вы быстро проверите, совпадает ли она со всеми числами.
- Найти ответ трудно (так считается). С ростом поля число вариантов расстановки резко растёт. Среди известных сегодня способов нет такого, который быстро находил бы ответ для любого поля.
Кроме того, известно, что NP-полные задачи можно свести друг к другу. Если найдётся способ быстро решать хотя бы одну из них в любом случае, то и все остальные NP-полные задачи окажутся быстро решаемыми. Вопрос «есть ли такой быстрый способ» известен как гипотеза «P ≠ NP» — знаменитая нерешённая проблема, за решение которой назначена премия в миллион долларов.
Число расстановок быстро становится огромным
Проверять расстановки трудно потому, что число вариантов становится очень большим.
- Расставить 8 мин на поле 9×7 можно числом способов, равным числу сочетаний из 63 клеток по 8, — примерно 3,9 миллиарда.
- Расставить 75 мин на поле 26×15 можно числом способов, равным числу сочетаний из 390 клеток по 75, — это число больше чем из 80 цифр.
Конечно, в реальной игре перебирать всё не нужно. Клетки, не соприкасающиеся с числами, можно рассматривать вместе, а во многих ситуациях всё решается по одному-двум числам. Но там, где числа сложно переплетены, надёжно найти ответ бывает трудно.
Приложение выбирает только поля, которые решает человеческая логика
Строя поле, приложение «Сапёр» проверяет, можно ли решить его от начала до конца, используя лишь три правила, которыми пользуются люди.
- Что видно по одному числу.
- Что видно по сочетанию двух чисел.
- Что видно по числу оставшихся мин на всём поле.
Каждое из правил рассматривает небольшую область и проверяется быстро. Если поле этими тремя правилами не решается, мины переставляются и поле строится заново. Поэтому игроку не нужно тяжёлое рассуждение с перебором всех расстановок — любое поле решается до конца.
Игровые поля, в которые можно поиграть прямо в статьях этого сайта, построены по тому же принципу. Когда я измерил время построения поля того же размера, что ★5, на компьютере, в среднем оно заняло несколько миллисекунд на поле.
Головоломки и математика
Известно, что и многие другие карандашные головоломки, например судоку, в общем виде с увеличением поля NP-полны. Многие головоломки, которые приятно решать людям, устроены так, что их можно решить последовательными рассуждениями, не перебирая всё. Поля без угадывания в приложении «Сапёр» — одна из таких.
О расчёте вероятностей рассказано в статье Вероятности в «Сапёре».
