Problema de las ocho reinas

Movimientos posibles de una reina en un tablero de 4×4.
Chess zhor 26.png
Chess zver 26.png a8 __ b8 __ c8 __ d8 ql e8 __ f8 __ g8 __ h8 __ Chess zver 26.png
a7 __ b7 __ c7 __ d7 __ e7 __ f7 __ g7 ql h7 __
a6 __ b6 __ c6 ql d6 __ e6 __ f6 __ g6 __ h6 __
a5 __ b5 __ c5 __ d5 __ e5 __ f5 __ g5 __ h5 ql
a4 __ b4 ql c4 __ d4 __ e4 __ f4 __ g4 __ h4 __
a3 __ b3 __ c3 __ d3 __ e3 ql f3 __ g3 __ h3 __
a2 ql b2 __ c2 __ d2 __ e2 __ f2 __ g2 __ h2 __
a1 __ b1 __ c1 __ d1 __ e1 __ f1 ql g1 __ 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 en el que se ponen ocho reinas en el tablero 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