En ce qui concerne la solution JavaScript au problème des huit reines, je pense toujours que j'ai besoin d'apprendre l'algorithme. Ce sera gênant de savoir si je l'utilise un jour.
arrière-plan
La question des huit reines est une question basée sur les échecs: comment huit reines peuvent-elles être placées sur la planche d'échecs 8 × 8 afin qu'aucune reine ne puisse manger les autres reines directement? Pour y parvenir, aucune reine ne peut être dans la même ligne horizontale, verticale ou diagonale
Le problème des huit reines peut être généralisé au problème le plus général du placement de N Queen: à ce moment, la taille de l'échecteur devient n × n, et le nombre de reines devient également n. Si et seulement si n = 1 ou n ≥ 4, il y a une solution au problème
Algorithme d'énumération aveugle
Grâce à des boucles de Npolt, en énumérant des solutions qui répondent aux contraintes (il existe de nombreux codes de boucle huit fois, des boucles quatre fois sont effectuées ici), trouvent toutes les positions possibles des quatre reines, puis jugez dans l'ensemble du conseil d'administration si ces quatre reines se mangeront directement. L'idée du programme est relativement simple.
Fonction Check1 (arr, n) {for (var i = 0; i <n; i ++) {for (var j = i + 1; j <n; j ++) {if ((arr [i] == arr [j]) || math.abs (arr [i] - arr [j]) == j - i) {return false; }}} return true;} fonction queen1 () {var arr = []; pour (arr [0] = 1; arr [0] <= 4; arr [0] ++) {pour (arr [1] = 1; arr [1] <= 4; arr [1] ++) {pour (arr [2] = 1; arr [2] <= 4; arr [2] ++) {pour (pour (3] = 1; arr [3] <= 4; arr [3] ++) continuer; } else {console.log (arr); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}, }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}, }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}, }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}En ce qui concerne le résultat, dans les échecs 4 * 4, les quatre reines ne peuvent pas être consécutives. arr [0] à arr [3] correspondent respectivement aux quatre reines respectivement. La valeur correspondant à l'indice du tableau et de l'indice est la position de la reine au conseil d'administration.
Méthode de retour en arrière
"Si vous ne pouvez pas y aller, retournez-vous." Déterminez s'il correspond au nœud approprié. Si cela ne correspond pas, vous n'explorerez plus cette branche.
Fonction Check2 (arr, n) {for (var i = 0; i <= n - 1; i ++) {if ((math.abs (arr [i] - arr [n]) == n - i) || (arr [i] == arr [n])) {return false; }} return true;} fonction queen2 () {var arr = []; pour (arr [0] = 1; arr [0] <= 4; arr [0] ++) {pour (arr [1] = 1; arr [1] <= 4; arr [1] ++) {if (! check2 (arr, 1)) continue; // Indiquez le conflit entre deux reines pour (arr [2] = 1; arr [2] <= 4; arr [2] ++) {if (! Check2 (arr, 2)) continuer; // Indiquez le conflit entre trois reines pour (arr [3] = 1; arr [3] <= 4; arr [3] ++) {if (! Check2 (arr, 3)) {Continuer; } else {console.log (arr); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}, }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}, }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}, }}}}}}}}}}}}}}Backtracking non réécursif
Framework d'algorithme:
tandis que (k> 0 『il existe un moyen d'aller』 et 『non atteint l'objectif』) {// k> 0 『Il existe un moyen de suivre si (k> n) {// recherche des nœuds de feuilles // recherche d'une solution, sortie} else {// a [k] la première valeur possible tandis que (" k] est dans l'espace de recherche ") {// a [k] la valeur suivante. Espace ") {// Marquez la ressource occupée // K = K + 1; } else {// Nettoyez l'espace d'état occupé // k = k - 1; }}}Le code spécifique est le suivant. La couche la plus externe tout en contient deux parties. L'un est une traversée des valeurs possibles de la reine actuelle, et l'autre est une décision de saisir la couche suivante ou de revenir en arrière la couche précédente.
Fonction Backdate (n) {var arr = []; var k = 1; // la nième reine 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; } // Cette reine satisfait les contraintes et fait le jugement suivant if (arr [k-1] <= n) {if (k == n) {// la Nth Queen Console.log (arr); } else {k = k + 1; // la prochaine reine arr [k-1] = 0; }} else {k = k - 1; // BackTrack, Last Queen}}} Backdate (4); // [2, 4, 1, 3] // [3, 1, 4, 2]Méthode de retour en arrière récursive
Les appels récursifs réduisent considérablement la quantité de code et augmentent la lisibilité du programme.
var arr = [], n = 4; fonction Backtrack (k) {if (k> n) {console.log (arr); } else {for (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]Magnifique Amb
Qu'est-ce que Amb? Donnez-lui une liste de données, qui peut renvoyer un moyen de respecter les situations de réussite des contraintes. Sans succès, il échouera. Bien sûr, il peut retourner toutes les situations de réussite. L'auteur a écrit tant de points ci-dessus, juste pour recommander cet algorithme AMB ici. Il convient à la gestion des scénarios de retour de retour en arrière simple. C'est très intéressant. Voyons comment cela fonctionne.
Tout d'abord, traitons avec un petit problème, trouvez des chaînes adjacentes: obtenez plusieurs ensembles de tableaux de chaîne et chaque tableau supprime une chaîne. Le dernier caractère de la chaîne précédente est le même que le premier caractère de la chaîne suivante. Si les conditions sont remplies, les chaînes nouvellement récupérées seront sorties.
Ambrun (fonction (amb, échec) {// Méthode de contrainte Fonction Linée (S1, S2) {return S1.slice (-1) == S2.slice (0, 1);} // injecter la liste des données var w1 = amb (["le", "que", "A"]; var w2 = amb ("frog", "elephant", "thing"]); "Tread", "Grows"];Il a l'air super simple ou non! Cependant, la prémisse de l'utilisation est que vous ne vous souciez pas des performances, c'est vraiment une perte de temps!
Vous trouverez ci-dessous son implémentation JavaScript. Si vous êtes intéressé, vous pouvez étudier comment il extrait le retour en arrière.
fonction ambrun (func) {var choix = []; var index; fonction amb (valeurs) {if (valeurs.length == 0) {fail (); } if (index == Choices.Length) {Choices.push ({i: 0, count: valeurs.length}); } var choix = choix [index ++]; Valeurs de retour [Choice.i]; } function fail () {throw fail; } while (true) {try {index = 0; retourner func (amb, échec); } catch (e) {if (e! = fail) {throw e; } var choix; while ((choix = choix.pop ()) && ++ Choice.i == Choice.Count) {} if (choix == Undefined) {return undefined; } Choices.push (choix); }}}Et le code spécifique du problème des huit reines implémenté en utilisant Amb
Ambrun (fonction (amb, échec) {var n = 4; var arr = []; var tour = []; for (var n = 0; n <n; n ++) {tour [Turn.length] = n + 1;} while (n--) {arr.length] = amb (tour);} pour (var i = 0; i <n; ++ i) {pour (var j = i + 1; var a = arr [i], b = arr [j];Solution JavaScript au problème des huit reines
Il s'agit de la solution JavaScript au problème des huit reines. L'ensemble du programme n'utilise pas pour les boucles et est implémenté par récursivité. Il utilise pleinement la carte, réduisez, filtrez, concat, tranche des méthodes de l'objet de tableau.
'utiliser strict'; var queens = function (boarderSize) {// Utilisez la récursivité pour générer un intervalle var du tableau de début à fin = fonction (start, end) {if (start> end) {return []; } Intervalle de retour (start, end - 1) .Concat (end); }; // Vérifiez si une combinaison est valide var isvalid = fonction (Queencol) {// Vérifiez s'il existe un conflit entre deux positions var issaFe = fonction (Pointa, PointB) {var slope = (Pointa.Row - PointB.Row) / (Pointa.col - PointB.Col); if ((0 === pente) || (1 === Slope) || (-1 === Slope)) {return false; } return true; }; var len = queencol.length; var PointtoCompare = {row: Queencol [len - 1], col: len}; // Tranchez d'abord le tableau sauf la dernière colonne, puis testez s'il existe un conflit entre les points de chaque colonne et les points à tester, et enfin fusionner les résultats du test. Return Queencol .slice (0, len - 1) .map (function (row, index) {return issafe ({row: row, col: index + 1}, pointtocompare);}) .reduce (function (a, b) {return a && b;}); }; // Générez récursivement des combinaisons conformes aux règles var queencols = fonction (taille) {if (1 === taille) {return interval (1, boardersize) .map (function (i) {return [i];}); } // Développez d'abord l'ensemble de toutes les colonnes précédentes conformes aux règles, puis utilisez la réduction de la réduction de la dimensionnalité et utilisez enfin Isvalid pour filtrer les combinaisons conformes aux règles Return Queencols (taille - 1) .map (fonction (Queencol) {return interal (a, b) {return a.concat (b);}) .filter (isvalid); }; // 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: Problème étendu et reine
Lorsque le joueur d'échecs Max Bezzel a demandé au puzzle des huit reines en 1848, il n'a probablement jamais pensé que plus de 100 ans plus tard, ce problème est devenu l'un des cours obligatoires les plus importants de l'apprentissage de la programmation. Le problème des huit reines semble très simple: mettez les huit reines sur la planche d'échecs afin que les huit reines ne s'attaquent pas (la planche d'échecs est un réseau carré 8 × 8, et la reine peut prendre plusieurs étapes dans l'une des huit directions horizontalement et verticalement). Bien qu'il existe 92 solutions à ce problème, il n'est pas facile de trouver une solution à mains nues. Le chiffre suivant est l'une des solutions:
Il existe de nombreuses variantes du problème des huit reines, mais peu importe à quel point il est difficile, il ne sera pas plus beau que la variante suivante: veuillez concevoir un plan pour placer une reine dans chaque ligne et chaque colonne d'un échec infini, afin que toutes les reines ne s'attaquent pas. Plus précisément, supposons que le coin inférieur gauche de cette planche soit à l'origine, avec des lignes infinies du bas en haut et des colonnes infinies de gauche à droite, vous devez découvrir l'arrangement de tous les entiers positifs A1, A2, A3, ... de sorte que lorsque vous placez la première reine de la première ligne dans la colonne A1, la deuxième reine de la colonne A2, etc., puis pas deux reines ne s'attaqueront à toutes les autres.
Voici une construction très simple et intelligente. Tout d'abord, nous donnons une réponse au problème des cinq reines. Et très important, l'une des reines occupe la grille dans le coin inférieur gauche.
Ensuite, nous élargissons la solution des cinq reines aux 25 reines, et sur la base de la disposition des cinq reines elle-même:
En conséquence, les cinq reines du même groupe ne s'attaqueront évidemment pas, et les reines de différents groupes ne s'attaqueront évidemment pas. Il s'agit d'une solution de 25 reine qui répond aux exigences. Notez qu'après l'expansion, la section précédemment remplie n'a pas changé.
Que dois-je faire ensuite? C'est vrai, nous avons copié le déblocage des 25 reine en cinq pièces et l'avons arrangée à nouveau selon la disposition des cinq reines, s'étendant ainsi à 125 reines!
En se développant constamment vers l'extérieur en fonction des pièces remplies comme celle-ci, vous pouvez générer une solution au problème de la reine infinie.