Buscaminas y circuitos lógicos

Cortesía de El Rincón del programador.

Hay poca gente que no haya oído hablar del Buscaminas, ese juego disponible en la mayoría de ordenadores personales. Es un juego que engancha con facilidad, quizá porque una vez se le coge el truco, la forma de jugar es bastante mecánica, excepto en ciertas situaciones clave que requieren mayor atención.

Aquí solo daremos un resumen de las reglas; aquellos que no las conozcan pero estén interesados pueden probar a jugar unas partidas hasta entender el desarrollo. Sobre un encasillado hay ocultas cierta cantidad de minas. Inicialmente todas las celdas del encasillado están cubiertas. Podemos destapar cada celda; si oculta una mina, perderemos el juego inmediatamente, y si no, la celda destapada nos indicará cuántas minas hay en las casillas adyacentes a ésa (contando las diagonales). Si de una celda tenemos la certeza de que contiene una mina, podemos marcarla para facilitar la búsqueda. Ganaremos el juego si destapamos todas las celdas que no contienen minas.

A pesar de lo mecánico que resulta el desarrollo normal del juego, existen numerosas situaciones en las que es sencillamente imposible saber cómo continuar. Hay otras en las que salir del apuro resulta ciertamente difícil, hecho que da pie a acertijos como el que vemos en la figura 1, problema cuyo autor es Richard W. Kaye. Las celdas que aparecen destapadas pero vacías indican que no hay minas alrededor, como es obvio en este caso; se prefiere este convenio en lugar de colocar un cero en su interior para evitar desviar la atención de las zonas irrelevantes.

Figura 1: Problema de buscaminas. ¿Dónde están las minas ocultas?

Pero el interés de Kaye por el Buscaminas no es meramente lúdico. Es el autor de un artículo técnico, no disponible en nuestro país, que demuestra lo difícil que puede llegar a ser averiguar si existe o no una mina en cierta posición. Para enfocar el problema, Kaye lo ha planteado desde el punto de vista de la consistencia, y no del simple juego: ¿es un determinado tablero consistente, o no lo es? Para entendernos mejor vamos a definir primero el término. Un tablero será consistente si existe una distribución de minas ocultas tal que los números que hay en las celdas descubiertas sean correctos; será inconsistente en caso contrario. La figura 2 muestra ejemplos de posiciones consistentes e inconsistentes.

Figura 2a: Posición consistente.
Figura 2a: Posición inconsistente.

En la figura 2a, si la celda oculta de la izquierda contiene una mina y la de la derecha no la contiene, está claro que los números en las celdas descubiertas dirán la verdad. Aunque en cualquier otro caso los números no serían coherentes, existe aquí una combinación concreta de presencia y ausencia de minas en las celdas ocultas que satisface todos los números simultáneamente; el hecho de que exista es lo que hace que la posición sea consistente. No es éste el caso de la figura 2b; cualquier combinación posible de presencia o ausencia de minas en las celdas ocultas implicará que al menos uno de los números de las celdas descubiertas sea falso (recordemos que se asume implícitamente que las celdas descubiertas vacías contienen ceros, y por tanto también están sujetas a escrutinio).

Es fácil entender la relación entre el problema de la consistencia y el desarrollo del juego: los programas de jugar al buscaminas conocen las ubicaciones de las minas y nos muestran valores que corresponden a ellas, es decir, siempre son consistentes; por otro lado, para analizar la consistencia hay situaciones en las que es necesario evaluar la práctica totalidad del tablero, pues basta que una celda no sea consistente para que no lo sea el tablero. Para dar una solución positiva al problema de la consistencia hay que proporcionar una disposición de celdas ocultas marcadas de manera que contando las celdas marcadas como minas y las no marcadas como no minas, todos los números se satisfagan. Esta parte es muy parecida al desarrollo normal del juego, excepto que en situaciones ambiguas no nos importa si hay o no una mina mientras podamos dar una colocación correcta. Comprobar la solución es fácil: basta con contar, para cada celda descubierta, las celdas marcadas que tiene alrededor. Si encontramos una cuyo número no coincide con el número de esa celda descubierta, rechazamos la solución como incorrecta; el tablero entonces puede ser inconsistente. ¿Lo es? ¿Cuán difícil es determinar si lo es?

