JavaScript-Implementierung der N-Queens-Problemalgorithmus-Rätsellösung_Javascript-Fähigkeiten

Rätsel

N-Queen-Problem. Platzieren Sie N Damen auf einem NxN-Schachbrett, wobei sich keine zwei Damen in derselben Reihe, Spalte oder Diagonale befinden, damit sie sich nicht gegenseitig angreifen können.

Strategie

Backtracking-Methode.

JavaScript-Lösung

Nehmen Sie das 8-Damen-Problem als Beispiel:

Code kopieren Der Code lautet wie folgt:

/**
 * Erstellt von cshao am 28.12.14.
 */

Funktion getNQueens(order) {
if (order < 4) {
console.log('N Queens-Problem gilt für Bestellungen größer als 3');
Zurück;
}

var nQueens = [];
var backTracking = false;
rowLoop:
for (var row=0; row If (nQueens[row] === undefiniert) {
nQueens[row] = [];
}

für (var col=0; col If (nQueens[row][col] === 0) {
Weiter;
} else if (backTracking && nQueens[row][col] == 1) {
If (col === order-1) {
              resetRow(nQueens, order, row);
             Zeile = Zeile - 2;
                 continue rowLoop;
}
nQueens[row][col] = 0;
         backTracking = false;
Weiter;
}
       
nQueens[row][col] = 1;
If (isQueenValid(nQueens, row, col)) {
Weiter rowLoop;
} else if (col == order-1) {
backTracking = true;
          resetRow(nQueens, order, row);
           Zeile = Zeile - 2;
Weiter rowLoop;
} sonst {
nQueens[row][col] = 0;
Weiter;
};
}
}

nQueens zurückgeben;
}

Funktion resetRow(nQueens, order, row) {
for (var col=0; col nQueens[row][col] = undefiniert;
}
}

Funktion isQueenValid(nQueens, row, col) {
für (var i=0; i If (nQueens[row][i] == 1) {
Gibt false zurück;
}
}
für (var j=1; j if (nQueens[row-j][col]==1 || (nQueens[row-j][col-j]!=undefiniert && nQueens[row-j][col-j]==1) || ( nQueens[row-j][col j]!=undefiniert && nQueens[row-j][col j]==1)) {
Gibt false zurück;
}
}
return true;
}

Funktion printQueens(queens) {
for (var row=0; row var rowText = '';
for (var col=0; col If (queens[row][col]===undefiniert) {
Queens[row][col] = 0;
}
rowText = rowText queens[row][col] ' ';
}
console.log(rowText);
}
}

var queens = getNQueens(8);
printQueens(Königinnen);

Ergebnisse

Code kopieren Der Code lautet wie folgt:

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