Por @Alvy — 6 de Septiembre de 2017

1000 damas

Hay un millón de dólares para quien resuelva el popular problema de las 8 damas de ajedrez pero en un tablero de 1.000 × 1.000 con 1.000 damas.

Obviamente no es un problema fácil. El original que todos conocemos se propuso en 1848 con ocho damas y aunque también se han encontrado las soluciones para 9, 10 y hasta 14 damas, no se conoce una forma de dar con una generalización de la solución ni tampoco el caso concreto de 1.000 × 1.000.

Más detalles en El País: Un millón de dólares para quien resuelva este “simple” enigma de ajedrez.

Actualización – José Luis nos hizo llegar un enlace a la fuente original (ClayMath) donde se explica que cuando los autores de un trabajo acerca del problema hablaban de esto podría significar ganar el millón de dólares de los Problemas del milenio no era el caso.

En realidad es un problema del tipo P vs. NP llamado Problema de completitud de las n-Damas, donde se trata de las soluciones de tipo P y NP para un tablero genérico en el que además ya se hayan hecho algunas «jugadas». En sus propias palabras: «sería necesario demostrar que hay un algoritmo que puede resolver el problema de completitud de las n-Damas en tiempo polinomial o una demostración de que no existe dicho algoritmo.»

Compartir en Flipboard Compartir en Facebook Tuitear

Microsiervos Selección


One Jump Ahead: Computer Perfection at Checkers

EUR 27,26 (Reseña en Microsiervos)

Comprar


The Puzzle Ninja

EUR 10,90

Comprar


Una partida más y me acuesto

EUR 23,70

Comprar


Amazon Associates

Los productos aquí enlazados están a la venta en Amazon. Incluyen un código de Afiliado Amazon Associates que nos cede un pequeño porcentaje de las ventas. Los productos están seleccionados por los autores del blog, pero ni Amazon ni los editores de los libros o fabricantes de los productos participan en dicha selección.

Más libros y productos en:

Microsiervos Selección