Reinas

El problema fue originalmente propuesto en 1848 por el ajedrecista Max Bezzel, y durante los años, muchos matemáticos, incluyendo a Gauss y a Georg Cantor, han trabajado en este problema y lo hangeneralizado 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 propusoun 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ónestructurada. É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 puede amenazar a todas las reinas que estén en la misma fila, cada una ha de situarse en una fila diferente. Podemos representar las 8reinas 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.
Ejemplo de dosreinas amenazadas en el tablero de 4 por 4.

El vector (3,1,6,2,8,6,4,7) significa que la reina 1 esta en la columna 3, fila1; la reina 2 en la columna 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 unapermutació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 las posiciones sobre una misma diagonal descendente secumple que tienen el mismo valor fila-columna, mientras que para las posiciones en la misma diagonal ascendente se cumple que tienen el mismo valor fila+columna. Así, si tenemos dos reinas colocadas en...