El problema del millón de dólares
04/09/2017 – Es un problema de ajedrez antiguo, que se planteó en el año 1848: coloque 8 damas en un tablero de ajedrez, de tal manera que ninguna de ellas amenace a otra. La solución fue publicada 2 años después, pero el problema de n damas en un tablero de n x n casillas (por ejemplo, 100 damas en un tablero de 100 x 100) sigue sin resolverse. Los ordenadores de hoy en día, tardarían miles de años en calcular la solución para resolver un problema tan complicado. Si usted consigue programar un algoritmo que pueda calcularlo en mucho menos tiempo, podría ganar un millón de dólares. ¿Por qué no lo intenta?
Find the right combination! ChessBase 15 program + new Mega Database 2020 with 8 million games and more than 85,000 master analyses. Plus ChessBase Magazine (DVD + magazine) and CB Premium membership for 1 year!
Generalización del problema de las 8 damas
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 reto del millón de dólares
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".
Soluciones
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
Enlaces
- Phys.org: 'Simple' chess puzzle holds key to $1m prize
- Courier: Challenge to end stalemate over $1 million maths puzzle
- Inquirer: Researchers: $1m is yours if AI can break the chess stalemate
- ITPro: University of St Andrews offers $1m prize to crack chess challenge
- Sky News: Eight queens puzzle: $1m prize for anyone who can solve 'simple' chess puzzle
