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



retina_ipad_mini_ipad_air_fake_mockup_hero

iPad Air, poderosame

Apple nos vuelve a sorprender con su mas reciente lanzamiento ...

kitkat-google

Android KitKat ha ll

El martes pasado Google anunció las características de Android KitKat ...

trello-logo

Control de tus proye

Buscando una aplicación que me permitiera organizar y gestionar mis ...

Manual-SQL-en-español

Antipatrones de SQL

Los Antipatrones son diseños  que invariablemente conduce a una mala ...

eclipse

7 Plugins Esenciales

Eclipse  poderosa herramienta  de desarrollo que permite crear nuestros proyectos ...

retina_ipad_mini_ipad_air_fake_mockup_hero

iPad Air, poderosame

Apple nos vuelve a sorprender con su mas reciente lanzamiento ...

kitkat-google

Android KitKat ha ll

El martes pasado Google anunció las características de Android KitKat ...

trello-logo

Control de tus proye

Buscando una aplicación que me permitiera organizar y gestionar mis ...

eclipse

7 Plugins Esenciales

Eclipse  poderosa herramienta  de desarrollo que permite crear nuestros proyectos ...

File Adobe Dreamweaver HTML 01

Aprendiendo HTML

HTML es el lenguaje de publicación en el Internet. Es ...