Каков алгоритм построения тральщика?

Question

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

Answer 1

Возможно, что-то в линиях:

grid = [n,m] // initialize all cells to 0 
for k = 1 to number_of_mines 
    get random mine_x and mine_y where grid(mine_x, mine_y) is not a mine 
    for x = -1 to 1 
     for y = -1 to 1 
     if x = 0 and y = 0 then 
      grid[mine_x, mine_y] = -number_of_mines // negative value = mine 
     else 
      increment grid[mine_x + x, mine_y + y] by 1 

Это в значительной степени это ...

** EDIT **

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

** UPDATE **

I «Мы взяли на себя смелость сыграть немного с JS bin, придумали функциональный Minesweeper game demo. Это просто продемонстрировать алгоритм, описанный в этом ответе. Я не оптимизировал случайность сгенерированной позиции шахты, поэтому некоторые игры могут быть невозможными или слишком легкими. Кроме того, нет никакой проверки относительно того, сколько мин есть в сетке, так что вы можете создать сетку 2 на 2 с 1000 минами .... но это приведет только к бесконечному циклу :) Наслаждайтесь!

Answer 2

Вы просто семена мин, и после этого вы пересекаете каждую ячейку и считаете соседние мины.

Или вы устанавливаете каждый счетчик на 0 и с каждой посевной шахтой, вы увеличиваете все соседние счетчики ячеек.

Answer 3

Если вы хотите разместить m шахты на квадратах N, и у вас есть доступ к генератору случайных чисел, вы просто пройдете через оставшиеся квадраты и для каждого квадратного вычисления (осталось # мин)/(осталось # квадратов) и поместите шахта, если ваше случайное число равно или ниже этого значения.

Теперь, если вы хотите, чтобы маркировать каждый квадрат с числом соседних шахт, вы можете просто сделать это прямо:

count(x,y) = sum(
    for i = -1 to 1 
    for j = -1 to 1 
     1 if (x+i,y+j) contains a mine 
     0 otherwise 
) 

или если вы предпочитаете вы можете начать с массивом нулей и увеличиваем каждый по одному в квадрате 3x3, у которого есть шахта в центре. (Это не мешает номеру квадратов с минами.)

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