Em relação à solução JavaScript para o problema do oito rainhas, sempre sinto que preciso aprender o algoritmo. Será embaraçoso descobrir se eu o usar um dia.
fundo
A pergunta do oito rainhas é uma pergunta baseada no xadrez: como oito rainhas podem ser colocadas no quadro de xadrez 8 × 8 para que nenhuma rainha possa comer as outras rainhas diretamente? Para conseguir isso, nenhuma rainha pode estar na mesma linha horizontal, vertical ou diagonal
O problema do oito rainhas pode ser generalizado para o problema mais geral da colocação da rainha: nesse momento, o tamanho do tabuleiro de xadrez se torna n × n, e o número de rainhas também se torna n. Se e somente se n = 1 ou n ≥ 4 existe uma solução para o problema
Algoritmo de enumeração cega
Através de loops N-dobráveis, enumeram soluções que atendem às restrições (existem muitos códigos de loop de oito vezes, os loops de quatro vezes são realizados aqui), encontre todas as posições possíveis das quatro rainhas e, em seguida, julgam em toda a placa se essas quatro rainhas se comerão diretamente. A ideia do programa é relativamente simples.
função check1 (arr, n) {for (var i = 0; i <n; i ++) {for (var j = i+1; j <n; j ++) {if ((arr [i] == arr [j]) || math.abs (arr [i] - arr [j]) == j - i) {return false; }}} retornar true;} função queen1 () {var arr = []; para (arr [0] = 1; arr [0] <= 4; arr [0] ++) {for (arr [1] = 1; arr [1] <= 4; arr [1] ++) {for (arr [2] = 1; arr [2] <= 4; Arr [2] ++) {para (arr [3] = 1; continuar; } else {console.log (arr); } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}Em relação ao resultado, no quadro de xadrez 4*4, as quatro rainhas não podem ser seguidas. arr [0] para arr [3] corresponde às quatro rainhas, respectivamente. O valor correspondente ao subscrito da matriz e do subscrito é a posição da rainha no conselho.
Método de backtracking
"Se você não puder ir, basta virar." Determine se ele corresponde ao nó apropriado. Se não corresponder, você não explorará mais esta filial.
função check2 (arr, n) {for (var i = 0; i <= n - 1; i ++) {if ((math.abs (arr [i] - arr [n]) == n - i) || (arr [i] == arr [n]) {return false; }} retornar true;} função queen2 () {var arr = []; para (arr [0] = 1; arr [0] <= 4; arr [0] ++) {for (arr [1] = 1; arr [1] <= 4; arr [1] ++) {if (! check2 (arr, 1)) continue; // Declare o conflito entre duas rainhas para (arr [2] = 1; arr [2] <= 4; arr [2] ++) {if (! Check2 (arr, 2)) continue; // Declare o conflito entre três rainhas para (arr [3] = 1; arr [3] <= 4; arr [3] ++) {if (! Check2 (arr, 3)) {continuação; } else {console.log (arr); } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }}}}}}}}}}}}}}Tracktracking não recursivo
Estrutura de algoritmo:
Enquanto (k> 0 『existe um caminho a seguir』 e 『não atingiu o objetivo』) {// k> 0 『Há um caminho a percorrer se (k> n) {// pesquisa para os nós da folha // pesquisa para uma solução, output} else {// a [k] o primeiro valor possível (" a [k] está no espaço} "{// a [k] o primeiro possível (" a [k] está no espaço} "{// a [k] o primeiro possível (" a [k] está no espaço} {// a [k] o primeiro possível ("a [k] está no space} {// a [k] o que é possível (" a [k]. espaço de pesquisa ") {// marque o recurso ocupado // k = k + 1; } else {// Limpe o espaço de estado ocupado // k = k - 1; }}}O código específico é o seguinte. A camada mais externa enquanto contém duas partes. Um é uma travessia dos possíveis valores possíveis da rainha atual, e o outro é uma decisão se deve entrar na próxima camada ou voltar à camada anterior.
função backdate (n) {var arr = []; var k = 1; // a enésima rainha arr [0] = 1; while (k> 0) {arr [k-1] = arr [k-1] + 1; while ((arr [k-1] <= n) && (! check2 (arr, k-1))) {arr [k-1] = arr [k-1] + 1; } // Esta rainha satisfaz as restrições e faz o próximo julgamento se (arr [k-1] <= n) {if (k == n) {// o enxd queen console.log (arr); } else {k = k + 1; // a próxima rainha arr [k-1] = 0; }} else {k = k - 1; // backtrack, última rainha}}} backdate (4); // [2, 4, 1, 3] // [3, 1, 4, 2]Método de retorno recursivo
As chamadas recursivas reduzem bastante a quantidade de código e aumentam a legibilidade do programa.
var arr = [], n = 4; function backtrack (k) {if (k> n) {console.log (arr); } else {for (var i = 1; i <= n; i ++) {arr [k-1] = i; if (check2 (arr, k-1)) {backtrack (k + 1); }}}}} backtrack (1); // [2, 4, 1, 3] // [3, 1, 4, 2]Lindo Amb
O que é Amb? Dê uma lista de dados, que pode retornar uma maneira de atender às situações de sucesso das restrições. Sem sucesso, isso falhará. Obviamente, ele pode retornar todas as situações de sucesso. O autor escreveu tantos pontos acima, apenas para recomendar este algoritmo AMB aqui. É adequado para lidar com cenários simples de retrocesso. É muito interessante. Vamos ver como funciona.
Primeiro, vamos lidar com um pequeno problema, encontrar strings adjacentes: obtenha vários conjuntos de matrizes de string e cada matriz retira uma string. O último caractere da sequência anterior é o mesmo que o primeiro caractere da próxima string. Se as condições forem atendidas, as strings recém -recuperadas serão emitidas.
Ambrun (função (Amb, Fail) {// Função do método de restrição vinculada (S1, S2) {return s1.slice (-1) == s2.slice (0, 1);} // Lista de dados de injeção var w1 = Amb ("o", "que", "a"]); "pista", "cresce"]; devagar"});Parece super simples ou não! No entanto, a premissa de usar é que você não se importa com o desempenho, é realmente uma perda de tempo!
Abaixo está sua implementação de JavaScript. Se você estiver interessado, pode estudar como ele extrai retrocesso.
function Ambrun (func) {var escolhas = []; Índice var; function AMB (valores) {if (valores.Length == 0) {Fail (); } if (index == Choics.Length) {Choics.push ({i: 0, count: valores.length}); } var escolha = opções [index ++]; Retornar valores [Choice.i]; } função falha () {throw frily; } while (true) {try {index = 0; retornar func (AMB, falha); } catch (e) {if (e! = Fail) {tiro e; } var escolha; while ((Choice = Choices.pop ()) && ++ Choice.i == Choice.Count) {} if (Choice == indefinido) {return indefined; } escolhas.push (escolha); }}}E o código específico do problema do oito rainhas implementado usando AMB
Ambrun (function (Amb, Fail) {var n = 4; var arr = []; var turn = []; para (var n = 0; n <n; n ++) {Turn [Turn.Length] = n +1;} while (n-) {d [arr.length] = (Turn);} para (var i = 0; var a = arr [i], b = arr [j];Solução JavaScript para o problema do oito rainhas
Esta é a solução JavaScript para o problema do oito rainhas. Todo o programa não usa loops e é implementado por meio de recursão. Ele utiliza totalmente o mapa, reduz, filtra, concat, métodos de fatia do objeto de matriz.
'Use Strict'; var queens = function (pensionersize) {// use a recursão para gerar um intervalo de matriz var de start to end = function (start, end, end) {if (start> end) {return []; } intervalo de retorno (Iniciar, final - 1) .CONCAT (END); }; // Verifique se uma combinação é válida var isValid = function (Queencol) {// Verifique se há conflito entre duas posições var issafe = function (Pointe, Pointb) {var slope = (Pointe.Row - Pointb.Row) / (Pointe.col - Pointb.col); if ((0 === SLOPE) || (1 === SLOPE) || (-1 === Slope)) {return false; } retornar true; }; var len = queencol.length; var pointtocompare = {linha: Queencol [len - 1], col: len}; // Primeiro, corte a matriz, exceto a última coluna, depois teste se há um conflito entre os pontos em cada coluna e os pontos a serem testados e finalmente mescla os resultados do teste. Return Queencol .Slice (0, Len - 1) .Map (function (linha, index) {return isSsafe ({{linha: linha, col: índice + 1}, PointTocompare);}) .Reduce (function (a, b) {return a && b;}); }; // gera recursivamente combinações que estão em conformidade com as regras var queencols = function (size) {if (1 === size) {intervalo de retorno (1, pensionersize) .map (function (i) {return [i];}); } // primeiro expandem o conjunto de todas as colunas anteriores que se adaptam às regras, depois use a redução da dimensionalidade e, finalmente, use o ISValid para filtrar as combinações que se adaptam às regras retornam queencols (tamanho 1) .Map (function (queencol) {Return Interval (1, placarsize). (a, b) {return A.Concat (b); }; // queens function entry return queenCols(boarderSize);};console.log(queens(8));// Output result:// [ [ 1, 5, 8, 6, 3, 7, 2, 4 ],// [ 1, 6, 8, 3, 7, 4, 2, 5 ],// ...// [ 8, 3, 1, 6, 2, 5, 7, 4 ],// [ 8, 4, 1, 3, 6, 2, 7, 5]]PS: Problema estendido da rainha
Quando o jogador de xadrez Max Bezzel perguntou ao oito quebra -cabeça do Queens em 1848, ele provavelmente nunca pensou que, mais de 100 anos depois, esse problema se tornou um dos cursos obrigatórios mais importantes na programação da aprendizagem. O problema das oito rainhas parece muito simples: coloque as oito rainhas na tábua de xadrez para que as oito rainhas não se ataquem (a placa de xadrez é uma matriz quadrada de 8 × 8 e a rainha pode tomar várias etapas em qualquer uma das oito direções horizontal e verticalmente). Embora existam 92 soluções para esse problema, não é fácil encontrar uma solução com as mãos. A figura a seguir é uma das soluções:
Existem muitas variantes do problema do oito rainhas, mas não importa o quão difícil seja, não será mais bonito do que a seguinte variante: projete um plano para colocar uma rainha em todas as fileiras e todas as colunas de um quadro de xadrez infinito, para que todas as rainhas não se ataquem. Especificamente, suponha que o canto inferior esquerdo desta placa esteja na origem, com linhas infinitas de baixo para cima e colunas infinitas da esquerda para a direita, você precisa descobrir o arranjo de todos os números inteiros positivos A1, A2, A3,… para que você coloque a primeira rainha na primeira linha da coluna A1, a segunda rainha na coluna A2, etc.
Aqui está uma construção muito simples e inteligente. Primeiro, damos uma resposta ao problema das cinco rainhas. E muito importante, uma das rainhas ocupa a grade no canto inferior esquerdo.
Em seguida, expandimos a solução das cinco rainhas para as 25 rainhas e com base no layout das cinco rainhas:
Como resultado, as cinco rainhas do mesmo grupo obviamente não se atacam, e as rainhas em diferentes grupos obviamente não se atacarão. Esta é uma solução de 25 Queen que atende aos requisitos. Observe que após a expansão, a seção preenchida anteriormente não mudou.
O que devo fazer a seguir? É isso mesmo, copiamos o desbloqueio da 25 Queen em cinco pedaços e o organizamos novamente de acordo com o layout das cinco rainhas, expandindo assim para 125 rainhas!
Ao expandir constantemente para fora, com base nas peças preenchidas como essa, você pode gerar uma solução para o problema da Rainha Infinita.