¿Cómo podría modificar los elementos de la matriz recursivamente con retroceso?

Escribí una especie de algorithm de N-Queens, manejando solo la detección de amenazas verticales y horizontales. Por lo tanto, es más bien un buscador de soluciones N-Towers.

Para hacer esto, uso recursion. Es un algorithm bien conocido. Para cada cuadrado del tablero de ajedrez, coloco una torre. Para cada torre colocada, bash colocar otra torre (esta es la llamada recursiva). Si no hay ninguna torre restante para colocar, significa que el progtwig ha encontrado una solución y el nivel recursivo tiene que regresar. Si todo el tablero de ajedrez se cruzó con la (s) torre (s) restante (s) para colocar, significa que el progtwig no encontró una solución y el nivel recursivo tiene que regresar.

Mi function recursiva tiene dos parameters: el número de torres que se deben colocar y el tablero de ajedrez (una matriz de serie de string, la cadena equivale a "T" para indicar que se ha colocado una torre en el tablero y "-" para indicar el cuadrado está vacío).

El problema

Mi algorithm parece encontrar todas las soluciones y las muestra como tableros de ajedrez, usando la notación "-" (y, si funcionó bien, "T"). Esta notación es explicada arriba.

Sin embargo, incluso si el número de soluciones parece ser correcto, las soluciones / tableros de ajedrez mostrados solo contienen "-".

Creo que no paso correctamente mi matriz de matriz (es decir, el tablero de ajedrez) en mi llamada recursiva.

Ilustración de este problema

Para 2 torres y un tablero de ajedrez de 2 * 2 casillas, se encuentran dos soluciones y es normal. Pero solo hay "-" y no aparece "T" … Ese es el problema. En efecto :

Código: concéntrate en mi function recursiva

/** * RECURSIVE FUNCTION. If there are still towers to place, this function tries to place them. If not, it means a * solution has been found : it's stonetworking in an array (external to this function). * If this function can't place a tower, nothing happens. * Else, it places it and makes the recursive call. * Each recursion level does this for each next (to the placed tower) chessboard's squares. * @param number_of_left_towers how many remaining towers to place there are (if 0, it means a solution has been * found) * @param array_array_chessboard the chessboard * @returns {Number} the return is not important */ function placeTower(number_of_left_towers, array_array_chessboard) { if (number_of_left_towers == 0) { return solutions.push(array_array_chessboard); } for (var current_x = 0; current_x < number_of_lines; current_x++) { for (var current_y = 0; current_y < number_of_columns; current_y++) { if (array_array_chessboard[current_x][current_y] == "-" && canBePlaced(array_array_chessboard, current_x, current_y)) { array_array_chessboard[current_x][current_y] = "T"; placeTower(number_of_left_towers - 1, array_array_chessboard); array_array_chessboard[current_x][current_y] = "-"; } } } } 

Código: JSFiddle con toda la fuente

https://jsfiddle.net/btcj6uzp/

