Probablemente usted ya conozca el probelma de las 8 damas y cómo tendrían que ser colocadas en un tablero de 8 x 8 casillas para que ninguna de ellas ataque a otra. Por ejemplo, no es posible colocar dos damas en la misma fila, columna o diagonal.
El problema fue ideado por Max Bezzel en 1848. La primera solución la mandó Franz Nauck en 1850. Amplió el problema a n damas en un tablero de ajedrez con n casillas. Desde entonces, muchos matemáticos, entre ellos el propio Carl Friedrich Gauss, han trabajado en el problema de las 8 damas y sus versiones generalizadas de n damas.
Un tablero de ajedrez infinito. La imágen es del siguiente vídeo genial: Infinite Chess | Fuente: PBS Infinite Series, en su canal de YouTube
Puede usted intentar resolver el problema en este fantástico tablero JavaScript, facilitado por Ronald Daenzer, que está disponible en la página web de The JavaScript Source . (Ojo: ¡puede ser una tarea que le lleve mucho tiempo!)
Las doce soluciones se encuentran en la parte inferior de la página
Tal y como menciona Martin Gardner en éste artículo el problema de las 8 damas tiene 92 soluciones distintas. 12 , si eliminamos las simétricas, generadas con rotaciones y reflexiones del tablero.
Gardner llevó el problema más allá: coloque 3 damas blancas y 5 damas negras en un tablero de 5 x 5 casillas de tal manera, que ninguna de las damas de un color esté atacando a las del otro color. Únicamente existe una solución para este problema, excluyendo reflexiones y rotaciones. Igual le apetece encontrar la solución para este problema. Bueno, pero ese no es el tema de nuestro artículo de hoy.
El problema de las 8 damas es un caso particular del problema más general de las n damas a colocar en un tablero de n x n casillas. La solución existe para todos los números naturales n (con la excepción de n=2 y n=3).
El profesor Ian Gent y el Dr. Peter Nightingale | Foto: Phys.org © Stuart Nicol
Los científicos informáticos Ian Gent y Peter Nightingale, de la Universidad de St. Andrews en Escocia, están retando a los programadores a resolver el problema del valor n. Las soluciones, al utilizar fuerza bruta, para un tablero de 8 x 8 únicamente tardan unos microsegundos, pero se ha calculado que una vez que las medidas del tablero llegan a 100 x 100 casillas el ordenador ya no puede con cifras tan grandes en un tiempo razonable de cálculo. La verdad es que teóricamente tardaría unos 1000 años para encontrar la solución.
O sea que, Gent y Nightingale ofrecen un premio de 1.000.000 dólares para aquel que encuentre una solución que tarde menos tiempo. Según Gent eso es importante porque "si fuese posible escribir un programa informático que pueda resolver ese problema en realmente poco tiempo, también se podría adaptar a la mayoría de los problemas importantes que nos afectan a todo el mundo a dario. Esto incluye unos retos tan triviales como por ejemplo, trabajar el grupo más grande de amigos en Facebook que no se conocen unos a otros. O bien cuestiones muy importantes como la de hackear los códigos que mantienen seguras todas nuestras transacciones a través de internet".
Estas son las 12 soluciones al problema de las 8 damas que excluyen las rotaciones y reflexiones del tablero:
Texto: Frederic Friedel (ChessBase)
Traducción: Nadja Wittmann (ChessBase)
Nota: aunque el problema se ha divulgado particularizándolo para el caso de las damas y el tablero de ajedrez, en puridad se trata de uno de los llamados problemas del milenio, cuyo enunciado es mucho más complejo. Declaración del Instituto Clay
