El problema de las 8 reinas es uno de los problemas combinatorios más famosos y elegantes de la matemática recreativa. Planteado en 1848 con un tablero de ajedrez como escenario, ha fascinado a matemáticos, programadores y aficionados durante casi dos siglos y sigue siendo un clásico en la enseñanza de la algoritmia y la programación.
El enunciado del problema
La reina de ajedrez es la pieza más poderosa del tablero: puede moverse cualquier número de casillas en cualquier dirección (horizontal, vertical o diagonal). El problema plantea la siguiente pregunta:
¿Es posible colocar 8 reinas en un tablero de ajedrez estándar de 8×8 casillas de manera que ninguna de ellas amenace a ninguna otra?
Dicho de otro modo: ninguna reina puede estar en la misma fila, la misma columna ni la misma diagonal que cualquier otra reina del tablero.
Historia del problema
El problema fue publicado por primera vez en 1848 por el ajedrecista alemán Max Bezzel en una revista ajedrecística de Berlín. La simplicidad del enunciado y la dificultad de encontrar la respuesta llamaron rápidamente la atención de matemáticos prominentes.
El gran Carl Friedrich Gauss, considerado uno de los mejores matemáticos de la historia, dedicó tiempo al problema y encontró 76 de las 92 soluciones, aunque no llegó al total. Fue el matemático Franz Nauck quien encontró todas las 92 soluciones en 1850 y demostró que ese era el número completo.
Las 92 soluciones
El problema tiene exactamente 92 soluciones. Si se consideran las simetrías del tablero (rotaciones de 90°, 180° y 270°, y reflexiones horizontales y verticales), muchas soluciones son equivalentes entre sí. Eliminando estas simetrías, quedan 12 soluciones esencialmente distintas o fundamentales.
Generalización: el problema de las N reinas
El problema de las 8 reinas se puede generalizar a tableros de N×N casillas con N reinas. Para N=1, la solución es trivial (1 reina en el único tablero de 1 casilla). Para N=2 y N=3, no hay solución. Para N=4, hay 2 soluciones. El número de soluciones crece rápidamente con N:
| N | Soluciones |
|---|---|
| 4 | 2 |
| 5 | 10 |
| 6 | 4 |
| 7 | 40 |
| 8 | 92 |
| 9 | 352 |
| 10 | 724 |
Importancia en informática
El problema de las 8 reinas es un ejemplo clásico que se utiliza en la enseñanza de la programación para ilustrar técnicas como la búsqueda con retroceso (backtracking): el algoritmo coloca reinas una a una, y cuando detecta un conflicto, retrocede y prueba otra posición. Esta técnica es directamente aplicable a una enorme variedad de problemas de optimización combinatoria en computación.
El problema también sirve como banco de pruebas para algoritmos de inteligencia artificial y ha motivado el desarrollo de técnicas de búsqueda heurística que hoy se aplican en logística, planificación y otras áreas.
Una curiosidad adicional
Si se generaliza el problema a un tablero de 27×27, el número de soluciones ya supera las 2.000 millones. Para tableros más grandes, incluso los mejores algoritmos modernos tardan un tiempo considerable en encontrar todas las soluciones. La belleza del problema está en que su enunciado es absolutamente simple y su enorme complejidad subyacente es una sorpresa que nunca deja de impresionar.