In Bezug auf die JavaScript -Lösung für das acht Queens -Problem habe ich immer das Gefühl, dass ich den Algorithmus lernen muss. Es wird peinlich sein, herauszufinden, ob ich es eines Tages benutze.
Hintergrund
Die acht Queens -Frage ist eine Frage, die auf Schach basiert: Wie können acht Königinnen auf das 8 × 8 -Schachbrett platziert werden, damit keine Königin die anderen Königinnen direkt essen kann? Um dies zu erreichen, kann sich keine Königin in der gleichen horizontalen, vertikalen oder diagonalen Linie befinden
Das acht Queens -Problem kann auf das allgemeinere Problem der Platzierung von N -Königin verallgemeinert werden: Zu diesem Zeitpunkt wird die Größe des Schachbretts N × N, und die Anzahl der Königinnen wird auch n. Wenn und nur wenn n = 1 oder n ≥ 4 eine Lösung für das Problem gibt
Blind Aufzählungalgorithmus
Durch n-fache Schleifen, die Lösungen aufzählen, die die Einschränkungen erfüllen (es werden viele achtfache Schleifencodes erfolgen, hier werden vierfache Schleifen durchgeführt), finden Sie alle möglichen Positionen der vier Königinnen und beurteilen dann in der gesamten Board, ob diese vier Königinnen sich direkt essen. Die Programmidee ist relativ einfach.
Funktion check1 (arr, n) {für (var i = 0; i <n; i ++) {für (var j = i+1; j <n; j ++) {if ((arr [i] == arr [j]) || math.abs (arr [i] - arr [j]) == j - i) {return caus return; }}} return true;} function Queen1 () {var arr = []; für (arr [0] = 1; arr [0] <= 4; arr [0] ++) {für (arr [1] = 1; arr [1] <= 4; arr [1] ++) {für (arr [2] = 1; 1; arr [2] <= 4; arr [2] ++) {für (arr [3] arr [3] 4; weitermachen; } else {console.log (arr); } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}In Bezug auf das Ergebnis können im 4*4 -Schachbrett die vier Königinnen nicht in einer Reihe sein. arr [0] bis arr [3] entspricht den vier Königinnen. Der Wert, der dem Einweis des Arrays und des Indexs entspricht, ist die Position der Königin im Vorstand.
Backtracking -Methode
"Wenn du nicht gehen kannst, dreh dich einfach um." Bestimmen Sie, ob es am entsprechenden Knoten entspricht. Wenn es nicht übereinstimmt, werden Sie diesen Zweig nicht mehr erforschen.
Funktion check2 (arr, n) {für (var i = 0; i <= n - 1; i ++) {if ((math.abs (arr [i] - arr [n]) == n - i) || (arr [i] == arr [n]) {return false; }} return true;} function Queen2 () {var arr = []; für (arr [0] = 1; arr [0] <= 4; arr [0] ++) {für (arr [1] = 1; arr [1] <= 4; arr [1] ++) {if (! check2 (arr, 1)) Fortsetzung; // Geben Sie den Konflikt zwischen zwei Queens für (arr [2] = 1; arr [2] <= 4; arr [2] ++) {if (! Check2 (arr, 2)) fort. Weiter; // Geben Sie den Konflikt zwischen drei Queens für (arr [3] = 1; arr [3] <= 4; arr [3] ++) {if (! Check2 (arr, 3)) {fort; } else {console.log (arr); } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }}}}}}}}}}}}}}}Nicht rekursives Backtracking
Algorithmus Framework:
Während (k> 0 『Es gibt einen Weg,』 und 『nicht das Ziel zu erreichen』) {// k> 0 『Es gibt einen Weg zu gehen, wenn (k> n) {// nach Blattknoten sucht // nach einer Lösung suchen, Ausgabe} else {// a [k] Der erste Wert, der (" a [k] in der Suche in der Suche in der Suchraum "). Space ") {// markieren Sie die besetzte Ressource // k = k + 1; } else {// den besetzten Zustandsraum aufräumen // k = k - 1; }}}Der spezifische Code ist wie folgt. Die äußerste Schicht enthält zwei Teile. Einer ist ein Traversal der möglichen Werte der aktuellen Königin, und das andere ist eine Entscheidung, ob die nächste Schicht eingeben oder die vorherige Schicht zurückverfolgen soll.
Funktion backdate (n) {var arr = []; var k = 1; // die n -te Königin arr [0] = 1; while (k> 0) {arr [k-1] = arr [k-1] + 1; while ((arr [k-1] <= n) && (! check2 (arr, k-1)) {arr [k-1] = arr [k-1] + 1; } // Diese Königin erfüllt die Einschränkungen und macht das nächste Urteil, wenn (arr [k-1] <= n) {if (k == n) {// die n-te Königin-Konsole.log (arr); } else {k = k + 1; // Die nächste Königin arr [k-1] = 0; }} else {k = k - 1; // Backtrack, letzte Königin}}} Backdate (4); // [2, 4, 1, 3] // [3, 1, 4, 2]Rekursive Backtracking -Methode
Rekursive Anrufe reduzieren die Codemenge erheblich und erhöhen Sie die Lesbarkeit des Programms.
var arr = [], n = 4; Funktion backtrack (k) {if (k> n) {console.log (arr); } else {für (var i = 1; i <= n; i ++) {arr [k-1] = i; if (check2 (arr, k-1)) {backtrack (k + 1); }}}}} Backtrack (1); // [2, 4, 1, 3] // [3, 1, 4, 2]Wunderschöne Amb
Was ist Amb? Geben Sie ihm eine Datenliste, die eine Möglichkeit zurückgeben kann, die Erfolgssituationen der Einschränkungen zu erfüllen. Ohne Erfolg wird es scheitern. Natürlich kann es alle Erfolgssituationen zurückgeben. Der Autor hat so viele Punkte oben geschrieben, nur um diesen ABB -Algorithmus hier zu empfehlen. Es eignet sich zum Umgang mit einfachen Backtracking -Szenarien. Es ist sehr interessant. Mal sehen, wie es funktioniert.
Lassen Sie uns zunächst mit einem kleinen Problem umgehen, benachbarte Zeichenfolgen finden: Holen Sie sich mehrere Sätze von String -Arrays, und jedes Array nimmt eine Zeichenfolge heraus. Das letzte Zeichen der vorherigen Zeichenfolge entspricht dem ersten Zeichen der nächsten Zeichenfolge. Wenn die Bedingungen erfüllt sind, werden die neu abgerufenen Zeichenfolgen ausgegeben.
Ambrun (Funktion (Amb, Fail) {// Einschränkungsmethode mit verknüpfter Methode (S1, S2) {return s1.slice (-1) == S2.Slice (0, 1);} // Datenliste injizieren var w1 = amb (["The", "das", "a"]; "Preed", "wächst"]; langsam"});Es sieht super einfach aus oder nicht! Die Prämisse der Verwendung ist jedoch, dass Sie sich nicht um Leistung kümmern, es ist wirklich Zeitverschwendung!
Nachfolgend finden Sie seine JavaScript -Implementierung. Wenn Sie interessiert sind, können Sie untersuchen, wie es Backtracking extrahiert.
Funktion Ambrun (func) {var choices = []; var Index; Funktion amb (values) {if (values.length == 0) {fail (); } if (index == Choices.length) {Choices.push ({i: 0, count: values.length}); } var choice = Auswahl [Index ++]; Rückgabewerte [Auswahl.I]; } function fail () {throw fail; } while (true) {try {index = 0; return func (amb, scheitern); } catch (e) {if (e! = fail) {throw e; } var Choice; while ((choice = choips.pop ()) && ++ choice } Choices.push (Auswahl); }}}Und den spezifischen Code des acht Queens -Problems, das mit AMB implementiert wurde
Ambrun (function (amb, fail) {var n = 4; var arr = [] []; var turn = []; für (var n = 0; n <n; n; n ++) {Turn [Turn.Length] = n +1;} while (n-) {arr [Arr.Length] = Amb (Turn);} für (var i = 0; i = 0) {{++ i ++ i ++ i ++ i ++ i. var a = arr [i], b = arr [j];JavaScript -Lösung für das acht Queens -Problem
Dies ist die JavaScript -Lösung für das acht Queens -Problem. Das gesamte Programm wird nicht für Schleifen verwendet und wird durch Rekursion implementiert. Es wird die Karte, reduziert, filtert, concat, Slice -Methoden des Array -Objekts reduziert, beschleunigt.
'strict'; var queens = function (boardersize) {// Verwenden Sie eine Rekursion, um ein Array -VAR -Intervall von start bis end = function (start, ende) {if (start> end) {return []; } Rückgabeintervall (Start, Ende - 1) .Concat (Ende); }; // Überprüfen Sie, ob eine Kombination gültig ist. if ((0 === Steigung) || (1 === Steigung) || (-1 === Steigung)) {return false; } Return true; }; var len = queencol.length; var pointTocompare = {row: queencol [len - 1], col: len}; // STRAG IST ZUSAMMEN DAS ARAY mit Ausnahme der letzten Spalte und dann testen Sie, ob ein Konflikt zwischen den Punkten in jeder Spalte und den zu testenden Punkten besteht, und verschmelzen schließlich die Testergebnisse. Return queencol .slice (0, len - 1) .MAP (Funktion (Zeile, Index) {return issafe ({row: row, col: index + 1}, pointTocompare);}) .Reduce (Funktion (a, b) {return a && b;}); }; // Generieren Sie rekursiv Kombinationen, die den Regeln entsprechen var queencols = function (Größe) {if (1 === Größe) {Rückgabeintervall (1, boarderSize) .MAP (Funktion (i) {return [i];}); } // Erweitern Sie zuerst den Satz aller früheren Spalten, die den Regeln entsprechen, und verwenden Sie dann die Reduzierung der Dimensionalität und verwenden schließlich Isvalid, um Kombinationen herauszufiltern, die den Regeln entsprechen. Return Queencols (Größe - 1). (a, b) {return a.concat (b); }; // queens function entry return queenCols(boarderSize);};console.log(queens(8));// Output result:// [ [ 1, 5, 8, 6, 3, 7, 2, 4 ],// [ 1, 6, 8, 3, 7, 4, 2, 5 ],// ...// [ 8, 3, 1, 6, 2, 5, 7, 4 ],// [ 8, 4, 1, 3, 6, 2, 7, 5]]PS: Erweitertes N -Königin -Problem
Als der Schachspieler Max Bezzel 1848 das Puzzle von acht Queens fragte, dachte er wahrscheinlich nie, dass dieses Problem mehr als 100 Jahre später zu einem der wichtigsten obligatorischen Kurse beim Programmieren von Lernen wurde. Das Problem mit acht Queens klingt sehr einfach: Legen Sie die acht Queens auf das Schachbrett, damit die acht Königinnen sich nicht angreifen (die Schachbrett ist ein 8 × 8 -Quadrat -Array, und die Königin kann horizontal und vertikal mehrere Schritte in einer der acht Anweisungen unternehmen). Obwohl dieses Problem 92 Lösungen gibt, ist es nicht einfach, eine Lösung mit bloßen Händen zu finden. Die folgende Abbildung ist eine der Lösungen:
Es gibt viele Varianten des acht Queens -Problems, aber egal wie schwer es ist, es wird nicht gutaussehender als die folgende Variante: Bitte entwerfen Sie einen Plan, um eine Königin in jede Reihe und jede Spalte eines unendlichen Schachbretts zu platzieren, damit sich alle Königinnen nicht angreifen. Angenommen, die untere linke Ecke dieses Platine befindet sich im Ursprung, mit unendlichen Reihen von unten nach oben und unendlichen Säulen von links nach rechts müssen Sie die Anordnung aller positiven Zahlen A1, A2, A3 herausfinden.
Hier ist eine sehr einfache und clevere Konstruktion. Erstens geben wir eine Antwort auf das Fünf -Queens -Problem. Und sehr wichtig ist, dass eine der Königinnen das Netz in der unteren linken Ecke nimmt.
Als nächstes erweitern wir die Lösung der fünf Königinnen auf die 25 Queens und basieren auf dem Layout der fünf Queens selbst:
Infolgedessen werden sich die fünf Königinnen in derselben Gruppe offensichtlich nicht gegenseitig angreifen, und die Königinnen in verschiedenen Gruppen werden sich offensichtlich nicht gegenseitig angreifen. Dies ist eine 25 -Königin -Lösung, die den Anforderungen entspricht. Beachten Sie, dass sich der zuvor ausgefüllte Abschnitt nach der Erweiterung nicht geändert hat.
Was soll ich als nächstes tun? Das ist richtig, wir haben die 25 Queen's Unblocking in fünf Teile kopiert und sie nach dem Layout der fünf Königinnen erneut arrangiert, wodurch sich auf 125 Königinnen ausdehnte!
Indem Sie sich ständig nach außen ausdehnen, können Sie eine Lösung für das Problem der unendlichen Königin erzeugen.