Algoritmos de Vuelta Atrás











Algoritmos de Vuelta Atrás







Estructura de Datos
Instituto IACC
10 de noviembre de 2014
Desarrollo

“Un amigo suyo aficionado al ajedrez, en medio de unapartida especialmente trabada, le cuenta una inquietud que él tiene hace mucho tiempo con este juego y que nadie ha podido responderle todavía. Se trata de cómo colocar ocho piezas iguales (8 reinas en estecaso) sobre el tablero, de tal forma que ninguna pueda comerse a otra”.
Sabiendo que en este juego, una reina amenaza a cualquier otra pieza que esté en la misma columna, fila o cualquiera de lascuatro diagonales, el problema es obviamente la forma en que dichas piezas deben estar distribuidas sobre el tablero en un primer momento.

¿Con qué tipo de algoritmo estamos tratando al intentarresolver este problema?
Este problema clásico puede ser resuelto con un diseño de algoritmo de Vuelta Atrás ya que este nos puede dar la solución al denominado problema de las ocho reinas y en general,a las de n reinas.
¿Por qué?
Porque si tratamos de colocar en un tablero de ajedrez de tamaño 8x8, y tratamos de colocar en él ocho reinas de manera que no se amenacen según las normas delajedrez, es decir, que no se encuentren o colisionen dos reinas ni en la misma fila, ni en la misma columna, ni en la misma diagonal.
Por lo cual el diseño Vuelta Atrás nos proporcionara de manerasistemática, todas las posibles soluciones siempre que dichas soluciones sean o estén susceptibles de resolverse en etapas durante el proceso de análisis de la solución.
En su forma básica de analizar laVuelta Atrás se asimila, en realizar un recorrido completo dentro de un mapa jerárquico cuya existencia sólo es implícita.
Este mapa conceptual lo utilizaremos solo para la organización como tal, endonde cada nodo de nivel N representa una parte de la solución ya analizada previamente y estará conformado por N cantidad de etapas que se suponen ya están realizadas.




2. ¿Con cuántos...