Al mediodía os proponía una forma de empezar a resolver el problema.
He seguido colocando damas y ha ocurrido lo siguiente:
O sea, que nos hemos encontrado sin salida. Hemos colocado 5 damas y ya no podemos continuar porque la sexta la pongas donde la pongas estará amenazada.Os preguntaba como continuar y no ha habido respuesta. Así que lo continuo como se me ocurra a mi.
Este algoritmo que hemos seguido se parece mucho a una búsqueda en un árbol. Para el que no haya estudiado esto de grafos y árboles os lo explico:
Ante un callejón sin salida, volvemos atrás y miramos si la última dama colocada se puede poner en otra casilla.
Llegamos al punto en el que colocamos la dama en E4. La siguiente dama no la podemos poner.Volvemos atrás y buscamos otra opción. Encontramos la casilla E8 donde podemos colocar dama.
Continuamos como siempre y vemos que se puede colocar una dama en F4.
Con esta técnica hemos podido poner una dama más aunque no nos ha servido demasiado por encontrarnos en otro callejón sin salida.
Como no podemos continuar más, hay que retroceder hasta ir agotando todas las posibilidades.
El grafo es un diagrama de líneas y el árbol es un tipo de grafo especial en el que un padre tiene 1 o varios hijos, pero un hijo sólo tiene un padre. El dibujo que hemos elaborado es un árbol.
Cuando nuestros programas tengan que recorrer un árbol hay dos estrategias diferentes:
La búsqueda que hemos visto se llama búsqueda en profundidad porque avanzamos todo lo que podemos por una rama hasta el callejón sin salida. Si hay que retroceder retrocedemos lo mínimo necesario para encontrar una rama lo más profunda posible. Esta es una buena estrategia cuando la profundidad máxima está controlada (en nuestro problema hay 8 niveles) y nuestro algoritmo no se va a perder por esos caminos.
Con grandes profundidades, si no queremos ver nuestro programa perdido en una rama profundísima podemos emplear la búsqueda en anchura. Se trata de retroceder hasta el nivel superior y empezar por otra rama antes de empezar a indagar en las profundidades.
Saludos.
No hay comentarios:
Publicar un comentario