El problema de las ocho reinas es un puzzel en el que se colocan ocho reinas sin que se amenacen.
Fue planteado por el ajedrecista alemán Max Bezzel en 1848.
En el juego del ajedrez la reina amenaza 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).
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".
oluciones al problema de las ocho reinas
El problema de las ocho reinas tiene 92 soluciones, de las cuales 12 son esencialmente distintas, es decir las 92 soluciones existentes se pueden obtener a partir de simetrías, rotaciones y traslaciones de las 12 soluciones únicas, que se muestran a continuación:
En la siguiente lista la columnas están numeradas de 1 a 8 y las filas nombradas con las letras de la a la h:
Esta animación utiliza backtracking para resolver el problema. Una reina se coloca en una columna que no será causa un conflicto. Si el programa encuentra un conflicto vuelve al estado del último buen movimiento y luego lo volverá a intentar en una columna diferente.
La siguiente tabla muestra el número de soluciones para la colocación de n reinas en un tablero n × n, a la vez único y distinto.
Tenga en cuenta que el rompecabezas seis reinas tiene menos soluciones que el rompecabezas cinco reinas.
Actualmente no existe una fórmula conocida para el número exacto de soluciones.
Fuentes:
No hay comentarios:
Publicar un comentario