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!

Solucionando sudokus

Su Doku es un juego muy conocido, no entraré en detalles históricos. Este problema puede ser visto como el problema de colorear un grafo, de esta forma los colores son cada uno de los números del uno al nueve, los nodos son cada una de las casillas y están conectados si están en un mismo recuadro, en una misma fila o en una misma columna.

Pasando a la solución por backtracking bien se puede ver que la fuerza bruta consiste en ubicar las casillas vacias y poner un numero en cada una de ellas y ver cuando ya no hayan casillas vacias si el sudoku ha sido resuelto, de no ser así se vuelve a atrás y se intenta con otros números. El problema de este enfoque es que si hay n casillas vacías se tendrán n! (n factorial) formas de llenar estas casillas. Tal vez para unas 9 casillas vacías funcione, pero si se intenta con 10 o más en un ordenador común en la actualidad, puede tardar mucho tiempo.

Así que la mejor forma de hacerlo es ver cuál casillas de las vacías tiene menos posibilidades y optar por una de ellas y hacer lo mismo recursivamente hasta que no hayan casillas vacías, en este punto se verifica si el sudoku está bien, de ser así ya está, si no entonces se vuelve atrás y se opta por otra de las posibilidades en la casilla que tenia varias posibilidades. Finalmente, si el sudoku está bien construido se podrá llegar a una solución.

En pseudocódigo esto podría ser algo como (la implementación en java o cpp no va más de 80 líneas! :) )

Creo que esta es la forma mas simple de resolver este problema, otro enfoque es usando la ténica de Knuth de "Dancing links". El enfoque presentado aquí no es el más eficiente pero es bastante sencillo de programar y puede ser útil en un concurso de programación :)

Cualquier comentario o duda, comenten.

Nota: les dejo algunos problemas que se pueden resolver con este algoritmo.

https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2246
http://projecteuler.net/problem=96