Todos nós já ouvimos falar do quebra-cabeça do Knight's Tour : encontre uma rota para um cavaleiro que atravessa todos os quadrados de um tabuleiro de xadrez. Mas vamos ser honestos, é um pouco chato. Então, vamos dar ao cavaleiro um desafio.

Tarefa

Escreva um programa que leve o cavaleiro por todos os quadrados em um tabuleiro de xadrez de tamanho arbitrário e tamanho arbitrário. Deve-se considerar o tabuleiro de xadrez como entrada e saída do conjunto de jogadas e da posição inicial. No caso de uma prancha impossível, ela deve exibir o conjunto de jogadas e a posição inicial de um passeio com o maior comprimento possível. Nota: o cavaleiro não precisa fazer uma viagem de ida e volta; suponha que ele tem outra maneira de chegar em casa.

As peças de xadrez são pequenas, portanto seu código precisa ser pequeno o suficiente para o cavaleiro carregar.

Entrada

A entrada será uma representação baseada em string ou em array de um tabuleiro de xadrez, em que um valor não em branco / verdade é um quadrado e um valor em branco / falso é um espaço vazio. Por uma questão de simplicidade, usarei #s e s dispostos em uma grade para os exemplos.

Resultado

A saída será dois números inteiros grandes, seguidos por uma série de números inteiros de 4 bits ou o equivalente do seu idioma. Os dois números inteiros grandes representarão as coordenadas iniciais e os seguintes números representarão um movimento da seguinte forma:

 7 0
6   1
  K
5   2
 4 3

onde Kestá a posição antes da movimentação e o número é a posição após a movimentação.

Exemplos

Como existem muitas soluções possíveis para o quebra-cabeça do Knight's Tour, fornecerei apenas exemplos de resultados. Pode haver mais saídas.

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

^{Novo desafio: crie mais exemplos}

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&]faz todo o trabalho.

A entrada é semelhante a uma matriz 2D (0,1) {{0,0,1},{1,1,1},{1,0,1},{1,1,1}}.

A saída é assim: {{2, 0}, {5, 3, 0, 5, 2, 7, 4, 1}}

Eu não sei muito sobre o golfe Mathematica, então fique à vontade para apontar melhorias. Existe uma maneira melhor de salvar resultados individuais do que usar um bilhão de funções puras?

Salva um byte; obrigado, CatsAreFluffy.