All geek questions in one place

How can I change the elements of an array recursively using backtracking?

I wrote a kind of N-Queens algorithm, processing only the detection of vertical and horizontal threats. So this is more of a search for N-Towers solutions.

For this I use recursion. This is a well-known algorithm. For each square of a chessboard, I place a tower. For each placed tower, I try to place another tower (this is a recursive call). If there is no tower to accommodate the remaining tower, this means that the program has found a solution, and the recursive level should return. If all the chessboards intersect with the remaining tower (s), this means that the program has not found a solution, and the recursive level should return.

My recursive function has two parameters: the number of towers to be placed, and the chessboard (array of string array, string equal to "T" to indicate that the tower was placed on this square of the chessboard and "-" to indicate that the square empty).

Problem

My algorithm seems to find all the solutions and display them like chessboards using a “-” (and, if that worked, a “T”). This notation is explained above.

However, even if the number of solutions seems to be correct, the displayed solutions / chessboards contain only “-”.

I think that I am not passing my array array (i.e. a chessboard) correctly in my recursive call.

Illustration of this problem

2 2 * 2 , . "-" ""... . :

-

-

:

    /**
     * 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 stored 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 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] = "-";
                }
            }
        }
    }

: JSFiddle

https://jsfiddle.net/btcj6uzp/

:

<!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 ones
     * @param number_of_columns chessboard 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 stored 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 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>
+4
2

, , () , , , , , ,

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

, ( , ish)
1) T 2) T
3) "-"

, "-",

return solutions.push(array_array_chessboard);


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

, , . , .

, ,

( :)

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

EDIT: JSON.parse + stringify Array::from:

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

- , .

( , polyfill Array.from IE ):

var arr1 = ["a"];
var arr2 = ["b"];
var metaArr = [arr1, arr2];
console.log(metaArr[0][0], metaArr[1][0]); // "a b"

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"
+2

. , , .

, , (, cheesboard), . .

ui, , , .

, , , , .

'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 ones
 * @param number_of_columns chessboard 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)
Hide result
0

Source: https://habr.com/ru/post/1659177/

More articles:


All Articles