¿Cuál es el algoritmo detrás de la generación de buscaminas

Question

Bueno, he estado en muchos sitios enseñando cómo resolverlo, pero me preguntaba cómo crearlo. No me interesan demasiado los aspectos de codificación, pero quería saber más sobre los algoritmos que lo respaldan. Por ejemplo, cuando la cuadrícula se genera con 10 minas más o menos, usaría cualquier función aleatoria para distribuirse a través de la cuadrícula, pero nuevamente ¿cómo establezco los números asociados a ella y decido qué casilla abrir? No pude enmarcar ningún algoritmo genérico sobre cómo iba a hacer eso.

Answer 1

Tal vez algo en la línea de:

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 

Eso es más o menos lo ...

** ** EDITAR

Debido a que este algoritmo podría plomo en la creación de una tablero con algunas minas agrupadas demasiado juntas, o peor muy dispersas (por lo tanto aburrido de resolver), puede agregar validación adicional al generar mine_x y mine_y número. Por ejemplo, para asegurar que por lo menos 3 células vecinas no son minas, o incluso tal vez a favor de limitar el número de minas que están demasiado lejos unos de otros, etc.

** ** ACTUALIZACIÓN

I Me he tomado la libertad de jugar un poco con JS bin aquí se le ocurrió un funcional Minesweeper game demo. Esto es simplemente para demostrar el algoritmo descrito en esta respuesta. No optimicé la aleatoriedad de la posición de la mina generada, por lo tanto, algunos juegos podrían ser imposibles o demasiado fáciles. Además, no hay ninguna validación en cuanto a la cantidad de minas que hay en la cuadrícula, por lo que puedes crear una cuadrícula de 2 por 2 con 1000 minas ... pero eso solo conducirá a un ciclo infinito :) ¡Disfruta!

Answer 2

Simplemente siembras las minas y luego atraviesas cada celda y cuentas las minas vecinas.

O establece cada contador a 0 y con cada mina con semilla, incrementa todos los contadores de celdas vecinas.

Answer 3

Si desea colocar m minas en N cuadrados, y tiene acceso a un generador de números aleatorios, simplemente caminar a través de los cuadrados restantes y para cada cálculo cuadrado (# minas restantes)/(# plazas restantes) y lugar una mina si su número aleatorio es igual o inferior a ese valor.

Ahora, si usted quiere etiquetar cada cuadrado con el número de minas adyacentes, sólo puede hacerlo directamente:

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 
) 

o si lo prefiere, puede comenzar con una serie de ceros y de incrementar cada por uno en el cuadrado 3x3 que tiene una mina en el centro. (No hace daño numerar los cuadrados con minas.)

Esto produce un juego de buscaminas totalmente aleatorio y correctamente anotado. Sin embargo, algunos juegos aleatorios pueden no ser juegos divertidos; seleccionar juegos aleatorios pero divertidos es una tarea mucho más desafiante.