Lo que Kaye ha demostrado es que la tarea de averiguar si un tablero es consistente o no, en el caso general, es un problema cuya dificultad es como mínimo la misma que en la familia de problemas llamados NP-completos. No es fácil expresar el significado de esto de forma breve. Para hacernos una idea aproximada, decir que un problema es NP-completo implica que si existe un algoritmo que lo resuelve, su tiempo de ejecución es una función que crece con respecto al tamaño del problema (el del tablero en el caso del Buscaminas) a un ritmo mayor que el de cualquier función polinómica, por ejemplo, en proporción exponencial. En realidad esto no está demostrado; si alguien descubre que no es así, o bien descubre que no tiene más remedio que ser así, podría ganar un millón de dólares. Esta conjetura se conoce abreviadamente como «P=NP?».

La demostración de Kaye se basa en una equivalencia sorprendente, que él mismo desarrolló: es posible construir tableros de buscaminas isomorfos (equivalentes) a funciones booleanas con entradas arbitrarias y de cuya salida dependa la cuestión de si el tablero es o no consistente. Éste es un problema de satisfactibilidad (abreviado SAT) del que se sabe que es NP-completo; por tanto el problema general de la consistencia del buscaminas también lo es.

Para su demostración Kaye elabora configuraciones de buscaminas que equivalen a elementos usados en la elaboración de circuitos lógicos. Construye las entradas lógicas, cables capaces de doblar esquinas, y por supuesto las puertas lógicas. Vemos en la figura 3 lo que sería una entrada lógica; hemos marcado con banderines las casillas que a priori tienen que ser minas para que la configuración sea consistente. El valor que se le dé a x (presencia o ausencia de mina) determinará el valor del resto de casillas cubiertas a la hora de mantener la consistencia. El «hilo conductor» tiene la forma de pares de casillas ocultas como los que se ven en la figura, y la señal se propaga en la dirección de la flecha.

Figura 3: Entrada lógica e hilo conductor.

Analizando la figura, queda claro que por cada par de casillas adyacentes no descubiertas, en una tiene que haber mina y en la otra no; además, la posición relativa de la que contiene la mina será siempre la misma, y dependerá de x. Por convenio, si de cada pareja de casillas adyacentes del «cable» la que tiene la mina es la posterior en el sentido de la flecha (las marcadas con * en la ilustración) diremos que el cable porta un «1 lógico»; de lo contrario será un «0 lógico». Según este convenio, un circuito inversor puede tomar la forma que vemos en la figura 4, que cambia el estado de los ceros y los unos.

Figura 4: Elemento inversor.

La puerta OR (figura 5), diseñada por Stefan Schwoon, es bastante compleja; sin embargo es fundamental, pues con puertas OR e inversores es posible implementar cualquier función lógica. Este diseño simplifica el que utilizó Kaye en su demostración; la puerta universal que él construyó era la AND pero por su volumen la hemos considerado menos apropiada para exponerla aquí. Si el lector está interesado, puede encontrarla junto con otras puertas y elementos (por ejemplo, el que dobla una esquina) en un folleto que está disponible en la página de Buscaminas de Kaye. Algunas de las configuraciones que aparecen en ese folleto son necesarias para la prueba formal, que por supuesto cuida todos los detalles minuciosamente.

Figura 5: Puerta OR.

Pongamos todo esto en práctica con un ejemplo. Consideremos el tablero de la figura 6, correspondiente a la función lógica «NOT (x OR NOT y)». Debido al diseño de la salida, para que esta configuración sea consistente el resultado de la función tiene que ser un 1. ¿Qué valores han de recibir las entradas para que esta condición se cumpla? Esta es precisamente la pregunta del problema SAT. En este caso, existe una combinación de entradas que hace que la salida sea 1, y por tanto el tablero es consistente. Sin embargo, esta función es muy sencilla; para funciones complejas puede llegar a costar mucho tiempo (del orden de milenios, incluso) averiguar la respuesta con los algoritmos disponibles actualmente.

