Rompecabezas
N problema de la reina. Coloque n reinas en un tablero de ajedrez en NXN, donde no hay dos reinas en la misma fila, en la misma columna o en la misma diagonal para que no puedan atacarse entre sí.
Estrategia
Método de retroceso.
Solución JavaScript
Tome la pregunta de la 8 reina como ejemplo:
La copia del código es la siguiente:
/**
* Creado por Chao el 28/12/14.
*/
función getNqueens (orden) {
if (orden <4) {
console.log ('n reenens se aplica para un pedido mayor que 3');
devolver;
}
var nqueens = [];
var backtracking = false;
Rowloop:
for (var fila = 0; fila <orden; fila ++) {
if (nqueens [fila] === indefinido) {
nqueens [fila] = [];
}
para (var col = 0; col <orden; col ++) {
if (nqueens [fila] [col] === 0) {
continuar;
} else if (backtracking && nqueens [fila] [col] == 1) {
if (col === orden-1) {
Resetrow (nqueens, orden, fila);
fila = fila - 2;
continuar rowloop;
}
nqueens [fila] [col] = 0;
backtracking = false;
continuar;
}
nqueens [fila] [col] = 1;
if (isQueenvalid (nqueens, row, col)) {
continuar rowloop;
} else if (col == orden-1) {
backtracking = true;
Resetrow (nqueens, orden, fila);
fila = fila - 2;
continuar rowloop;
} demás {
nqueens [fila] [col] = 0;
continuar;
};
}
}
devolver nqueens;
}
function Resetrow (nqueens, orden, fila) {
para (var col = 0; col <orden; col ++) {
nqueens [fila] [col] = undefined;
}
}
función isQueenválida (nqueens, fila, col) {
para (var i = 0; i <col; i ++) {
if (nqueens [fila] [i] == 1) {
devolver falso;
}
}
para (var j = 1; j <fila+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)) {
devolver falso;
}
}
devolver verdadero;
}
function printqueens (Queens) {
for (var fila = 0; fila <Queens.length; row ++) {
var rowtext = '';
para (var col = 0; col <Queens.length; col ++) {
if (Queens [fila] [col] === Undefined) {
Queens [fila] [col] = 0;
}
RowText = RowText + Queens [fila] [col] + '';
}
console.log (RowText);
}
}
var Queens = getNqueens (8);
printqueens (reinas);
resultado
La copia del código es la siguiente:
1 0 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 1 0
0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0