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. Hay 92 soluciones. El problema se planteó por primera vez a mediados del siglo XIX. En la era moderna, a menudo se usa como un problema de ejemplo para varias técnicas de programación de computadoras .
El rompecabezas de las ocho reinas es un caso especial del problema más general de n reinas de colocar n reinas que no atacan en un tablero de ajedrez n × n . Existen soluciones para todos los números naturales n con la excepción de n = 2 y n = 3. Aunque el número exacto de soluciones solo se conoce para n ≤ 27, la tasa de crecimiento asintótico del número de soluciones es (0.143 n ) n .
El compositor de ajedrez Max Bezzel publicó el rompecabezas de las ocho reinas en 1848. Franz Nauck publicó las primeras soluciones en 1850. [1] 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. [1] 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 bastante costoso desde el punto de vista computacional, ya que hay 4 426 165 368 arreglos posibles de ocho reinas en un tablero de 8 × 8, [a] 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 elige una reina de cada columna, 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 pueden verificar para detectar ataques diagonales.
| 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
