Каков алгоритм создания тральщика

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

Ответы

Ответ 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 соседние ячейки не являются минами, или даже, возможно, предпочитают ограничивать количество мин, которые слишком далеки друг от друга и т.д.

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

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

Ответ 2

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

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

Ответ 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, у которого есть шахта в центре. (Не мешает число квадратов с минами.)

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