如何使用回溯递归修改数组元素
How could I modify the array elements recursively with backtracking?
我写了一种N-Queens算法，只处理垂直和水平威胁检测。因此，它相当于一个N-Towers解决方案查找器。
为此，我使用递归。这是一个众所周知的算法。对于棋盘的每一个方格，我都会放置一座塔。对于每个放置的塔，我尝试放置另一个塔(这是递归调用(。如果没有任何剩余的塔可以放置，这意味着程序已经找到了解决方案，必须返回递归级别。如果所有的棋盘都已经与剩余的塔交叉，这意味着程序没有找到解决方案，必须返回递归级别。
我的递归函数有两个参数：必须放置的塔的数量和棋盘(一组字符串；字符串等于"T"表示塔已放置在棋盘的正方形中，"-"表示正方形为空(。
问题
我的算法似乎找到了所有的解决方案，并将它们显示为棋盘，使用"-"(如果效果良好，还使用"T"(表示法。上面解释了这个符号。
然而，即使解决方案的数量似乎是正确的，显示的解决方案/棋盘也只包含"-"。
我想我在递归调用中没有正确地传递数组(即：棋盘(。
此问题的说明
对于2个塔和2*2个正方形的棋盘，找到了两个解决方案，这是正常的。但是只有"-"，没有"T"出现。。。这就是问题所在。事实上：
--
--
代码：关注我的递归函数
/**
* 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 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'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] = "-";
}
}
}
}
代码：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'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 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'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>
您的问题很可能只有一个(二维(数组，它是全局的，所以最终您的解决方案都指向同一个数组，这将是递归函数完全返回之前的最后一个状态。
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+Stringfy over Array::from:
如果你只是做
solutions.push(Array.from(array_array_chessboard));
第二个维度仍然会引用相同的数组，毕竟这就是字符串数据的存储位置。
演示(请注意，您需要在IE中polyfill Array.from，或者只需在不同的浏览器上尝试(：
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"
您不需要将解决方案保留在递归函数之外。如果将解决方案保留在递归函数中，而不是返回所有解决方案，则可能会更好，这样就不必担心函数外的状态。
当然，如果你必须在递归函数返回之前使用找到的解决方案(也许你有一个大棋盘(，你的解决方案可能会更好。或者你可以使用发电机。
将这种逻辑与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'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)相关文章：
- 在函数中添加数组元素的数值
- 访问JSON对象内部的数组元素
- Mongoose-在更新中删除数组元素
- javascript数组元素是否知道其封闭数组
- 将数组元素附加到FormData dos'不适用于Firefox 15
- 如何在javascript中使用click函数选择数组元素
- 如何在JavaScript中剥离数组元素中的非整数
- 消隐数组元素是否生成自己的属性
- 如何使一个Math.random数组元素比另一个数组元素更有可能被选中
- 在Codrops的内容中添加数组元素展开缩略图网格预览
- 如何使用Jquery水平打印表中的数组元素，并在某个元素之后垂直打印
- 如何访问数组中的数组元素(JavaScript）
- 生成ACF标记位置的数组(元素列表后缺少]）
- validate.js验证数组元素
- JavaScript:如何在迭代过程中修改数组中的值
- JavaScript Unshift EACH 数组元素
- 如何在加号运算符之后选择数组元素的一部分
- Emscripten:调用修改数组元素的 C 函数
- 如何使用回溯递归修改数组元素
- 如何替换数组元素而不修改原始数组并创建副本
