stackoverflow_how-could-i-modify-the-array-elements-recursively-with-backtracking.js

'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);
};

module.exports.nTowersSolutions = nTowersSolutions;