Создать доску тральщика, которая не нуждается в угадывании

Question

Я разрабатываю игру, похожую на Сапера (с измененными правилами), и хочу, чтобы игрок не угадал.Моя цель: сгенерированная доска с несколькими раскрытыми квадратами, и игрок может решить всю головоломку без каких-либо догадок.

Википедия упомянуто:

Некоторые реализацииof Minesweeper установит доску, никогда не ставя мину на первом обнаруженном квадрате, или расставляя доску так, чтобы решение не требовало угадывания.

Однако я не могу понять алгоритм.

Кроме того, в другом вопросе StackOverflow: Алгоритм решения тральщика

Улучшение: Запустите решатель рядом с генератором, убедившись, что у головоломки есть уникальное решение.Это требует некоторого умного подхода, и в большинстве вариантов этого не делается.

Я сомневаюсь, действительно ли это работает.Хорошо известно, что решение тральщика является NP-завершенным.

Таким образом, мои вопросы таковы:

• Как создать доску Сапер, которая не требует догадок?
• Если мы можем, каков конкретный алгоритм??
• Можем ли мы решить эту проблему за полиномиальное время детерминистически?Эта проблема NP-полная?Как это доказать?

Answer 1

Реализация Minesweeper в Портативная коллекция головоломок Саймона Тэтхама не требует догадок.(Он также лицензирован MIT, поэтому вы можете свободно копировать его реализацию, если хотите).

Answer 2

Хорошо известно, что траление минного тральщика завершено NP.

Это правда, но, возможно, не так важно, как вы думаете.Предложенный алгоритм выглядит как «многократно генерировать случайные доски, пока компьютер не сможет их решить».NP-твердость является свойством наихудшего случая, но здесь мы действительно заинтересованы в среднем случае твердости.Если генерируется необычно жесткая плата, мы можем установить время ожидания решателя и перезапустить с новой платой.

Кроме того, даже если бы был оракул, отличающий хорошие доски от плохих, вы бы действительно хотели, чтобы пользовательрешить сложную проблему, чтобы не гадать?Менее талантливый компьютерный решатель может сделать выбор в пользу более справедливых плат.