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

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

Вот и все ...

** РЕДАКТИРОВАТЬ **

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

** ОБНОВЛЕНИЕ **

Я позволил себе немного поиграть с JS bin, здесь я получил функциональную демоверсию игры Minesweeper .Это просто для демонстрации алгоритма, описанного в этом ответе.Я не оптимизировал случайность сгенерированной шахты, поэтому некоторые игры могут быть невозможными или слишком легкими.Кроме того, нет никакой проверки того, сколько мин в сетке, поэтому вы можете создать сетку 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
)

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

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