Buscaminas - Posibilidad de ganar de un clic

Question

Me gustaría saber si es posible calcular las probabilidades de ganar un juego de Buscaminas (en dificultad fácil) de un solo clic. Esta página documenta un error que ocurre si lo haces, y calculan las probabilidades en alrededor de 1 entre 800,000. Sin embargo, esto se basa en la versión anterior de Buscaminas, que tenía un número fijo de tableros preestablecidos, por lo que no era posible cada disposición de minas. (Además, el tamaño del tablero en la versión actual es de 9x9, mientras que el antiguo era de 8x8. Ignoremos por ahora los niveles intermedio y experto - asumo que esas probabilidades son casi imposibles, aunque una solución generalizada que pudiera resolver para cualquier W×H y número de minas sería genial también, pero supondría mucho más trabajo, creo.) En general, el aumento del tamaño del tablero (con el mismo número de minas), así como la eliminación de los tableros preestablecidos probablemente harían que tal evento fuera mucho más común.

Entonces, asumiendo un tablero de 9x9 con 10 minas, y asumiendo que cada disposición posible de minas es igualmente probable (no es cierto dado la naturaleza pseudoaleatoria de los generadores de números aleatorios de computadora, pero finjamos), y sabiendo que el primer clic siempre es seguro (asuma que el comportamiento descrito en ese sitio aún se mantiene - si haces clic en una mina en el primer clic, se mueve al primer espacio disponible en la esquina superior izquierda), primero deberíamos calcular el número de tableros que se pueden resolver de un solo clic. Es decir, tableros con solo una apertura, y sin casillas numeradas que no estén adyacentes a esa apertura. El número total de tableros es lo suficientemente fácil: $\frac{(W×H)!}{((W×H)-M)! ×M!}$ o $\frac{81!}{71!×10!} \approx 1.878×10^{12}$. (Más complicado es averiguar qué tableros no se pueden resolver de un solo clic a menos que hagas clic en una mina y la muevas. Quizás podamos ignorar la regla del primer clic seguro si complica demasiado las cosas.) Las disposiciones válidas tendrían las 10 minas en los bordes lo suficientemente alejadas unas de otras para evitar crear números que no toquen la apertura. Luego es simplemente cuestión de contar cuántos espacios sin numeración existen en cada tablero y dividirlos por 81.

¿Es este un cálculo que razonablemente se puede representar en una fórmula matemática? ¿O tendría más sentido escribir un programa para probar cada configuración posible del tablero? (Desafortunadamente, los números con los que estamos tratando se acercan mucho al valor máximo almacenable en un entero de 64 bits, por lo que aquí es muy probable un desbordamiento. Por ejemplo, la calculadora predeterminada de Windows arruina por completo el número a menos que lo multipliques manualmente de 81 hasta 72.)

Answer 1

Debemos ignorar la regla de "no se puede perder en el primer clic", ya que complica severamente las cosas.

En esta respuesta, usaré una notación similar a la FEN del ajedrez (Notación Forsyth-Edwards) para describir tableros de buscaminas. m es una mina y los espacios vacíos se indican con números. Comenzamos en la parte superior del tablero y nos movemos de izquierda a derecha, volviendo a la izquierda al final de cada fila. Para describir un cuadro específico, las columnas se numeran de a a h, de izquierda a derecha, y las filas se numeran de 8 a 1, de arriba abajo.

En un tablero de buscaminas, todas las minas están adyacentes a cuadros numerados que indican cuántas minas hay al lado de ellos (incluyendo en diagonal). Si hay un cuadro numerado rodeado solo por minas y otros cuadros numerados, los nuevos cuadros dejarán de revelarse en ese cuadro. Por lo tanto, la pregunta es realmente:

¿Cuántos tableros de buscaminas de 9 x 9 con 10 minas existen de modo que cada cuadro en blanco adyacente a una mina toque un cuadro que no es una mina ni está adyacente a una?

Me gusta abordar problemas como estos colocando minas una por una. Hay 81 cuadros para colocar la primera mina. Si la colocamos en una esquina, por ejemplo, a1, entonces los tres cuadros diagonales adyacentes a la esquina (en este caso a3, b2 y c1) ya no son válidos (ahora a2 o b1 está "atrapado"). Si la colocamos en cualquier cuadro de borde excepto los ocho cuadros adyacentes a las esquinas, los cuadros a dos espacios horizontales o verticales se vuelven inválidos. En cuadros de borde adyacentes a las esquinas (por ejemplo, b1) también se vuelven indisponibles tres cuadros. En cuadros centrales, ya sea 4 o 3 cuadros se vuelven inaccesibles.

El problema es que los cuadros inválidos se pueden corregir en cualquier momento. Por ejemplo, colocar minas primero en a1 y luego en c1 puede ser inicialmente inválido, pero una mina en b1 soluciona eso.

Esta es mi análisis preliminar. Concluyo que no hay forma de calcular este número de tableros sin fuerza bruta. Sin embargo, cualquier persona con suficiente karma es bienvenida a mejorar esta respuesta.

Answer 2

Primero pido disculpas por mi mal inglés.

Una regla simple para usar y detectar un grado de un solo clic es: "si cada número tiene una celda 0 (o celda vacía) adyacente a él, entonces, el grado es de un solo clic." Esa regla fue fácil de comprender entendiendo cómo funcionan las aperturas automáticas de una celda. si la celda abierta es un 0, entonces abre todas las celdas adyacentes.

Esta regla es muy buena para el algoritmo de fuerza bruta para determinar los casos favorables.

Además, intenté encontrar los patrones que evitan que se produzca una victoria de un solo clic en un intento de contar la cantidad de grados posibles que no se pueden ganar con un solo clic. si ignoras las paredes, es simple, solo hay dos que engloban a todos los demás: B N B y B N N B (B para bomba, N para no bomba.) Estas celdas N quedan atrapadas porque tienen solo bombas o números adyacentes a ellas y este tipo de grados no pueden ser de un solo clic, como dice la regla.

Hay casos en los que las bombas forman grupos de celdas no abribles también, sin necesariamente usar esas etiquetas.

Pero con paredes, cosas como trampas de no-bombas en las esquinas y líneas de bombas cruzando el tablero hacen las cosas mucho más difíciles. Estos casos no necesariamente necesitan usar patrones BNB o BNNB porque la pared actúa como un bloque a la apertura de celdas vacías en la cadena de dominó. Así que me detuve ahí.

Incluso si pudiéramos descubrir todos los patrones incluyendo el factor de la pared, tendríamos otro problema contando las posibles combinaciones de patrones... así que creo que es muy difícil, virtualmente imposible sin una computadora para contar esta cantidad de grados.

Esa es mi contribución. Espero que pueda ser útil