Puzzle
N Problème de la reine. Placez N queens sur une planche d'échecs dans NXN, où il n'y a pas deux reines dans la même ligne, dans la même colonne ou dans la même diagonale afin qu'ils ne puissent pas s'attaquer.
Stratégie
Méthode de retour en arrière.
Solution javascript
Prenez la question de la 8 reine comme exemple:
La copie de code est la suivante:
/ **
* Créé par Chao le 28/12/14.
* /
fonction getnqueens (ordre) {
if (ordre <4) {
Console.log («N Queens Problème Appliquez une commande supérieure à 3»);
retour;
}
var nqueens = [];
var backtracking = false;
Rowloop:
pour (var row = 0; row <order; row ++) {
if (nqueens [row] === Undefined) {
nqueens [row] = [];
}
pour (var col = 0; col <ordonnance; col ++) {
if (nqueens [row] [col] === 0) {
continuer;
} else if (backtracking && nqueens [row] [col] == 1) {
if (col === ORDER-1) {
Resetrow (nqueens, ordre, rang);
row = ligne - 2;
continuer Rowloop;
}
nqueens [row] [col] = 0;
BackTracking = false;
continuer;
}
nqueens [row] [col] = 1;
if (isQueenValid (nqueens, row, col)) {
continuer Rowloop;
} else if (col == ordre-1) {
BackTracking = true;
Resetrow (nqueens, ordre, rang);
row = ligne - 2;
continuer Rowloop;
} autre {
nqueens [row] [col] = 0;
continuer;
};
}
}
retour nqueens;
}
fonction restrow (nqueens, ordre, ligne) {
pour (var col = 0; col <ordonnance; col ++) {
nqueens [row] [col] = non défini;
}
}
fonction isQueenValid (nqueens, row, col) {
pour (var i = 0; i <col; i ++) {
if (nqueens [row] [i] == 1) {
retourne false;
}
}
pour (var j = 1; j <row + 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]! = Undefined && nqueens [row-j] [col + j] == 1)) {
retourne false;
}
}
Retour Vrai;
}
fonction printqueens (reines) {
pour (var row = 0; row <queens.length; row ++) {
var rowText = '';
pour (var col = 0; col <queens.length; col ++) {
if (Queens [row] [col] === Undefined) {
Queens [Row] [col] = 0;
}
RowText = RowText + Queens [Row] [Col] + '';
}
console.log (RowText);
}
}
var Queens = getnqueens (8);
printqueens (reines);
résultat
La copie de code est la suivante:
1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0