Apuntes

Problema de las ocho reinas

1

Problema de las ocho reinas

Movimientos posibles de una reina en un tablero de 4x4.

Una posible solución entre las 92 posibles soluciones en un tablero de 8x8 El problema de las ocho reinas es un pasatiempo en el que se colocan ocho reinas sin que se amenacen. Fue propuesto por el ajedrecista alemán Max Bezzel en 1848. En el juego del ajedrez la reinaamenaza a aquellas piezas que se encuentren en su misma fila, columna o diagonal. El juego de las 8 reinas consiste en colocar sobre un tablero de ajedrez ocho reinas sin que estas se amenacen entre ellas. Para resolver este problema emplearemos un esquema vuelta atrás (o Backtracking).

Problema de las ocho reinas

2

Historia
El problema fue originalmente propuesto en 1848 por elajedrecista Max Bezzel, y durante los años, muchos matemáticos, incluyendo a Gauss y a Georg Cantor, han trabajado en este problema y lo han generalizado a n-reinas. Las primeras soluciones fueron ofrecidas por Franz Nauck en 1850. Nauck también se abocó a las n-reinas (en un tablero de nxn de tamaño arbitrario). En 1874, S. Günther propuso un método para hallar las soluciones usando determinantes, y J.W.L.Glaisher redefinió su aproximación. Edsger Dijkstra usó este problema en 1972 para ilustrar el poder de la llamada programación estructurada. Él publicó una descripción altamente detallada del desarrollo del algoritmo de backtracking, "depth-first". Este acertijo apareció en el popular juego de computadora de los '90 llamado "The 7th Guest".

Planteamiento del Problema
Como cada reina puedeamenazar a todas las reinas que estén en la misma fila, cada una ha de situarse en una fila diferente. Podemos representar las 8 reinas mediante un vector[1-8], teniendo en cuenta que cada índice del vector representa una fila y el valor una columna. Así cada reina estaría en la posición (i, v[i]) para i = 1-8. El vector significa que la reina 1 esta en la

columna 3, fila1; la reina 2 en lacolumna 1, fila 2; la reina 3 en la columna 6, fila 3; la reina 4 en la columna 2, fila 4; etc... Como se puede apreciar esta solución es incorrecta ya que estarían la reina 3 y la 6 en la misma columna. Por tanto el vector correspondería a una permutación de los ocho primeros números enteros. El problema de las filas y columnas lo tenemos cubierto, ¿pero qué ocurre con las diagonales? Para lasposiciones sobre una misma diagonal descendente se cumple que tienen el mismo valor , mientras que para las posiciones en la misma
Ejemplo de dos reinas amenazadas en el tablero de 4 por 4.

diagonal ascendente se cumple que tienen el mismo valor . Así, si tenemos dos reinas colocadas en posiciones solo si cumple: y entonces están en la misma diagonal si y

o o Teniendo en cuenta todas estasconsideracioneas, podemos aplicar el esquema de retroactivamente para implementar las ocho reinas de una manera realmente eficiente. Para ello, reformulamos el problema como problema de búsqueda en un árbol. Decimos que en un vector de enteros entre 1 y 8 es -prometedor, para , si ninguna de las reinas colocadas en las posiciones amenaza a ninguna de las otras. Las soluciones a nuestro problema secorresponden con aquellos vectores que son 8-prometedores.

Problema de las ocho reinas

3

Establecimiento del algoritmo
Sea • • • el conjunto de vectores de es es -prometedores, , con , sea tal que el grafo dirigido tal que si y solo si existe un entero -prometedor -prometedor para todo . sus hojas son o bien soluciones ( ). Las soluciones del problema de las ocho reinas se pueden obtenerexplorando

Este grafo es un árbol. Su raíz es el vector vacío correspondiente a ), o posiciones sin salida (

este árbol. Sin embargo no generamos explícitamente el árbol para explorarlo después. Los nodos se van generando y abandonando en el transcurso de la exploración mediante un recorrido en profundidad. Hay que decidir si un vector es extensión de un vector -prometedor, sabiendo que es una...