Problema de las ocho reinas

Movimientos posibles de una reina en un tablero de 4×4.
Chess zhor 26.png
Chess zver 26.pnga8 __b8 __c8 __d8 qle8 __f8 __g8 __h8 __Chess zver 26.png
a7 __b7 __c7 __d7 __e7 __f7 __g7 qlh7 __
a6 __b6 __c6 qld6 __e6 __f6 __g6 __h6 __
a5 __b5 __c5 __d5 __e5 __f5 __g5 __h5 ql
a4 __b4 qlc4 __d4 __e4 __f4 __g4 __h4 __
a3 __b3 __c3 __d3 __e3 qlf3 __g3 __h3 __
a2 qlb2 __c2 __d2 __e2 __f2 __g2 __h2 __
a1 __b1 __c1 __d1 __e1 __f1 qlg1 __h1 __
Chess zhor 26.png
Una posible solución entre las 92 posibles soluciones en un tablero de 8×8.

El problema de las ocho reinas es un pasatiempo que consiste en poner ocho reinas en el tablero de ajedrez sin que se amenacen. Fue propuesto por el ajedrecista alemán Max Bezzel en 1848[cita requerida]. 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 poner 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).

Historia

El problema fue originalmente propuesto en 1848 por el ajedrecista Max Bezzel. Durante años, muchos matemáticos, incluyendo a Gauss y a Georg Cantor, han trabajado en él 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. Publicó una descripción muy 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".

Other Languages