Problema de las N reinas
La solución a este problema se encuentra con un algoritmo de backtracking, que consiste en asignar una fila a cada reina, y progresivamente colocar cada reina en una posición diferente. Si una reina es amenazada en cualquier casilla de su fila, la retiramos y colocamos la reina anterior en otra posición. El programa termina cuando se ha conseguido colocar a todas las reinas en posiciones seguras.
Aquí dejo una propuesta dinámica para N reinas, en lenguaje C:
>> Descargar reinas.c <<
Mejorando el algoritmo
Tiempo después de publicar originalmente este post, estudié que éste es realmente un problema de satisfacción de restricciones. Resolver un problema NP completo puede costarnos mucho tiempo, ya que el espacio de búsqueda crece enormemente respecto al tamaño del problema. La aproximación por backtracking "a pelo" intenta asignar las posiciones de las reinas en cualquier orden, y con cada movimiento tiene que comprobar si la reinas es amenazada.
Podemos hacer la búsqueda mucho más eficiente si, en vez de colocar una reina y comprobar si está segura (solución parcial consistente), colocarla donde sabemos que estará segura, y prohibir al resto de reinas posicionarse donde nuestra reina la pueda amenazar. En palabras de programador: antes usábamos un vector en el que se indicaba dónde está cada reina; ahora guardaremos un vector de conjuntos, que indicarán en qué casillas se podrá alojar cada reina.
Cuando coloquemos una reina, le asignaremos uno de sus candidatos y, mediante propagación de restricciones, tacharemos la casilla correspondiente en los conjuntos vecinos (eliminaremos la vertical y las dos diagonales). Si, a medida que propagamos restricciones, eliminamos todos los candidatos de una de las variables (la reina no se puede colocar en ningún lugar sin ser amenazada), deshacemos las restricciones y volvemos atrás.
Además, a la hora de escoger qué reina colocar, en lugar de hacerlo por orden de filas, ahora podemos colocar primero a la reina con menos posiciones candidatas (heurística del mínimo de valores restantes) para que, si tenemos que volver atrás, lo hagamos lo antes posible.
El siguiente enlace contiene la nueva implementación en cuatro lenguajes: C++, Java, C# y Python, todos con exactamente el mismo algoritmo:
Podremos ver que, para tamaños del problema donde el primer código tardaba casi un minuto (alrededor de 32 reinas), el nuevo algoritmo lo hace en pocos milisegundos.
Para resolver problemas de este tipo se puede utilizar la herramienta Eclipse CLP, donde describimos las restricciones en una extensión de Prolog y el sistema se encarga de utilizar heurísticas avanzadas para encontrar la solución muy rápidamente. Siempre tardaremos menos tiempo en describir el problema que en construir un algoritmo de búsqueda en otro lenguaje.
graciassssssssssssss :)
ResponderEliminarEn algunos diagramas de ajedrez a la pieza del alfil se lo representa con un yelmo o casco de armadura de caballero medieval. ¿A qué se debe esto si lo legal es que se le represente con una mitra papal?. ¡Gracias!.
ResponderEliminarRealmente no soy experto en ajedrez, pero es interesante tu pregunta. Según parece, el ajedrez es una representación político-religiosa, y su diseño actual concibe al alfil como un obispo, de ahí la mitra como símbolo del orden episcopal.
EliminarSin embargo, en una antigua variante de origen protestante, el alfil era un caballero, consejero del Rey, por eso se le representaba con un yelmo. Hay que tener en cuenta que a lo largo de los años, el ajedrez ha cambiado tanto en sus reglas como en representación, y algunos cambios se han debido a cuestiones políticas o religiosas.
He encontrado la información en esta página: https://es.answers.yahoo.com/question/index?qid=20151007113851AAalnKA
¡Un saludo!