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 para 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 las 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 en profundidad . 2
El problema de encontrar todas las soluciones al problema de las 8 reinas puede ser bastante costoso computacionalmente, ya que hay 4,426,165,368 (es decir, 64 C 8 ) posibles arreglos de ocho reinas en un tablero de 8 × 8, pero solo 92 soluciones. Es posible utilizar atajos que reduzcan los requisitos computacionales o reglas prácticas que eviten técnicas computacionales de fuerza bruta . Por ejemplo, al aplicar una regla simple que restringe a cada reina a una sola columna (o fila), aunque todavía 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 revisan para detectar 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. Estos se denominan 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 para el rompecabezas de las ocho reinas (
hasta rotación y 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 | |
Solucion 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 | |
Solucion 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 | |
Solucion 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 de min-conflictos a 8 reinas
