Füllen 2D-Gitter mit einzelnem Pfad

Question

Wie kann ich mit Zahlen in einem quadratischen 2D-Array zu füllen, so dass ein (zufälliger) Pfad von aufeinanderfolgenden Zahlen in aufsteigender Reihenfolge 1-(edge length)2 erstellt wird?

Ich versuche, einen Hidato (alias Hidoku) Generator in JavaScript zu schreiben. Es ist nicht unbedingt die beste Sprache, um es zu schreiben, aber das ist es, was ich gerade benutze. Das Spielbrett ist zunächst nur teilweise gefüllt. Die einzigen angezeigten garantierten Nummern sind die erste und die letzte Nummer im Pfad. Die Idee des Spiels ist es, einen einzelnen Weg von Zahlen durch das Gitter (vertikal, horizontal oder diagonal) zu schaffen, so dass es eine fortlaufende aufsteigende Kette von Zahlen gibt. Die Kette kann sich aufgrund der Diagonalen überschneiden.

Ich bin auf der Platine Generation Teil stecken. Ein gültiges Gitter muss einen (einzelnen, nicht verzweigenden) Pfad mit fortlaufenden Nummern haben, die von 1 bis (grid size)2 gehen. Ich habe geschaut und geschaut, aber nichts gefunden, was mir hätte helfen können. Gibt es einen Wegverfolgungsalgorithmus, der ein 2D-Array mit einem einzigen Pfad füllen kann, der aus aufeinanderfolgenden Zahlen besteht?

Meine anfängliche, naive Methode bestand darin, ein 2D-Array mit Werten und Auslagerungswerten zu füllen, bis das Gitter ein gültiges Hidato-Puzzle war. Das würde ewig dauern und wäre sehr ineffizient, also habe ich diese Idee verschrottet.

Mein nächster Gedanke war, einen Backtracking Tracer zu verwenden, um das Raster mit aufeinanderfolgenden Werten zu füllen, aber ich bin mir nicht sicher, wie man einen solchen Tracer implementiert. Das Erzeugen eines Pfades ist einfach genug (wähle eine zufällige benachbarte Zelle und bewege dich dorthin, bis das 2D-Array voll ist), aber mein Problem hier ist die "Rückverfolgungs-Eigenschaft" des Algorithmus oder eine andere Möglichkeit, immer sicherzustellen, dass es ein zufälliges gibt Pfad der fortlaufenden Nummern im gesamten Netz. Ich dachte an einen Labyrinth-Tracer, aber das geht nicht um einzelne Pfade ohne Abzweigungen oder Sackgassen.

Wie kann ich von hier fortfahren? Sollte ich andere Optionen in Betracht ziehen als einen Pfad-Tracer oder einen ähnlichen Algorithmus?

Verwandte Fragen:

• Routing “paths” through a rectangular array
• Algorithm to find a random Hamiltonian path in a grid?

Answer 1

Es stellt sich heraus, dass der lokale Suchalgorithmus für den Pfad Hamilton wegen Angluin und Valiant (1977) auf diese ziemlich gut, sogar obwohl es keinen Beweis für nicht zufällige Graphen gibt. Hier ist ein Beispielquadrat

99 98 101 103 105 106 129 132 133 140 135 136 
    97 100 102 104 107 130 131 128 141 134 139 137 
    95 96 109 108 112 122 127 126 125 142 143 138 
    80 94 110 111 121 113 123 124 40 39 36 144 
    79 81 93 120 116 115 114 48 41 38 37 35 
    78 82 92 90 119 117 47 46 49 42 33 34 
    77 83 84 91 89 118 45 58 43 50 32 31 
    76 1 85 87 88 60 59 44 57 51 30 28 
    75 2 86 4 6 63 61 54 52 56 29 27 
    73 74 3 7 5 64 62 53 55 22 24 26 
    72 69 67 8 65 11 12 14 15 23 21 25 
    70 71 68 66 9 10 13 16 17 18 19 20 

und der (etwas hastig geschriebene) Java-Code, der es gemacht hat.