Con respecto a la solución de JavaScript al problema de las ocho reinas, siempre siento que necesito aprender el algoritmo. Será vergonzoso averiguar si lo uso algún día.
fondo
La pregunta de las ocho reinas es una pregunta basada en el ajedrez: ¿cómo se pueden colocar ocho reinas en la placa de ajedrez 8 × 8 para que ninguna reina pueda comer las otras reinas directamente? Para lograr esto, ninguna de la reina puede estar en la misma línea horizontal, vertical o diagonal
El problema de las ocho reinas se puede generalizar al problema más general de la colocación de N Queen: en este momento el tamaño del tablero de ajedrez se convierte en n × n, y el número de reinas también se convierte en n. Si y solo si n = 1 o n ≥ 4 hay una solución al problema
Algoritmo de enumeración ciega
A través de los bucles N-Fold, enumeradas soluciones que cumplen con las limitaciones (hay muchos códigos de bucle de ocho veces, se realizan cuatro trucos aquí), encuentren todas las posiciones posibles de las cuatro reinas y luego juzguen en toda la junta si estas cuatro reinas se comerán directamente. La idea del programa es relativamente simple.
función 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; }}} return true;} function Queen1 () {var arr = []; for (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; arr [3] <= 4; arr [3] ++) continuar; } else {console.log (arr); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Ial }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Ial }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Ial }}}}}}}}}}}}}}}}}}}}}}} IalCon respecto al resultado, en el tablero de ajedrez 4*4, las cuatro reinas no pueden estar en una fila. arr [0] a arr [3] corresponde a las cuatro reinas respectivamente. El valor correspondiente al subíndice de la matriz y el subíndice es la posición de la reina en el tablero.
Método de retroceso
"Si no puedes ir, solo da la vuelta". Determine si lo coincide con el nodo apropiado. Si no coincide, ya no explorará esta rama.
función 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; }} return true;} function Queen2 () {var arr = []; for (arr [0] = 1; arr [0] <= 4; arr [0] ++) {for (arr [1] = 1; arr [1] <= 4; arr [1] ++) {if (! check2 (arr, 1)) continúa; // Indique el conflicto entre dos reinas para (arr [2] = 1; arr [2] <= 4; arr [2] ++) {if (! Check2 (arr, 2)) continuar; // Indique el conflicto entre tres reinas para (arr [3] = 1; arr [3] <= 4; arr [3] ++) {if (! Check2 (arr, 3)) {continuar; } else {console.log (arr); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Ial }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Ial }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Ial }}}}}}}}}}}}}}Retroceso no recursivo
Marco de algoritmo:
mientras que (k> 0 『hay un camino por recorrer』 y 『no alcanzado el objetivo』) {// k> 0 『Hay un camino por recorrer si (k> n) {// busca nodos de hoja // busca una solución, salida} más {// a [k] el primer valor posible mientras (k] está en el espacio de búsqueda") {// a [k] el próximo valor} espacio ") {// Marque el recurso ocupado // k = k + 1; } else {// limpia el espacio de estado ocupado // k = k - 1; }}}El código específico es el siguiente. La capa más externa mientras contiene dos partes. Uno es un recorrido de los posibles valores de la reina actual, y el otro es una decisión de ingresar a la siguiente capa o retroceder la capa anterior.
function Backdate (n) {var arr = []; var k = 1; // la nth reina 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 reina satisface las restricciones y realiza el siguiente juicio si (arr [k-1] <= n) {if (k == n) {// la nth Queen Console.log (arr); } else {k = k + 1; // la próxima reina arr [k-1] = 0; }} else {k = k - 1; // retroceso, última reina}}} retroceso (4); // [2, 4, 1, 3] // [3, 1, 4, 2]Método de retroceso recursivo
Las llamadas recursivas reducen en gran medida la cantidad de código y aumentan la legibilidad del programa.
var arr = [], n = 4; función 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]Hermoso ambiente
¿Qué es Amb? Déle una lista de datos, que puede devolver una forma de cumplir con las situaciones de éxito de las limitaciones. Sin éxito, fallará. Por supuesto, puede devolver todas las situaciones de éxito. El autor ha escrito muchos puntos anteriores, solo para recomendar este algoritmo AMB aquí. Es adecuado para manejar escenarios de retroceso simples. Es muy interesante. Veamos cómo funciona.
Primero, lidiemos con un pequeño problema, encuentre cadenas adyacentes: obtenga varios conjuntos de matrices de cuerdas, y cada matriz saca una cadena. El último carácter de la cadena anterior es el mismo que el primer carácter de la siguiente cadena. Si se cumplen las condiciones, se emitirán las cadenas recién recuperadas.
ambRun(function(amb, fail) { // Constraint method function linked(s1, s2) { return s1.slice(-1) == s2.slice(0, 1); } // Inject data list var w1 = amb(["the", "that", "a"]); var w2 = amb(["frog", "elephant", "thing"]); var w3 = amb(["walked", "Tured", "crece"); despacio"});¡Se ve súper simple o no! Sin embargo, la premisa de usar es que no le importa el rendimiento, ¡es realmente una pérdida de tiempo!
A continuación se muestra su implementación de JavaScript. Si está interesado, puede estudiar cómo extrae retroceso.
function Ambrun (func) {Var opciones = []; índice var; función amb (valores) {if (value.length == 0) {fail (); } if (index == Choices.length) {Choices.push ({i: 0, Count: Values.Length}); } var Choice = Choices [index ++]; Valores de retorno [Choice.i]; } function fail () {lanzar fail; } while (true) {try {index = 0; regreso func (Amb, Fail); } catch (e) {if (e! = fail) {lanzar e; } elección var; while ((Choice = Choices.pop ()) && ++ Choice.i == Choice.count) {} if (Choice == Undefined) {return Undefined; } ophes.push (elección); }}}Y el código específico del problema de las ocho reinas implementado usando AMB
Ambrun (function (Amb, Fail) {var n = 4; var arr = []; var thurn = []; for (var n = 0; n <n; n ++) {thur [thurn.length] = n +1;} while (n--) {arr [arr.length] = amb (thure);} for (var i = 0; i <n; + +i) {para (var j = i +1; J) J) var a = arr [i], b = arr [j];Solución de JavaScript al problema de las ocho reinas
Esta es la solución de JavaScript al problema de las ocho reinas. Todo el programa no se usa para bucles y se implementa a través de la recursión. Utiliza completamente el mapa, reduce, filtra, concatora, se corta los métodos del objeto de matriz.
'Use Strict'; var queens = function (boardersize) {// use recursión para generar un intervalo var de matriz desde inicio a final de Funcion (inicio, end) {if (start> end) {return []; } intervalo de retorno (inicio, final - 1) .concat (final); }; // verifique si una combinación es válida var isValid = function (queencol) {// verifique si hay conflicto entre dos posiciones var issAfe = function (punto, puntob) {var slope = (punto.row - pointb.row) / (punto.col - pointb.col); if ((0 === Slope) || (1 === Slope) || (-1 === Slope)) {return false; } return verdadero; }; var len = queencol.length; var pointTocompare = {Row: Queencol [len - 1], col: len}; // Primero corte la matriz, excepto la última columna, luego pruebe si hay un conflicto entre los puntos en cada columna y los puntos a probar, y finalmente fusionar los resultados de la prueba. Return queencol .slice (0, len - 1) .map (function (fila, index) {return isSafe ({row: fila, col: index + 1}, pointtocompare);}) .reduce (function (a, b) {return a && b;}); }; // Genere de forma recursiva combinaciones que se ajusten a las reglas var queenCols = function (size) {if (1 === size) {return Interval (1, boardersize) .map (function (i) {return [i];}); } // Primero expanda el conjunto de todas las columnas anteriores que se ajustan a las reglas, luego usen la reducción de dimensionalidad Red y finalmente use ISValid para filtrar combinaciones que se ajustan a las reglas return queencols (size - 1) .map (function (queEnCol) {return (1, boilderSize) .map (función (fila) {return queenCol.concat (row);});});});});});});});});}); (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]]PD: PROBLEMA EXTENCIDADA N LENA
Cuando el jugador de ajedrez Max Bezzel le preguntó al rompecabezas de las ocho reinas en 1848, probablemente nunca pensó que más de 100 años después, este problema se convirtió en uno de los cursos obligatorios más importantes en la programación del aprendizaje. El problema de las ocho reinas suena muy simple: coloque las ocho reinas en el tablero de ajedrez para que las ocho reinas no se ataquen entre sí (el tablero de ajedrez es una matriz cuadrada de 8 × 8, y la reina puede dar múltiples pasos en ninguna de las ocho direcciones horizontal y verticalmente). Aunque hay 92 soluciones a este problema, no es fácil encontrar una solución con las manos desnudas. La siguiente figura es una de las soluciones:
Hay muchas variantes del problema de las ocho reinas, pero no importa cuánto sea, no será más guapo que la siguiente variante: diseñe un plan para colocar una reina en cada fila y cada columna de un tablero de ajedrez infinito, para que todas las reinas no se atacen entre sí. Específicamente, suponga que la esquina inferior izquierda de este tablero está en el origen, con filas infinitas de abajo a arriba e infinita columnas de izquierda a derecha, debe descubrir la disposición de todos los enteros positivos A1, A2, A3, ... para que cuando coloque la primera reina en la primera fila en la columna A1, la segunda reina en la columna A2, etc., luego, no se atacarán dos reinas entre sí.
Aquí hay una construcción muy simple e inteligente. Primero, damos una respuesta al problema de las cinco reinas. Y muy importante, una de las reinas ocupa la cuadrícula en la esquina inferior izquierda.
A continuación, expandimos la solución de las cinco reinas a las 25 reinas, y basadas en el diseño de las cinco reinas:
Como resultado, las cinco reinas en el mismo grupo obviamente no se atacan entre sí, y las reinas en diferentes grupos obviamente no se atacan entre sí. Esta es una solución de 25 Queen que cumple con los requisitos. Tenga en cuenta que después de la expansión, la sección llena previamente no ha cambiado.
¿Qué debo hacer a continuación? Así es, copiamos el desbloqueo de las 25 reinas en cinco piezas, y lo arreglamos nuevamente de acuerdo con el diseño de las cinco reinas, ¡expandiéndose así a 125 reinas!
Al expandir constantemente hacia afuera en función de las partes llenas como esta, puede generar una solución al problema infinito de la reina.