Wir haben alle vom Knight's Tour- Puzzle gehört: Finde eine Route für einen Ritter, der alle Felder auf einem Schachbrett durchquert. Aber seien wir ehrlich, es ist ein bisschen langweilig. Geben wir dem Ritter also eine Herausforderung.

Aufgabe

Schreiben Sie ein Programm, das den Ritter auf einem Schachbrett beliebiger Größe und beliebiger Form durch alle Felder führt. Es sollte das Schachbrett als Eingabe und Ausgabe der Züge und der Startposition verwenden. Im Falle eines unmöglichen Boards sollte es den Satz von Zügen und die Startposition für eine Tour mit der längstmöglichen Länge ausgeben. Hinweis: Der Ritter muss keine Rundreise machen. Angenommen, er hat einen anderen Weg nach Hause.

Schachfiguren sind klein, daher muss Ihr Code klein genug sein, damit der Ritter sie herumtragen kann.

Eingang

Die Eingabe ist eine auf Zeichenfolgen oder Arrays basierende Darstellung eines Schachbretts, wobei ein nicht leerer / wahrheitsgemäßer Wert ein Quadrat und ein leerer / falscher Wert ein leerer Raum ist. Der Einfachheit halber werde ich für die Beispiele #s und s verwenden, die in einem Raster angeordnet sind.

Ausgabe

Die Ausgabe besteht aus zwei großen Ganzzahlen, gefolgt von einer Reihe von 4-Bit-Ganzzahlen oder dem Äquivalent Ihrer Sprache. Die zwei großen ganzen Zahlen repräsentieren die Startkoordinaten, und die folgenden Zahlen repräsentieren eine Bewegung wie folgt:

 7 0
6   1
  K
5   2
 4 3

Wo Kist die Position vor dem Umzug und die Zahl ist die Position nach dem Umzug.

Beispiele

Da es viele mögliche Lösungen für das Knight's Tour-Puzzle gibt, werde ich nur Beispielausgaben bereitstellen. Möglicherweise sind mehr Ausgänge vorhanden.

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

^{Neue Herausforderung: Überlegen Sie sich weitere Beispiele}

Mathematica, 151 Bytes

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

Offensichtlich HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&]macht die ganze Arbeit.

Die Eingabe erfolgt wie eine 2D (0,1) -Matrix {{0,0,1},{1,1,1},{1,0,1},{1,1,1}}.

Die Ausgabe sieht folgendermaßen aus: {{2, 0}, {5, 3, 0, 5, 2, 7, 4, 1}}

Ich weiß nicht viel über Mathematica Golf, also zögern Sie nicht, auf Verbesserungen hinzuweisen. Gibt es einen besseren Weg, um einzelne Ergebnisse zu speichern, als eine Milliarde reine Funktionen zu verwenden?

Ein Byte gespeichert; Danke, CatsAreFluffy.