El Buscaminas se conoce como el jueguecito que traía el ordenador, pero también ha dado que hablar en la investigación matemática e informática. La palabra clave es «NP-completo».

El Buscaminas es NP-completo

Hacia el año 2000, el matemático Richard Kaye mostró, según se cuenta, que el siguiente problema del Buscaminas pertenece a la familia de los problemas difíciles llamados «NP-completos».

Dado un tablero con números, ¿existe al menos una forma de colocar las minas que no contradiga esos números?

La pregunta que nos hacemos al jugar, «¿esta casilla es segura?», está muy ligada a este problema.

Qué es NP-completo

Dicho de forma sencilla, un problema NP-completo tiene estas características.

  • Comprobar si una respuesta es correcta es fácil: si te enseñan una forma de colocar las minas, se comprueba enseguida si encaja con todos los números.
  • Encontrar la respuesta es difícil (eso se cree): cuando el tablero crece, el número de posibilidades se dispara. Hasta ahora no se conoce ningún método que encuentre rápido la respuesta para cualquier tablero.

Además, se sabe que los problemas NP-completos se pueden convertir unos en otros. Si se encontrara un método que resolviera rápido uno solo de ellos en todos los casos, todos los demás problemas NP-completos también se resolverían rápido. Saber si existe ese método rápido es la famosa conjetura P≠NP, un problema aún sin resolver que figura entre los que tienen un premio de un millón de dólares.

El número de colocaciones crece enseguida

Comprobar las colocaciones es difícil porque el número de posibilidades se hace enorme.

  • Las formas de colocar 8 minas en un tablero de 9×7 son las combinaciones de elegir 8 casillas entre 63: unos 3900 millones.
  • Las formas de colocar 75 minas en un tablero de 26×15 son las combinaciones de elegir 75 casillas entre 390: un número de más de 80 cifras.

Claro que, al jugar, no hace falta revisarlas todas. Las casillas que no tocan ningún número se pueden pensar en bloque, y muchas situaciones se deciden mirando solo uno o dos números. Aun así, cuando los números se enredan entre sí, a veces cuesta llegar a una respuesta segura.

La app elige solo tableros que una persona puede resolver razonando

Al crear un tablero, la app «Buscaminas» comprueba si se puede resolver de principio a fin usando solo estas 3 reglas, las que usa una persona.

  1. Lo que se deduce de un solo número
  2. Lo que se deduce combinando dos números
  3. Lo que se deduce del número de minas que quedan en todo el tablero

Las tres reglas miran una zona pequeña y se comprueban deprisa. Si un tablero no se resuelve con ellas, se mueven las minas y se vuelve a crear. Así, quien juega siempre puede llegar hasta el final sin recurrir a un razonamiento pesado que revise todas las colocaciones.

Los tableros para jugar dentro de los artículos de esta web se crean con la misma idea. Al medir el tiempo de crear en un ordenador un tablero del tamaño de ★5, salió una media de unos pocos milisegundos por tablero.

Rompecabezas y matemáticas

Se sabe que muchos otros rompecabezas de lápiz, como el sudoku, también son NP-completos en su forma general con tableros más grandes. Muchos rompecabezas que una persona resuelve con gusto están hechos de modo que se pueden resolver con lógica, sin revisarlo todo. Los tableros sin adivinanzas de la app «Buscaminas» son uno de ellos.

El cálculo de probabilidades se explica en Las probabilidades en el Buscaminas.