martes, 31 de diciembre de 2013

Sherlock Homes y el problema del caballo

Después de un rato jugar el videojuego The testament of Sherlock Holmes me encontré con este acertijo conocido.



Se trata del tour del caballo como las máquinas sirven para hacer prueba y error dejé la consola y encendí el PC para escribir la solución a este.

Hay que decir que este problema es bastante sencillo de resolver para tableros pequeños y basta con un dfs o backtracking y se obtienen no sólo una sino todas las soluciones posibles :)

Así pues la idea básica del algoritmo es:


Guardar los deltas de los movimientos en alguna estructura puede ser un arreglo.

función solución(f, c, cam, vis):
  si ya visitó todas las casillas imprima cam y retorne
  para cada movimiento:
    si es posible(no se ha realizado y no se sale del tablero)
      movf = f+deltaf iésimo
      movc = c+deltac iésimo
      solución(movf, movc, cam+(movf+movc), vis+(movf+movc))
      remover movf y movc de cam y de vis

y la llamada inicial sería algo como

solucíon(0,0,'',estruc)
donde estruc es alguna estructura que permita eficientemente controlar qué casillas ya se han visitado.


Si se usa un conjunto se puede saber cuántas se han visitado aunque con una matriz también funcionaría se necesitaría un contador como parámetro adicional.

Que se diviertan!

No hay comentarios:

Publicar un comentario