Modelo matemático para resolver situaciones de buscaminas

Question

Supongamos que hay un tablero de buscaminas como el siguiente:

1 1 1
A B C

Donde A, B, C es un cuadrado no revelado que podría contener una mina.

Esto se puede representar con:

A + B = 1
A + B + C = 1
B + C = 1

Lo que se puede resolver fácilmente para mostrar que B = 1

Ahora bien, espero estar en el stackexchange adecuado para esto ya que soy relativamente aficionado a las matemáticas, pero ¿existe algún algoritmo que pueda resolver este tipo de ecuaciones de forma relativamente rápida y sencilla?

Answer 1

El Buscaminas pertenece a la categoría de los problemas NP-completos (un tipo de problema combinatorio ubicuo pero intratable), y para las posiciones generales no se conoce ni se sospecha ningún método de solución que sea fundamentalmente mejor que la búsqueda por fuerza bruta. Las ecuaciones lineales que codifican una posición tienen variables enteras no negativas, o variables booleanas 0-1; definen instancias de Programación Entera y Satisfacción respectivamente. Estos también son problemas NP-completos bien conocidos. Por lo tanto, no se puede ganar nada codificando el problema de esta manera, excepto en los pequeños casos en los que se puede alimentar la posición a los solucionadores de SAT o de programas enteros.

http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

http://www.claymath.org/Popular_Lectures/Minesweeper/

(Respuesta añadida a la pregunta de los comentarios: )

¿Cómo se puede calcular el Buscaminas con escenarios como 1 1 A B (suponiendo que se trata de una isla)?

El buscaminas se suele formalizar como un problema de decisión: ¿es el escenario consistente con al menos una colocación de minas? Si este problema fuera eficientemente resoluble, entonces para cada casilla indeterminada S se podría probar eficientemente si Minado(S) o Vacío(S) es inconsistente con el escenario. Si Minado(S) es inconsistente, entonces S debe ser Vacío, y viceversa; si ambos son consistentes, entonces S es (actualmente) indeterminado. La iteración de este proceso sería un algoritmo para resolver eficientemente todas las casillas que están determinadas lógicamente por el escenario original. Dentro de los algoritmos de juego determinista esto es el juego perfecto.