Implémentation JavaScript de l'algorithme de problème N Queens puzzle solution_javascript skills

Puzzle

Problème N Queen. Placez N reines sur un échiquier NxN où il n'y a pas deux reines dans la même rangée, colonne ou diagonale afin qu'elles ne puissent pas s'attaquer.

Stratégie

Méthode de retour en arrière.

Solution JavaScript

Prenons l'exemple du problème des 8 Dames :

Copier le code Le code est le suivant :

/**
 * Créé par cshao le 28/12/14.
 */

fonction getNQueens(ordre) {
si (commande < 4) {
console.log('Le problème N Queens s'applique aux commandes supérieures à 3');
Retour ;
>

var nQueens = [];
var backTracking = false;
rowLoop :
pour (var rangée=0; rangée Si (nQueens[row] === non défini) {
nReines[ligne] = [];
>

pour (var col=0; col Si (nQueens[row][col] === 0) {
Continuer ;
} else if (backTracking && nQueens[row][col] == 1) {
Si (col === commande-1) {
              resetRow(nQueens, order, row);
             rangée = rangée - 2 ;
                 continuer rowLoop ;
>
nReines[ligne][col] = 0;
         backTracking = false;
Continuer ;
>
       
nReines[ligne][col] = 1;
Si (isQueenValid(nQueens, ligne, col)) {
Continuer rowLoop;
} else if (col == order-1) {
backTracking = vrai;
          resetRow(nQueens, order, row);
           rangée = rangée - 2 ;
Continuer rowLoop;
} autre {
nReines[ligne][col] = 0;
Continuer ;
};
>
>

renvoie nQueens ;
>

function resetRow(nQueens, order, row) {
pour (var col=0; col nQueens[row][col] = undefined;
>
>

fonction isQueenValid(nQueens, ligne, col) {
pour (var i=0; i Si (nQueens[row][i] == 1) {
Renvoie faux ;
>
>
pour (var j=1; j if (nQueens[row-j][col]==1 || (nQueens[row-j][col-j]!=undefined && nQueens[row-j][col-j]==1) || ( nQueens[row-j][col j]!=undéfini && nQueens[row-j][col j]==1)) {
Renvoie faux ;
>
>
renvoie vrai ;
>

fonction printQueens(reines) {
pour (var rangée=0; rangée var rowText = '';
pour (var col=0; col Si (queens[row][col]===undefined) {
Reines[ligne][col] = 0;
>
rowText = rowText reines[row][col] ' ';
>
console.log(rowText);
>
>

var reines = getNQueens(8);
printQueens(reines);

Résultats

Copier le code Le code est le suivant :

1  0  0  0  0  0  0  0 
0  0  0  0  1  0  0  0 
0  0  0  0  0  0  0  1 
0  0  0  0  0  1  0  0 
0  0  1  0  0  0  0  0 
0  0  0  0  0  0  1  0 
0  1  0  0  0  0  0  0 
0  0  0  1  0  0  0  0