El Problema de las 8 Damas
Uno de los problemas mas vistos y conocidos en la ingenieria, hasta por los que no saben de ajedrez. Recuerdo que mi maestra de Inteligencia Artificial nos machacaba con problemas de ese tipo.
¿De que trata el problema de las ocho damas? es un acertijo en el que se colocan ocho damas sin que se amenacen en el tablero normal de 8x8, en pocas palabras (para los no entendidos en ajedrez) consiste en colocar las 8 piezas de manera que no coincidan dos en la misma fila, columna o diagonal.
Conocido tambien como el problema de las n damas, la n es el numero de damas y la logitud del lado del tablero, un problema de 5 damas se solucionaria en un tablero de 5x5, uno de 4 en un tablero de 4x4 y asi para los demas.
El planteamiento del problema en si es algo ya viejo, fue propuesto por el alemán Max Bezzel en 1848 y el primero en hallar las 92 soluciones sería el matemático ciego Franz Nanuck en 1850.
Existen infinidad de metodos para la solucion del mismo, uno de los que se enseña en las univerdidades es el metodo de Backtracking o vuelta atrás que consiste en la realizacion de un diagrama de arbol en el que las soluciones se van dando parcialmente a medida que se progresa por el recorrido del mismo, en palabras mas tecnicas es un recorrido en profundidad dentro de un grafo dirigido.
Lo curioso del caso es que de las 92 soluciones solo 12 son esencialmente distintas, las otras 80 soluciones restantes existentes se pueden obtener a partir de simetrías, rotaciones y traslaciones de las 12 soluciones únicas las cuales se pueden ver el diagrama siguiente:
En la actualidad hasta programas hay para jugar y divertirse con este problema, al final de este articulo les dejare una lista de enlaces interesantes como un articulo de Chessbase, una pagina para resolver el problema en linea y por si fuera poco el codigo en C# de un programa que resuelve el problema, que lo disfruten.
Sitios Relacionados:
[1] Ocho Reinas por Manuel López Michelone
[2] Juego Online Ocho reinas
[3] Codigo desarrollado en C# para el modo consola
¿De que trata el problema de las ocho damas? es un acertijo en el que se colocan ocho damas sin que se amenacen en el tablero normal de 8x8, en pocas palabras (para los no entendidos en ajedrez) consiste en colocar las 8 piezas de manera que no coincidan dos en la misma fila, columna o diagonal.
Conocido tambien como el problema de las n damas, la n es el numero de damas y la logitud del lado del tablero, un problema de 5 damas se solucionaria en un tablero de 5x5, uno de 4 en un tablero de 4x4 y asi para los demas.
El planteamiento del problema en si es algo ya viejo, fue propuesto por el alemán Max Bezzel en 1848 y el primero en hallar las 92 soluciones sería el matemático ciego Franz Nanuck en 1850.
Existen infinidad de metodos para la solucion del mismo, uno de los que se enseña en las univerdidades es el metodo de Backtracking o vuelta atrás que consiste en la realizacion de un diagrama de arbol en el que las soluciones se van dando parcialmente a medida que se progresa por el recorrido del mismo, en palabras mas tecnicas es un recorrido en profundidad dentro de un grafo dirigido.
Lo curioso del caso es que de las 92 soluciones solo 12 son esencialmente distintas, las otras 80 soluciones restantes existentes se pueden obtener a partir de simetrías, rotaciones y traslaciones de las 12 soluciones únicas las cuales se pueden ver el diagrama siguiente:
En la actualidad hasta programas hay para jugar y divertirse con este problema, al final de este articulo les dejare una lista de enlaces interesantes como un articulo de Chessbase, una pagina para resolver el problema en linea y por si fuera poco el codigo en C# de un programa que resuelve el problema, que lo disfruten.
Saludos y hasta la proxima
Sitios Relacionados:
[1] Ocho Reinas por Manuel López Michelone
[2] Juego Online Ocho reinas
[3] Codigo desarrollado en C# para el modo consola