Алгоритм решения

Ответ 1

Генерация сетки проста. Есть несколько простых алгоритмов, которые вам нужны при выполнении перемещения игрока, чтобы определить, какие квадраты открывать и потеряли ли они или выиграли.

Создание сетки

Самый простой алгоритм - разместить все мины случайным образом. (Убедитесь, что вы не перекрываете их!)

Проблема: Первый клик игрока может быть моим.

Улучшение: Задержка генерации сетки до тех пор, пока пользователь не нажмет на первый квадрат и не поместит никаких мин в этот квадрат.

Проблема: Первый клик игрока может показать ненулевой номер, и они будут вынуждены щелкнуть случайным образом, пока что-то не откроется.

Улучшение: не создавайте никаких шахт в (до) восьми квадратов вокруг первого щелчка.

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

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

Другим, менее распространенным способом устранения двусмысленностей является обнаружение, когда игрок знает, что они выбирают между одинаково вероятными возможностями и "сворачивают форму волны" в позицию, на которую они решили. Я никогда не видел этого в действии, но было бы весело.

Игра в игру

Помимо отметки флажков, игрок может сделать два вида ходов, чтобы попытаться раскрыть квадраты:

• Одиночная догадка: Игрок нажимает на квадрат с неизвестным состоянием и без флага. Выясните квадрат, посмотрите, умер ли игрок, и введите в него номер. Если квадрат содержит 0, повторите это рекурсивно для всех окружающих квадратов. Это должно быть в специальной функции, чтобы отделить ее от обработчика событий GUI, чтобы сделать рекурсию легкой и потому, что она повторно используется в многоязычности.

• Multiguess: Игрок нажимает на квадрат, который не обнаружен и известен как безопасный. Если количество окружающих флагов равно числу в этом квадрате, мы открываем неокрашенные квадраты, используя ту же процедуру, что и выше.

Победа в игре

Если количество закрытых квадратов совпадает с количеством мин, то игрок выиграл, даже если они не поместили флаг на каждый квадрат.

Когда проигрыватель проигрывает, обычно принято отмечать любые неправильные догадки, которые они сделали, оставшиеся мины и шахту, на которую они наступили.

Ответ 2

Я просто хочу добавить следующее, если вы попытаетесь написать решатель - Minesweeper NP завершен. Это означает, что до тех пор, пока кто-то не докажет P = NP, возможно, что вы можете ничего не делать лучше, чем выполнять поиск грубой силы в некоторых ситуациях (но, возможно, игра не является NP полной для небольших полей).

Ответ 3

Вот мой решатель тральщика:

• для каждого квадрата числа:
  • если количество неоткрытых вокруг == квадратного числа: все они являются минами
  • если квадратное число - количество помеченных вокруг == 0: все нераскрытые не являются минами
• использовать правило подмножества

Вот фактическая реализация, обратите внимание, что она использует правило подмножества, которое сложнее объяснить https://github.com/SHiNKiROU/Minesweeper/blob/master/src/org/shinkirou/minesweeper/MinesweeperSolver.java#L27

Конечно, мой алгоритм иногда может терпеть неудачу. Я планирую реализовать решатель обратного отслеживания в стиле Prolog

Ответ 4

Я определенно не эксперт тральщика, но вот алгоритм, который я использую, когда пытаюсь его решить:

Перейдите по всем квадратам, которые являются границей выявленной области. Для каждого из этих квадратов подсчитайте количество мин, которые вы обнаружили рядом с ним. вычтите число, которое написано в квадрате (истинное количество мин, находящихся вокруг него). Это количество нераскрытых мин, оставшихся вокруг этого квадрата. Разделите это на количество нераскрытых квадратов вокруг текущего квадрата. Это вероятность каждого из соседних квадратов, содержащих шахту. Если какой-либо квадрат имеет вероятность 1, вы отмечаете его как шахту. Если какой-либо квадрат имеет вероятность 0, вы отмечаете его как безопасный. Затем вы обновите соответствующие номера.

Что вы делаете, если квадрат не имеет вероятности 0 или 1? Оптимальный алгоритм учитывал бы ограничения от множества квадратов. Но, как я писал в начале, я не специалист по тральщику, поэтому я выбираю случайным образом из других квадратов с вероятностью, ближайшей к 0 или к 1.

Ответ 5

Отметьте это: http://quantum-p.livejournal.com/19616.html

Любая позиция на доске, которая не может быть решена интуитивно с мышлением обезьяны, - это матрица, которая могла бы решить некоторые отдельные (или целые позиции) квадраты, которые могут привести к лучшему разрешению ставок. Простые случайные догадки не дали хороших результатов. Я реализовал этот метод в своем решающем алгоритме на С++, добавив линейную систему уравнений-решателей. Я изучаю сложность Minesweeper, запуская десятки тысяч игр через алгоритм и делая статистику.

Мой алгоритм решает до 85% (9,9,10) тральщиков с легким уровнем. Я еще не выполнил полных тестов на других уровнях сложности, но меньшие тесты показывают, что средний уровень (16,16,40) имеет решающую скорость 55-60% и жесткий уровень (30,16,99) всего лишь 5 -10%. Я собираюсь добавить несколько новых вещей, которые сделают его наиболее оптимальным.

Ответ 6

Как отметил Анри, правильным способом решения тральщика является математика, в частности математика линейной алгебры матриц для детерминированной части. У меня есть целый пост, который:

• объясняет, как работает этот метод.
• имеет рабочий код, который можно компилировать и запускать на любой платформе.
• содержит код для создания игры и решателя.

Вы можете видеть все здесь: https://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/

Я бы рекомендовал прочитать это, а затем подумать об этом. Вероятностную часть Minsweeper можно решить, используя статистику, но у меня пока нет хорошего плана. Тем не менее, другие люди тоже заглянули в него.

Ответ 7

Вы видели эту реализацию С# для игры? Исходный код загружается, и объясняется объектная модель.

Ответ 8

Комментарии заключаются в том, что вам не нужен алгоритм для создания игры. Я считаю, что вы имеете в виду алгоритм в смысле решения, и каждый может понять его так же.

Однако любое решение проблемы можно считать алгоритмом.

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

Игровое поле можно рассматривать как двумерный массив. У вас будет алгоритм, связанный с каждой операцией. Первой операцией, вероятно, будет случайный набор минных местоположений с координатами x, y с параметром количества мин и размера платы. У вас будет еще один алгоритм, связанный с раскрытием квадрата, который берет плату и местоположение, и определяет, сколько мин находится рядом с ним. Окончательный алгоритм взял бы плату и проверил, оставлены ли какие-либо квадраты без мин.

Теперь вы можете взять каждый из этих алгоритмов и попытаться оптимизировать каждую из них для лучшей производительности и сказать "какой лучший способ подсчитать квадраты с минами, смежными с текущим квадратом, учитывая двумерный массив с использованием координат x, y.