El problema de las ocho reinas
El problema de las ocho reinas pide colocar ocho reinas en un tablero de ajedrez sin que dos de ellas se ataquen. El compositor de problemas de ajedrez Max Bezzel lo publicó en 1848, y se ha convertido en el primer ejemplo clásico de búsqueda con vuelta atrás (backtracking).
Un problema de ajedrez de 1848
Max Bezzel, un compositor alemán de problemas de ajedrez, planteó el problema en una revista de ajedrez de Berlín en 1848. Franz Nauck publicó las 92 soluciones en 1850 y planteó la misma pregunta para tableros más grandes. Carl Friedrich Gauss siguió el problema con interés y lo comentó en sus cartas.
Una reina por fila y columna
Ocho reinas que no se atacan entre sí deben estar en ocho filas distintas y ocho columnas distintas. Así que una solución es una reordenación de los números del 1 al 8, una permutación, con una regla más: dos reinas no pueden compartir una diagonal. De las 40.320 permutaciones, solo 92 superan la prueba.
La vuelta atrás
La vuelta atrás construye una solución pieza a pieza y retrocede en cuanto llega a un callejón sin salida. Para las reinas: coloca una reina en la primera casilla segura de la fila siguiente y, cuando una fila no tenga ninguna casilla segura, vuelve a la fila de arriba y haz avanzar esa reina. En 1972, Edsger Dijkstra usó el problema para explicar la programación estructurada con exactamente esta búsqueda.
Simetría
Gira el tablero un cuarto de vuelta, o refléjalo, y una solución sigue siendo una solución. Eso da hasta ocho versiones de cada una. Las 92 soluciones se agrupan en 12 familias así: once con 8 miembros y una con solo 4, porque esa solución se ve igual tras media vuelta.
El problema de las n reinas
En un tablero de n×n la pregunta es la misma con n reinas. Hay soluciones para todo n a partir de 4, y su número crece rápido: 2 para 4×4, 92 para 8×8 y 14.200 para 12×12. No se conoce ninguna fórmula para el recuento; los valores récord vienen de grandes búsquedas por ordenador.
Pruébalo en PictorX
Abre Ocho reinas y haz clic en una casilla para colocar una reina; vuelve a hacer clic para quitarla. «Mostrar ataques» marca con un punto las casillas que atacan tus reinas, y las reinas en rojo se atacan entre sí. Resolver ejecuta la búsqueda con vuelta atrás paso a paso y mantiene las reinas que colocaste. Siguiente solución recorre todas las soluciones en orden, y Tamaño cambia el tablero de 4×4 a 12×12.
Preguntas frecuentes
¿Quién inventó el problema de las ocho reinas?
Max Bezzel, un compositor alemán de problemas de ajedrez, en 1848. Franz Nauck publicó la primera lista completa de soluciones en 1850.
¿Cuántas soluciones hay?
92 en el tablero estándar. Si las rotaciones y los reflejos cuentan como una sola, hay 12.
¿Por qué el tablero de 6×6 tiene tan pocas soluciones?
Solo tiene 4, todas de una misma familia. El tablero de 5×5, más pequeño, tiene 10. Los tableros más grandes tienen cada vez más: 40 en 7×7 y 92 en 8×8.
¿PictorX sube algo?
No. El tablero se dibuja en un lienzo en tu navegador. Guardar descarga un PNG, y Editar abre esa imagen en el editor de PictorX.
Herramientas relacionadas
Ocho reinas
Coloca ocho reinas en un tablero de ajedrez de modo que ninguna ataque a otra. Pruébalo tú mismo, mira cómo la búsqueda con vuelta atrás encuentra una solución paso a paso y recorre las 92 soluciones.
Recorrido del caballo
Haz saltar un caballo de ajedrez a cada casilla del tablero exactamente una vez. Juega tú mismo con las pistas de Warnsdorff, o mira cómo Resolver termina un recorrido abierto o cerrado. Guarda el trazado como PNG.
El recorrido del caballo
La historia y las matemáticas del recorrido del caballo: Euler y Warnsdorff, recorridos abiertos y cerrados, por qué los tableros de lado impar no tienen recorrido cerrado y cómo un ordenador encuentra uno.
Torre de Hanói
Mueve una torre de discos entre tres varillas en tu navegador. Un disco cada vez, nunca uno grande sobre uno pequeño. La solución más corta son 2ⁿ − 1 movimientos.
Torre de Hanói
La Torre de Hanói: tres varillas, un disco cada vez y nunca uno grande sobre uno pequeño. La solución más corta son 2ⁿ−1 movimientos. Édouard Lucas presentó el rompecabezas en 1883.
Hormiga de Langton
Ejecuta la hormiga de Langton en tu navegador. Observa la simetría, el caos y la autopista de 104 pasos, y luego prueba reglas de varios colores, varias hormigas, una cuadrícula hexagonal y turmitas.
¿Listo para probarlo?
Abra PictorX en su navegador: no requiere instalación ni tarjeta de crédito para comenzar.
Probar Ocho reinas