El problema del recorrido del caballo en el tablero de ajedrez

Como ya mencionamos en la entrada del Cuaderno de Cultura Científica titulada A vueltas con el origen del ajedrez, la relación entre ajedrez y matemáticas ha sido siempre muy fructífera. Problemas clásicos como el recorrido del caballo sobre el tablero de ajedrez, el problema de Guarini (al que dedicamos la entrada Ajedrez y matemáticas: el […]

[#1 Urasandi]

Solo se me ocurre una palabra: Prolog.

Si, tengo la pauta completa.

[#2 Vauldon]

#1 Primero de carrera, esa palabra es la ballena blanca de mis pesadillas.

[#3 Urasandi]

#2 Yo hice mecánica, pero me gustaba la informática. Me hizo gracia el Prolog, pero no llegue muy lejos. Peor me parecia el Lisp, que lo hubiese podido usar con el Autocad.

[#12 mecha]

#3 (((((porque) no) te) gusta) LISP) ?

[#20 minarun]

#12 Haskell es mucho mejor, y sin paréntesis

[#14 Ehorus]

#2 secundo
y sin embargo, el lisp me pareció hasta entretenido... quizás porque al final termine de entender el concepto de recursividad absurda (al menos así fué para mí) .. sin embargo, el prolog.. nop, imposible....
en favor mia, diré que los profesores podrian haber dado clase a un hormiguero, que se iban a enterar lo mismo

[#4 Deckardio]

Muy interesante... ¡y con bibliografía!

[#5 napoleon]

Hay ajedrez, hay meneo

[#6 --624999--]

borro esto que esta equivocado

[#7 Don_Gato]

El caballo solo trae problemas. Da igual dónde leas esto.

[#8 eltoloco]

Hice una práctica sobre esto en 2º de carrera, la cual nos servia para aprender backtracking.

Apliqué la regla de Warndorff (Que no se menciona en el artículo), y esto junto con algunos puntos adicionales (Tablero y movimientos configurables) me valió el 10..

en.wikipedia.org/wiki/Knight's_tour#Warnsdorff's_rule

[#23 eltoloco]

#15 es al contrario, el siguiente movimiento es el que tiene menos opciones de movimiento, se llama regla de Warnsdorff, la he mencionado y enlazado en #8

Además unos cuantos segundos es una auténtica burrada, lo debería resolver en milisegundos, pues con dicha regla no se requiere backtracking y se resuelve a la primera. Incluso sin la mencionada regla debería resolverse muchísimo más rápido, ese algoritmo que programaste tiene algo que falla.

[#24 adrigm]

#23 Tienes razón lo recordaba al revés (pero en su momento lo hice bien )

Aquí tienes el enlace del artículo que escribí en su día y el código en Python. Seguramente ahora haría algo mucho mejor

razonartificial.wordpress.com/2010/01/08/el-salto-del-caballo-backtrac

[#9 rubentotal]

Al precio que van las algarrobas este año, sí que es un problema sí

[#10 Nitzen]

Recuerdo hace años que, tras leer sobre el reto de mover el caballo por todas las casillas del tablero sin repetir ninguna, me animé a probar a hacerlo al pronto y sin preparación, y el problema solía ser que se me olvidaba por qué casillas había pasado ya (como aficionado al ajedrez, me gusta el tablero y me empeñaba en hacerlo sobre el tablero en vez de tachando casillas sobre un papel). Tiempo después lo conseguí y lo mostré a algunos amigos, pero simplemente había memorizado una de las soluciones que me había calculado otro amigo que no era experto en ajedrez pero sí en matemáticas jejeje.

[#11 La_patata_española]

En la primera solución, de recorrido abierto, hay un 45 que debería ser un 43 (lo he puesto encima en rojo).  

[#13 --722994--]

Hay 2 cuadros 45, debe de ser un error. Bien empezamos!
#11 perdon, no te había leido.

[#21 minarun]

#11 Sí, ya me dí cuenta. No era tan difícil de verificar.

[#15 adrigm]

En sus tiempos programé en Python un algoritmo de backtraking para resolverlo. Se tiraba como 5 min en resolverlo. Aplicando una herustica tan simple como que siempre elegí era primero que el siguiente cuadrado fuera el que más opciones detenía de movimiento lo resolvía en unos segundos.

[#22 minarun]

#16 En catalán son "peces" y las casillas son "escacs"

[#19 piper]

#16 Me parece que sí, el equivalente gallego "trebello" también figura en algún diccionario gallego, pero yo nunca lo he escuchado con ese significado. Normalmente significa herramienta rara o complicada, nada con relación al ajedrez.

[#18 jaramero]

#16 vaya nombre más raro, si dices fichas te entiende todo el mundo

[#17 poyeur]

En el programa "Qué apostamos" recuerdo a un participante que lo hacía con los ojos cerrados, no recuerdo si la solución abierta o cerrada