También puede encontrar el mismo código a continuación:

 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Recursive algorithm of the N-Towers</title> </head> <body> <script type="text/javascript"> /** * Finds all the solutions to the N-Towers algorithm. * * @param number_of_towers number of towers to try to place in the chessboard * @param number_of_lines chessboard's ones * @param number_of_columns chessboard's ones * @returns {nTowersSolutions} array containing all the solutions */ function nTowersSolutions(number_of_towers, number_of_lines, number_of_columns) { /* NB "T" = "Tower" = presence of a tower in this square of the chessboard "-" = "nothing" = no tower in this square of the chessboard (used for both solutions displaying and finding) */ var solutions = []; var array_array_chessboard = []; // Represents the chessboard for(var i = 0; i < number_of_lines; i++) { array_array_chessboard[i] = new Array(number_of_columns); for(var j = 0; j < number_of_columns; j++) { array_array_chessboard[i][j] = "-"; // We initialize the chessboard with "-" } } /** * Uses HTML to display the found solutions, in the Web page */ this.displaySolutions = function() { var body = document.body; solutions.forEach((array_array_chessboard) => { array_array_chessboard.forEach(function(array_chessboard) { array_chessboard.forEach((square) => { body.innerHTML += square; // New cell }); body.innerHTML += "<br />"; // New line }); body.innerHTML += "<br /><br />"; // New solution }); }; /** * RECURSIVE FUNCTION. If there are still towers to place, this function tries to place them. If not, it means a * solution has been found : it's stonetworking in an array (external to this function). * If this function can't place a tower, nothing happens. * Else, it places it and makes the recursive call. * Each recursion level does this for each next (to the placed tower) chessboard's squares. * @param number_of_left_towers how many remaining towers to place there are (if 0, it means a solution has been * found) * @param array_array_chessboard the chessboard * @returns {Number} the return is not important */ function placeTower(number_of_left_towers, array_array_chessboard) { if (number_of_left_towers == 0) { return solutions.push(array_array_chessboard); } for (var current_x = 0; current_x < number_of_lines; current_x++) { for (var current_y = 0; current_y < number_of_columns; current_y++) { if (array_array_chessboard[current_x][current_y] == "-" && canBePlaced(array_array_chessboard, current_x, current_y)) { array_array_chessboard[current_x][current_y] = "T"; placeTower(number_of_left_towers - 1, array_array_chessboard); array_array_chessboard[current_x][current_y] = "-"; } } } } /** * Can this tower be placed ? * @param array_array_chessboard * @param new_x * @param new_y * @returns {boolean} */ function canBePlaced(array_array_chessboard, new_x, new_y) { for(var i = 0; i < array_array_chessboard.length; i++) { for(var z = 0; z < array_array_chessboard[i].length; z++) { if(array_array_chessboard[i][z] == "T" && ( new_x == z || new_y == i // Horizontal and vertical checks ) ) { return false; } } } return true; } placeTower(number_of_towers, array_array_chessboard); return this; } // <!-- CHANGE THESE PARAMETERS' VALUE TO TEST --> nTowersSolutions(2, 2, 2).displaySolutions(); </script> </body> </html> 

Es muy probable que su problema sea que solo hay una matriz (dos dimensiones), que es global, por lo que al final sus soluciones apuntan a la misma matriz que será el último estado que tenía antes de que nuestra function recursiva regresara por completo.

 array_array_chessboard[current_x][current_y] = "T"; placeTower(number_of_left_towers - 1, array_array_chessboard); array_array_chessboard[current_x][current_y] = "-"; 

Si entiendo lo anterior correctamente, estás (pasando por todas las posiciones, ish)
1) asignar T a una location
2) resolver todas las tablas con T en esa location
3) asignar "-" a la location anterior

así que al final tienes una matriz llena de "-", y todas las soluciones apuntan a esta misma matriz

Intenta replace

 return solutions.push(array_array_chessboard); 

por

 return solutions.push(JSON.decode(JSON.encode(array_array_chessboard))); 

Lo anterior hará una copy profunda de su solución, y aunque no sea la manera más eficiente de hacer una copy profunda, es simple. Si su algorithm necesita ser realmente rápido, es posible que desee search una forma más rápida para clonar su solución.

Aunque no puedo garantizar que esto funcione, ya que no puedo ejecutar tu violín

