Quebra-cabeça
N Problema da Rainha. Coloque N Queens em uma tábua de xadrez no NXN, onde não há duas rainhas na mesma linha, na mesma coluna ou na mesma diagonal para que não possam se atacar.
Estratégia
Método de backtracking.
Solução JavaScript
Tome a pergunta da 8 Queen como exemplo:
A cópia do código é a seguinte:
/**
* Criado por Chao em 28/12/14.
*/
função getNqueens (ordem) {
if (ordem <4) {
console.log ('N Queens Problem se aplica a ordem maior que 3');
retornar;
}
var nQueens = [];
var backtracking = false;
Rowloop:
for (var linha = 0; linha <ordem; linha ++) {
if (nqueens [linha] === indefinido) {
nqueens [linha] = [];
}
for (var col = 0; col <ordem; col ++) {
if (nqueens [linha] [col] === 0) {
continuar;
} else if (backtracking && nqueens [linha] [col] == 1) {
if (col === order-1) {
retrow (nqueens, ordem, linha);
linha = linha - 2;
Continue Rowloop;
}
nqueens [linha] [col] = 0;
tracktracking = false;
continuar;
}
nqueens [linha] [col] = 1;
if (isQueenValid (Nqueens, Row, Col)) {
Continue Rowloop;
} else if (col == order-1) {
tracktracking = true;
retrow (nqueens, ordem, linha);
linha = linha - 2;
Continue Rowloop;
} outro {
nqueens [linha] [col] = 0;
continuar;
};
}
}
Retornar Nqueens;
}
Função Resetrow (Nqueens, Order, Row) {
for (var col = 0; col <ordem; col ++) {
nqueens [linha] [col] = indefinido;
}
}
função isQueenValId (Nqueens, Row, Col) {
for (var i = 0; i <col; i ++) {
if (nqueens [linha] [i] == 1) {
retornar falso;
}
}
for (var j = 1; j <linha+1; j ++) {
if (nqueens [line-j] [col] == 1 || (nqueens [line-j] [col-j]! = indefinido && nqueens [line-j] [col-j] == 1) || (nqueens [linhas-j] [col+j]!
retornar falso;
}
}
retornar true;
}
função printqueens (rainhas) {
for (var linha = 0; linha <Queens.length; Row ++) {
var rowText = '';
for (var col = 0; col <Queens.length; col ++) {
if (rainhas [linha] [col] === indefinido) {
rainhas [linha] [col] = 0;
}
rowText = rowText + rainhas [linha] [col] + '';
}
console.log (rowText);
}
}
var queens = getNqueens (8);
printqueens (rainhas);
resultado
A cópia do código é a seguinte:
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1
0 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