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).



9 Responses so far.

  1. erika says:

    hola nececito el codigo del algoritmo de fleury y del algoritmo de kruskal, porfa, para mañana 4 de dicicembre de 2008 m urge es mi derecho a extra. espero q m puedan ayudar.

  2. hitokiri says:

    nadie ayudo a erike, que mal pez. ajaja
    que buena anotación le pude entender de una vez a ese dicho movimiento del caballo algo que no consegui leyendo el Deitel.

  3. Alejandro says:

    publiquen de nuevo el codigo para el recorrido del caballo, lo necesito checar mañana 16/12/09 en la mañana… Porfa Gracias

  4. admin says:

    Yo también necesito muchas cosas. ¿Por que no mejor lo hacen ustedes?, se supóne que “deberían” saber eso.

    Con el agoritmo publicado es suficiente para programarlo en cualquier lenguaje.

    Saludos.

  5. eulerss says:

    >>porfa, para mañana 4 de dicicembre de 2008 m urge es mi derecho a extra.

    y si lo mando mas tarde?? hay que estudiar para no irse a extras Erika

    >>publiquen de nuevo el codigo para el recorrido del caballo, lo necesito checar mañana 16/12/09 en la mañana…

    otro, si gustan que vaya admin a hacer sus tareas y examenes por ustedes, o que mejor, a tomar las clases tambien

  6. admin says:

    jajajaja, si, ya casi me mandan el correo de su profe para que les mande la tarea

  7. Toro93 says:

    Hola quisiera saber si alguien tiene el algoritmo de fleury en c++ o algun otro lenguaje

  8. yo says:

    hola man gracias pro el post una pregunta el codigo se demora en correr estoy correindo el ejemplo que colgaste pero al momento de darle las coordenadas se queda

  9. Ernesto Alonso says:

    Hola! Solo para comentar una pequeña sugerencia sobre la palabra “Desarollando”. Se debería cambiar por “Desarrollando”. Con doble “r”.
    Saludos!


Subscribe to email feed



Password box on a webpage

Como usar una funci

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

t-google-404-1299071983

Cómo escribir códi

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

java_logo

Las 114 preguntas de

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

ziff-davis

Believe in technolog

Ziff Davis Publishing es la más grande editorial de contenidos ...

software-architect-salary

Introducción a SCRU

SCRUM es una plataforma de desarrollo ágil que da las ...

Password box on a webpage

Como usar una funci

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

t-google-404-1299071983

Cómo escribir códi

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

java_logo

Las 114 preguntas de

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

ziff-davis

Believe in technolog

Ziff Davis Publishing es la más grande editorial de contenidos ...

software-architect-salary

Introducción a SCRU

SCRUM es una plataforma de desarrollo ágil que da las ...