(También para facilitar la lectura, le sugiero que escriba su statement como tal 🙂

 solutions.push(JSON.parse(JSON.stringify(array_array_chessboard))); return; 

EDIT: ¿por qué usar JSON.parse + stringify sobre Array::from :

si simplemente lo haces

 solutions.push(Array.from(array_array_chessboard)); 

La segunda dimensión seguirá haciendo reference a las mismas matrices, y ahí es donde se almacenan los datos de la cadena después de todo.

para demostrar (tenga en count que debe rellenar Polyfill el Array.from en IE, o simplemente probar en un browser diferente):

 var arr1 = ["a"]; var arr2 = ["b"]; var metaArr = [arr1, arr2]; console.log(metaArr[0][0], metaArr[1][0]); // "ab" var metaArrClone = Array.from(metaArr); var metaArrClone[0][0] = "c"; console.log(metaArrClone[0][0]); // "c" console.log(metaArr[0][0]); // "c" var metaArrClone2 = JSON.parse(JSON.stringify(metaArr)); console.log(metaArrClone2[0][0]); // "c" metaArrClone2[0][0] = "d"; console.log(metaArrClone2[0][0]); // "d" console.log(metaArr[0][0]); // "c" 

No necesita mantener las soluciones fuera de su function recursiva. Podría ser mejor si mantiene las soluciones dentro de su function recursiva y luego devuelve todas las soluciones, por lo que no debe preocuparse por el estado fuera de la function.

Por supuesto, si tiene que usar las soluciones finitas antes de que vuelva la function recursiva (tal vez tenga una gran tabla de cortar), su solución podría ser mejor. O podrías usar un generador.

También podría ser bueno mantener este tipo de lógica separada de la interfaz de usuario así que primero concéntrese en la solución y luego intente dibujar el resultado en el browser o donde desee, o haga lo contrario.

Puede comenzar desde el siguiente código, pero compruebe si realmente encuentra todas las soluciones antes de usarlo.

 'use strict' /* Finds all the solutions to the N-Towers algorithm. * * @param number_of_towers number of towers to try to place in the chessboard * @param number_of_lines chessboard's ones * @param number_of_columns chessboard's ones * @returns {nTowersSolutions} array containing all the solutions * "Tower" = presence of a tower in this square of the chessboard * "Nothing" = no tower in this square of the chessboard * "Blocked" = the cell is blocked */ function nTowersSolutions(number_of_towers, number_of_lines, number_of_columns) { var chessboard = _initChessboard(number_of_lines, number_of_columns); var solutions = _findAllSolution(chessboard, number_of_towers); return solutions; } // nuber, * -> array var _newArrFromLenAndElement = function(length, element) { return Array.apply(null, Array(length)).map(function(){ return element; }); }; // number, number -> cheesboard var _initChessboard = function(number_of_lines, number_of_columns) { var oneColumnChessboard = _newArrFromLenAndElement(number_of_lines, []); var chessboard = oneColumnChessboard.map(function() { var line = _newArrFromLenAndElement(number_of_columns, 'Nothing'); return line; }); return chessboard; }; // chessboard, line_index, column_index -> chessboard var _placeTower = function(chessboard, line_index, column_index) { var ff = chessboard.map(function(line, index) { if (index === line_index) { return line.map(function() { return 'Blocked'; }); } else { return line.map(function(x, index){ if(index===column_index){return'Blocked';} else{return x;} }); } }); ff[line_index][column_index] = 'Tower'; return ff; }; // array[][] -> array[] var _flatten = function(arr) { return [].concat.apply([], arr); }; // *, array -> boolean var _isInArray = function(value, array) { return array.indexOf(value) > -1; }; // cheesboard, numberm number -> array // this could be a bruteforce recursive solution at your problem ( actually you have to check if // it is correct ) // we need _lines_done for don't look for solutions already finded (if you have tried all the // pattern with a tower in the first line you don't want try to place a tower in the first line) var _findAllSolution = function(chessboard, number_of_towers, _lines_done, _deep) { _lines_done = _lines_done || []; _deep = _deep || 0; if (number_of_towers === 0){ return chessboard; } //for all the cells in the ceesboard try to place a tower var solutions = chessboard.map(function(line, line_index) { var solution = line.map(function(cell, column_index) { if (_isInArray(line_index, _lines_done)) { return 'alreadyVisitedLine'; } else if (cell === 'Nothing') { var fulfilledChessboard = _placeTower(chessboard, line_index, column_index); if (line_index > 0 && _deep === 0 && !(_isInArray(line_index - 1, _lines_done))) { _lines_done.push(line_index - 1); } return _findAllSolution(fulfilledChessboard, number_of_towers -1, _lines_done, _deep + 1); } else { return 'DeadEnd!'; } }); return _flatten(solution); }); var flatSolutions = _flatten(solutions); //you should .filter the solutions return _flatten(solutions); }; var h = nTowersSolutions(2,2,2) console.log(h)