Figura 6: Problema de consistencia.

El lector puede disfrutar comprobando cómo, al darles a x e y los valores apropiados, efectivamente se obtiene una configuración legítima (y en este caso única), y que todos los demás valores posibles de x e y conducen a una contradicción en los datos de las celdas numéricas. Las soluciones tanto de este problema como del propuesto en la figura 1 pueden ser comprobadas mediante mi programa Diseñador de Buscaminas.

Complementos

La elaboración de mi programa Diseñador de Buscaminas me ha permitido comprobar la validez de los circuitos aquí expuestos. También me ha ayudado a comprobar que el diseño de la puerta OR de Stefan Schwoon tiene un defecto un tanto sutil. Hay exactamente una casilla marcada como mina que no es deducible a partir de los datos de que se dispone. ¿Sabría el lector corregir el diseño de Schwoon para que no tenga ese defecto? Las respuestas, como siempre, a [email protected]. Publicaré las mejores que reciba en próximos artículos.

Después de publicar este artículo he descubierto que las demostraciones para probar la dificultad (en sentido técnico) de ciertos juegos son bastante populares incluso desde antes de la aparición del artículo de Kaye. Por ejemplo, el propio Schwoon, en un trabajo conjunto con Markus Holzer, ha demostrado que el juego Atomix es todavía más difícil que el Buscaminas, ya que pertenece a la clase de problemas denominados PSPACE-completos. No entraremos en detalles sobre lo que eso significa ya que excede los propósitos de este artículo; hay buenos libros sobre teoría de la complejidad donde se puede aprender el significado de este y otros términos. Baste decir que los problemas NP-completos están englobados dentro de los PSPACE-completos, lo cual parece significar que el Atomix es más difícil que el Buscaminas; sin embargo vale la pena recordar a este punto que la prueba de Kaye dice que el Buscaminas es como mínimo NP-completo.

Joseph C. Culberson ha demostrado también que el Sokoban, un juego de empujar bloques, es PSPACE-completo. Lo ha hecho construyendo una máquina de Turing que utiliza construcciones de Sokoban diseñadas al efecto. En 1978 David Lichtenstein y Michael Sipser probaron que el Go, un juego de tablero de origen oriental, tiene dificultad PSPACE al jugarlo con tableros de tamaño arbitrario.

Usando métodos parecidos a los de Kaye (nos referimos a la construcción de elementos lógicos circuitales), Erich Friedman, profesor de matemáticas de la universidad de Stetson, ha demostrado que un juego de bloques llamado Cubic (más conocido por una versión comercializada con el nombre de Puzznic) también pertenece a la clase de los NP-completos. Friedman también ha dado una prueba del mismo tipo para otro juego llamado Spiral Galaxies, un juego que se puede jugar con lápiz y papel. También ha demostrado la complejidad NP-completa de un juego que se llama Pearl Puzzles, aunque en este caso por metodos completamente distintos de los de Kaye: utilizando ciertos resultados de la teoría de grafos. Por métodos aún más complicados, Erik D. Demaine, junto con otros autores, demuestran lo mismo del conocido Tetris y también de un juego muy adictivo llamado Clickomania!, conocido también por el nombre de Same Game, del cual hay una versión llamada Click co-escrita por la webmaster del Rincón del Programador y un servidor.

Holzer ya había demostrado que un juego llamado TANTRIX, en su versión de puzzle, es NP-completo por el método de Kaye. Mediante una construcción parecida aunque más potente, Gary W. Flake y Eric B. Baum demuestran que un juego de bloques deslizantes llamado Rush Hour, de Binary Arts, que casualmente poseo, es PSPACE-completo en su versión de tamaño indefinido. Demaine, en un trabajo conjunto con Robert A. Hearn, ha dado una demostración alternativa más simple. También simplifica la de Culberson sobre el Sokoban mediante la construcción de elementos lógicos al estilo de los de Flake y Baum.

