我写了一种 N-Queens 算法，只处理垂直和水平威胁检测。因此，它更像是一个 N-Towers 解决方案查找器。
为此，我使用了递归。这是一个众所周知的算法。对于棋盘的每个方格，我都放置了一个塔。对于每个放置的塔，我尝试放置另一个塔(这是递归调用)。如果没有剩余的塔可以放置，则意味着程序已找到解决方案并且递归级别必须返回。如果所有棋盘都已与剩余的塔交叉放置，则表示程序未找到解决方案，递归级别必须返回。
我的递归函数有两个参数:必须放置的塔的数量和棋盘(字符串数组的数组；字符串等于“T”表示塔已放置在此棋盘的正方形中，“- "表示方 block 是空的)。
问题
我的算法似乎找到所有解决方案并将它们显示为棋盘，使用“-”(如果运行良好，则使用“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)));
以上内容将对您的解决方案进行深度复制，虽然它可能不是进行深度复制的最有效方法，但它很简单。如果您的算法需要非常快，您可能希望以更快的方式克隆您的解决方案。
虽然我不能保证这会起作用，因为我不能运行你的 fiddle
(同样为了可读性，我建议你这样写你的返回:)
solutions.push(JSON.parse(JSON.stringify(array_array_chessboard)));
return;
编辑:为什么要在 Array::from 上使用 JSON.parse+stringify:
如果你只是这样做
solutions.push(Array.from(array_array_chessboard));
第二个维度仍将引用相同的数组，毕竟那是存储字符串数据的地方。
演示(请注意，您需要在 IE 中填充 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"
关于javascript - 如何通过回溯递归地修改数组元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40303601/