Novacreations

Desarollando Software

Recorrido del caballo

En un tablero de ajedrez de nXn casillas se tiene un caballo situado en la posición inicial de coordenadas (x0,y0). El problema consiste en encontrar, si existe, un circuito que permita al caballo pasar exactamente una vez por cada una de las casillas del tablero, teniendo en cuenta lo movimientos permitidos a un caballo en el juego de ajedrez.La primera consideración a tener en cuenta es que el caballo, desde una casilla, puede realizar hasta 8 movimientos.

Los 8 posibles movimientos del caballo se obtienen sumando a la posición actual, (x, y), los desplazamientos relativos (d) que permiten obtenerlos:

d={(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)}

Por ejemplo, suponiendo que el caballo se encuentra en la posición con coordenadas (3,5), los posibles movimientos que puede realizar son:

d={(5,6),(4,7),(2,7),(1,6),(1,4),(2,3),(4,3),(5,4)}

No siempre será posible realizar los ocho movimientos; se debe comprobar que la casilla destino esté dentro del tablero y también que no ha pasado previamente el caballo por ahí. En caso de ser posible el movimiento, se anota, guardando el número del salto realizado.

La condición de resolución del problema es que el caballo haya pasado por las n2 casillas, es decir que el caballo haya realizado 64 saltos. En ese momento se pone a true la variable éxito.

Si se agotan los ocho posibles movimientos sin alcanzar la solución se vuelve al movimiento anterior, backtracking, se borra la anotación para ensayar con el siguiente movimiento. Y si también se han agotado los movimientos, ocurre lo mismo; se vuelve al que fue su movimiento anterior para ensayar, si es posible, con el siguiente movimiento.

Algoritmo:

Descarga el ejemplo de código implementado en C++

[download id=”59″ format=”1″]

Backtracking es una estrategia para encontrar soluciones a problemas que safisfacen restricciones. El término fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en 1950s.

La técnica va creando todas las posibles combinaciones de elementos para obtener una solución. Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso, se dice que este tipo de algoritmo es una búsqueda en profundidad. Durante la búsqueda, si se encuentra una alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa. Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción. Si no hay más alternativas la búsqueda falla. De esta manera, se crea un árbol implícito, en el que cada nodo es un estado de la solución (solución parcial) o en el caso de los nodos hoja (solución total).



10 Tips para el Cód

Nuestro objetivo como desarrolladores es tener un código que sea ...

Ganadores del Premio

El Centro de Educación y Capacitación para el Desarrollo Sustentable ...

La fábrica de softw

La Fábrica de Software de la Dirección de Innovación y ...

Administradores de A

Durante años aplicación ES File Explorer era la mejor y ...

Apoyo del Conacyt a

El Consejo Nacional de Ciencia y Tecnología (Conacyt), como parte ...

Ganadores del Premio

El Centro de Educación y Capacitación para el Desarrollo Sustentable ...

Las 10 funciones de

  Java 8 incluye nueva funcionalidad que nos permite tener un ...

Como usar una funci

Usar una función hash para encriptar una contraseña no es ...

Cómo escribir códi

Nunca supongas a la malicia lo que puede ser explicado ...

Las 114 preguntas de

¿Tienes una entrevista de trabajo en puerta para un posición Java? ...