Otros juegos que tengo noticia de que se han probado difíciles son: Damas, Othello, Mastermind, Dots and Boxes (conocido en España como los cuadritos), Shanghai (también conocido como el Solitario del Mahjongg), PushPush y algunas variantes, Gravity, Instant Insanity, Twixt y Corral Puzzles.

Enlaces

Sobre Buscaminas y circuitos lógicos

Diseñador de Buscaminas, escrito por el autor de este artículo (124.973 bytes). La documentación está en un apéndice. Disponible para descarga en la siguiente dirección:
http://perso.wanadoo.es/p.gimeno/files/MineDsgn.zip

Página de Buscaminas de Richard W. Kaye:
http://www.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm

Un artículo de Ian Stewart sobre el trabajo de Kaye:
http://www.claymath.org/Popular_Lectures/Minesweeper/

Un programa en Java (con fuente) para resolver tableros de Buscaminas automáticamente, aunque no siempre con éxito. Su autor invita a otros programadores a implementar su estrategia en Java.
http://www.ccs.neu.edu/home/ramsdell/pgms/

Sobre otros juegos de los que se ha probado la dificultad

Una página de David Eppstein sobre la complejidad de algunos juegos:
http://www.ics.uci.edu/~eppstein/cgt/hard.html

En la página de Stefan Schwoon está disponible el artículo sobre el Atomix.
http://wwwbrauer.in.tum.de/~schwoon/

