Rompecabezas de las ocho reinas
El rompecabezas de las ocho reinas es el problema de colocar ocho reinas de ajedrez en un tablero de ajedrez de 8 × 8 de modo que no haya dos reinas que se amenacen entre sí; por lo tanto, una solución requiere que no haya dos reinas que compartan la misma fila, columna o diagonal. El rompecabezas de las ocho reinas es un ejemplo del problema más general de n reinas de colocar n reinas que no atacan en un tablero de ajedrez n × n , para el cual existen soluciones para todos los números naturales n con la excepción de n = 2 y n = 3. [ 1]
El compositor de ajedrez Max Bezzel publicó el rompecabezas de las ocho reinas en 1848. Franz Nauck publicó las primeras soluciones en 1850. [2] Nauck también extendió el rompecabezas al problema de las n reinas, con n reinas en un tablero de ajedrez de n × n cuadrados.
Desde entonces, muchos matemáticos , incluido Carl Friedrich Gauss , han trabajado tanto en el rompecabezas de las ocho reinas como en su versión generalizada de n -reinas. En 1874, S. Gunther propuso un método que utiliza determinantes para encontrar soluciones. [2] JWL Glaisher refinó el enfoque de Gunther.
En 1972, Edsger Dijkstra utilizó este problema para ilustrar el poder de lo que llamó programación estructurada . Publicó una descripción muy detallada de un algoritmo de retroceso de profundidad primero . 2
El problema de encontrar todas las soluciones al problema de las 8 reinas puede ser muy costoso desde el punto de vista computacional, ya que hay 4 426 165 368 (es decir, 64 C 8 ) arreglos posibles de ocho reinas en un tablero de 8×8, pero solo 92 soluciones. Es posible usar atajos que reducen los requisitos computacionales o reglas generales que evitan las técnicas computacionales de fuerza bruta . Por ejemplo, al aplicar una regla simple que restringe cada reina a una sola columna (o fila), aunque aún se considera fuerza bruta, es posible reducir el número de posibilidades a 16 777 216 (es decir, 8 8 ) combinaciones posibles. La generación de permutaciones reduce aún más las posibilidades a solo 40 320 (es decir, ¡8!), que luego se verifican en busca de ataques diagonales.
El rompecabezas de las ocho reinas tiene 92 soluciones distintas. Si las soluciones que difieren solo por las operaciones de simetría de rotación y reflexión del tablero se cuentan como una, el rompecabezas tiene 12 soluciones. Estas se llaman soluciones fundamentales ; Los representantes de cada uno se muestran a continuación.
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
La única solución simétrica al rompecabezas de las ocho reinas (
hasta la rotación y la reflexión)
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 1
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 2
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 3
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 4
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 5
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 6
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 7
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 8
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 9
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 10
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 11
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución 12
| a | B | C | D | mi | F | gramo | h | |
| 8 | | 8 |
| 7 | 7 |
| 6 | 6 |
| 5 | 5 |
| 4 | 4 |
| 3 | 3 |
| 2 | 2 |
| 1 | 1 |
| a | B | C | D | mi | F | gramo | h | |
Solución de escalera para 8 reinas
| a | B | C | D | mi | F | gramo | h | I | j | | |
| 10 | | | | | | | | | | | 10 |
| 9 | | | | | | | | | | | 9 |
| 8 | | | | | | | | | | | 8 |
| 7 | | | | | | | | | | | 7 |
| 6 | | | | | | | | | | | 6 |
| 5 | | | | | | | | | | | 5 |
| 4 | | | | | | | | | | | 4 |
| 3 | | | | | | | | | | | 3 |
| 2 | | | | | | | | | | | 2 |
| 1 | | | | | | | | | | | 1 |
| a | B | C | D | mi | F | gramo | h | I | j | | |
Solución de escalera para 10 reinas
solución min-conflicts a 8 reinas
