Todos hemos oído hablar del rompecabezas del Knight's Tour : encuentra una ruta para un caballero que pase por todos los cuadrados en un tablero de ajedrez. Pero seamos honestos, es un poco aburrido. Entonces, demos un desafío al caballero.

Tarea

Escriba un programa que lleve al caballero a través de todos los cuadrados en un tablero de ajedrez de tamaño arbitrario y de forma arbitraria. Debe tomar el tablero de ajedrez como entrada y salida del conjunto de movimientos y la posición inicial. En el caso de un tablero imposible, debería generar el conjunto de movimientos y la posición inicial para un recorrido con la mayor longitud posible. Nota: el caballero no necesita hacer un viaje de ida y vuelta; suponga que tiene otra forma de llegar a casa.

Las piezas de ajedrez son pequeñas, por lo que su código debe ser lo suficientemente pequeño para que el caballero pueda llevarlo.

Entrada

La entrada será una representación basada en cadenas o matriz de un tablero de ajedrez, donde un valor no en blanco / verdadero es un cuadrado, y un valor en blanco / falso es un espacio vacío. Por razones de simplicidad usaré #s y S dispuestos en una rejilla para los ejemplos.

Salida

La salida será dos enteros grandes, seguidos de una serie de enteros de 4 bits, o el equivalente de su idioma. Los dos enteros grandes representarán las coordenadas iniciales, y los siguientes números representarán un movimiento como este:

 7 0
6   1
  K
5   2
 4 3

donde Kestá la posición antes del movimiento, y el número es la posición después del movimiento.

Ejemplos

Como hay muchas posibles soluciones para el rompecabezas de Knight's Tour, solo proporcionaré ejemplos de resultados. Puede haber más salidas.

###
# #
###
0 0 3 0 5 2 7 4 1

^{Nuevo desafío: presenta más ejemplos}

Mathematica, 151 bytes

Needs@"Combinatorica`"
{Reverse@#[[1]]-1,3-Floor[1.2Arg[Complex@@@Differences@#]]}&[#[[HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&]]]&@Position[#,1]]&

Obviamente, HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&]hace todo el trabajo.

La entrada es similar a una matriz 2D (0,1) {{0,0,1},{1,1,1},{1,0,1},{1,1,1}}.

La salida se ve así: {{2, 0}, {5, 3, 0, 5, 2, 7, 4, 1}}

No sé mucho sobre el golf de Mathematica, así que siéntase libre de señalar mejoras. ¿Existe una mejor manera de guardar resultados individuales que usar mil millones de funciones puras?

Guardado un byte; gracias, CatsAreFluffy.