1 .
Complementos
2 .
Enlaces
3 .
Apéndice: Documentación del Diseñador de Buscaminas
4 .
Historia de revisiones de esta página
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.
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.
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.
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.
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.
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.
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
inforecre@wanadoo.es. 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
inforecre@wanadoo.es.
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.
Artículos