Directorio de artículos técnicos, con multitud de ellos en formato PDF y PostScript. Contiene gran parte de la bibliografía utilizada para escribir el apartado de complementos.
http://citeseer.nj.nec.com/cs
Contiene, entre otros muchos:
Sokoban is PSPACE-complete (Joseph C. Culberson)
Spiral Galaxies Puzzles are NP-complete (Erich Friedman)
Pearl Puzzles are NP-complete (Erich Friedman)
Corral Puzzles are NP-complete (Erich Friedman)
Pushing Blocks in Gravity is NP-hard (Erich Friedman)
The Game of Cubic is NP-complete (Erich Friedman)
PushPush and Push-1 are NP-hard in 2D (Erik D. Demaine, Joseph O'Rourke)
PushPush is NP-hard in 3D (Joseph O'Rourke)

En la página de Erik D. Demaine sobre juegos combinatorios hay varios artículos utilizados como bibliografía sobre Tetris, Clickomania, Phutball, Sliding Blocks (Rush Hour, Sokoban), etc.
http://theory.lcs.mit.edu/~edemaine/games/

Las páginas personales de los autores cuyo enlace está disponible en el texto también contienen en muchos casos los artículos publicados por ellos.

Juegos mencionados en el texto, disponibles en línea

Página dedicada al Buscaminas como juego. Entre las descargas hay varios programas para jugar al Buscaminas, algunos de ellos con encasillados diferentes del estándar cuadriculado (hexagonal, por ejemplo).
http://metanoodle.com/minesweeper/

Aquí encontraremos una versión en Java del Buscaminas con la cual podremos jugar en línea:
http://www.hut.fi/~mantell/Minesweeper.html

Si la versión Java no sirviera, desde la página del siguiente enlace podremos jugar en línea con cualquier navegador, aunque de una forma un poco engorrosa:
http://www.linc.or.jp/~hamano/game/minesweeper.html

Página sobre puzzles de bloques deslizantes. La mayoría de ellos son jugables mediante Java. Está entre otros el Rush Hour mencionado en el texto.
http://www.puzzleworld.org/SlidingBlockPuzzles/default.htm

Otra página con un juego tipo Rush Hour en Java:
http://www.rhymezone.com/games/bb/

El juego del Cubic es parecido al Puzznic pero carece de bloques móviles.
http://www.agon.com/four.html

El juego del Click escrito por Lola Cárdenas y Pedro Gimeno.
http://rinconprog.metropoliglobal.com/Programas/Juegos/Click.php

Un juego idéntico al Click se puede jugar en línea en la siguiente dirección (requiere Java y JavaScript):
http://www.clickomania.co.uk/

Aquellos que estén registrados en Yahoo! pueden jugar en línea contra otros jugadores al Go, Puntos y Rayas (Dots and Boxes, Cuadraditos), Othello, Damas, Shanghai (Mahjongg Solitaire) y muchos otros.
http://es.games.yahoo.com/

Sobre los problemas NP y el premio de un millón de dólares

Página de Stanislav Busygin sobre los problemas NP-completos.
http://www.busygin.dp.ua/npc.html

Página en español sobre el problema SAT.
http://www.mor.itesm.mx/~jfrausto/Algoritmos/pagina_sat/Sat.htm

Hay varias páginas en inglés dedicadas a algoritmos de resolución del problema SAT. Esta es una de ellas:
http://www.cs.duke.edu/~mlittman/topics/sat.html

Página sobre los premios ofrecidos por el Instituto Matemático Clay. Contiene una definición formal del problema «P=NP?».
http://www.claymath.org/Millennium_Prize_Problems/

Apéndice: Documentación del Diseñador de Buscaminas

La intención del programa es proporcionar una herramienta con la que diseñar y probar configuraciones de Buscaminas, principalmente con el propósito de poder ensayar las que se exponen en este artículo. Lamentablemente, sólo está disponible para Windows por el momento, aunque si recibo suficientes peticiones quizá escriba una versión para Linux.

La instalación es muy simple: basta con descomprimir el fichero MineDsgn.zip en la carpeta de nuestra elección. El fichero MineDsgn.lng debe estar en la misma carpeta que MineDsgn.exe puesto que contiene la traducción al español de todos los textos. El programa es gratuito, freeware y de libre distribución siempre y cuando lo que se distribuya sea el paquete completo.

La forma de uso es la siguiente. Al comenzar el programa se muestra un tablero vacío del último tamaño que hayamos usado. Actualmente tiene dos modos de funcionamiento: el modo Diseño, activo por defecto, y el modo Prueba.

Modo Diseño

En modo diseño podemos «pintar» sobre el tablero; para ello escogemos la herramienta en el panel superior y utilizamos el botón izquierdo del ratón para dibujar. No se nos permite crear configuraciones inconsistentes: en una casilla no podemos poner un número mayor que el número de casillas cubiertas totales que rodean a esa casilla, ni menor que el número de casillas marcadas como minas. Las celdas cubiertas tienen preferencia sobre las descubiertas, en el sentido de que si alteramos una celda cubierta que provoca un cambio en los números de las celdas descubiertas a su alrededor, las que se actualizarán para reflejarlo serán las descubiertas.

Un doble click con el botón izquierdo sobre una casilla hará que si estaba cubierta se sustituya por una celda descubierta (con el número mínimo posible como valor inicial), y si estaba descubierta se sustituya por una cubierta.

Con el botón derecho incrementamos el número en las celdas descubiertas, o si ya era el máximo pasará al mínimo. En el caso de las celdas cubiertas la cambiaremos entre marcada y sin marcar. Cuando se use el botón derecho de esta manera, se seleccionará como herramienta la correspondiente al tipo de celda en el que se convierte la actual, de manera que podemos seguir dibujando con este nuevo tipo.

Existe una opción, «Utilizar marcas (?)», que hace que al pulsar el botón derecho en una celda marcada como mina ésta pase a ser un interrogante en lugar de una en blanco. Las celdas cubiertas con interrogante se comportan de la misma manera que las celdas sin él; el interrogante es sólo un signo para destacar ciertas casillas a voluntad del diseñador.

La misma opción hará además que al pulsar con el botón derecho sobre una celda descubierta ésta haga el ciclo entre el menor posible y el mayor posible y a continuación un interrogante. Este interrogante podrá sustituir a cualquier número más adelante, cuando probemos el tablero.

Una regla a la hora de dibujar es que si empezamos a dibujar en celdas cubiertas, sólo podremos dibujar en celdas cubiertas hasta que soltemos el botón izquierdo del ratón y lo volvamos a pulsar; similarmente, cuando empezamos a dibujar en las celdas descubiertas sólo podremos dibujar en celdas descubiertas.

Las opciones «Abrir configuración», «Guardar configuración» y «Guardar como...» se comportan como es de esperar. La opción «Nuevo tablero» borrará el diseño actual y dejará preparado el tablero para nuevos diseños. Para cambiarle el tamaño se usa la opción «Redimensionar tablero», pero cuidado porque los cambios no son reversibles actualmente. El tamaño máximo en esta versión es 200×200.

Modo Prueba

En este modo iremos descubriendo celdas cubiertas pero no marcadas, de forma tal que se mantenga siempre la consistencia. Cada vez que se invoque se restaurará el tablero creado con el modo Diseño. El tablero resultante de la prueba no se puede grabar. Las celdas cubiertas con un interrogante se comportarán exactamente igual que las celdas sin él.

Con el botón izquierdo descubriremos una celda cubierta; si ésta tiene que ser forzosamente una mina de acuerdo con sus vecinas descubiertas, en vez de descubrirse se marcará como tal. Al descubrirla, dependiendo de las celdas que la rodeen se mostrará un número o un interrogante. Si todas las celdas cubiertas a su alrededor son marcas de mina, o simplemente no tiene celdas cubiertas alrededor, mostrará el número de celdas marcadas como minas; si hay alguna celda cubierta que no está marcada como mina alrededor de ésa, mostrará un interrogante, pues no se sabe todavía si tienen minas o no. Si al pulsar el botón la celda no se marca ni se descubre, será porque no puede ni ser una mina ni no serlo, de acuerdo con los números que tiene alrededor; es decir, se habrá alcanzado una posición inconsistente. Si la opción de sonido está seleccionada, al pulsar sonará además una campanilla avisándolo.

Haciendo doble click sobre una celda se restaurará el valor que tuviera en modo diseño.

Con el botón derecho se marcará una celda cubierta como mina, o bien se desmarcará si ya lo estaba. En caso de que la opción «Utilizar marcas (?)» esté activa, el ciclo será celda cubierta - celda marcada - celda cubierta con interrogante. El marcar una celda como mina puede tener como resultado que se actualicen los interrogantes descubiertos que tuviera alrededor. Si al intentar marcar una mina no se nos permite, será porque alguna de las celdas descubiertas que tiene alrededor ya tiene una cantidad de celdas marcadas que coincide con su número, y por tanto no podemos marcar ésta.

El botón central también es muy útil. Si el ratón no dispone de botón central, se pueden usar simultáneamente los botones izquierdo y derecho, en ese orden (para realizar pulsaciones repetidas se puede utilizar sólo el botón derecho sin soltar el izquierdo). La forma de usarlo es la siguiente: con el puntero del ratón apuntamos a una celda descubierta cuyo número coincide bien con el número de celdas cubiertas totales, bien con el número de celdas marcadas que rodean a ésa. Al pulsar con el botón central se marcarán o se descubrirán las que falten, según proceda. En otro caso no hará nada. Al igual que con el click izquierdo, es posible que una celda no pueda ni contener una mina ni no contenerla (inconsistencia), lo cual se nos avisará con una campanilla si está activo el sonido.

A pesar de lo complicado que puede sonar, el manejo es más sencillo de lo que parece. En caso de que alguien encuentre algún error ruego me lo comunique escribiendo a [email protected].

Historia de revisiones de esta página

  • 2003-01-22: Primera versión.
  • 2003-02-08: Modificado el párrafo que compara el juego con el problema de consistencia; añadido el apartado Complementos; añadido el programa Diseñador de Buscaminas y su documentación; pequeña reordenación de apartados; añadidos algunos enlaces; añadida versión en inglés.

COMPARTE ESTE ARTÍCULO

COMPARTIR EN FACEBOOK
COMPARTIR EN TWITTER
COMPARTIR EN LINKEDIN
COMPARTIR EN WHATSAPP