递归函数，用于计算 N 大小板中的车

Question

我正在尝试实现一个函数，该函数将计算"n"大小的国际象棋盘中可以有多少"n"个车，而不会在可以被另一只车攻击的位置发生碰撞。 我使用了 4*4 网格作为基础。我正在努力解决创建数组的概念以及如何继续进行递归(必须根据练习请求使用递归来完成)。我的递归一团糟，我仍然不知道如何以[ | | | ]x4 的形状填充数组。

我看了很多，这是皇后区的问题(现在只是车)，但我仍然不知道如何进行。 那里有很多解决方案，但没有一个需要返回阶乘整数(我已经尝试了阶乘方法并且它有效，但不是练习需要的)。调试显示solutions永远不会更新，当n小于 1 时，它会进入无限循环。

function calc (size) {
// should be incremented each time a rook is placed
let rooks = 0;
// should increment and
let solutions = 0;
// where the array should populated ...?
const board = [];
function recursively (n) {
// if size becomes smaller than 1 stop recursion?
while (n > 1) {
// update solution var?
solutions += n * recursively(n -1);
}
// increment count of rooks
rooks++;
// return 0 in case there is a size of 0
return 0;
}
recursively(size);
return solutions;
}
console.log(calc(4));

请注意，我现在正在学习JS。谢谢

Answer 1

从某种意义上说，这是一个极其微不足道的问题，因为我们一眼就能看到答案。 在n x n板上，当我们在任何地方放置 Rook 时，我们已经阻止了该行或该列上任何其他 Rook 的放置，从而将问题减少到(n - 1) x (n - 1)，因此我们可以注意到，因此在n x n板上，我们可以放置n个 Rook。

所以一个微不足道的答案是

const countRooks = (n) => n

或者，如果你必须使用递归，而你的导师不介意一个聪明的人，你可以写

const countRooks = (n) => 
n <= 0
? 0 
: 1 + countRooks (n - 1)

但是，让我们假设这是在为更艰巨的任务做准备，并且我们希望通过实际的董事会代表做一些合法的事情。 我们应该如何代表我们的董事会？ 我们可以尝试这样的事情：

const ourEmpty4x4Board = [
{c: 'a', r: 4, v: ' '},  {c: 'b', r: 4, v: ' '},  {c: 'c', r: 4, v: ' '},  {c: 'd', r: 4, v: ' '},
{c: 'a', r: 3, v: ' '},  {c: 'b', r: 3, v: ' '},  {c: 'c', r: 3, v: ' '},  {c: 'd', r: 3, v: ' '},
{c: 'a', r: 2, v: ' '},  {c: 'b', r: 2, v: ' '},  {c: 'c', r: 2, v: ' '},  {c: 'd', r: 2, v: ' '},
{c: 'a', r: 1, v: ' '},  {c: 'b', r: 1, v: ' '},  {c: 'c', r: 1, v: ' '},  {c: 'd', r: 1, v: ' '},
]

const ourFilled4x4Board = [
{c: 'a', r: 4, v: 'R'},  {c: 'b', r: 4, v: ' '},  {c: 'c', r: 4, v: ' '},  {c: 'd', r: 4, v: ' '},
{c: 'a', r: 3, v: ' '},  {c: 'b', r: 3, v: ' '},  {c: 'c', r: 3, v: 'R'},  {c: 'd', r: 3, v: ' '},
{c: 'a', r: 2, v: ' '},  {c: 'b', r: 2, v: ' '},  {c: 'c', r: 2, v: ' '},  {c: 'd', r: 2, v: 'R'},
{c: 'a', r: 1, v: ' '},  {c: 'b', r: 1, v: 'R'},  {c: 'c', r: 1, v: ' '},  {c: 'd', r: 1, v: ' '},
]

但这似乎工作量很大，而且有些难以处理。 它必须处理字符串列标记而不是使用整数循环，这很尴尬;此外，它没有为我们提供任何明确的方式来推动我们解决问题。

因此，让我们尝试另一种表示形式。 这个怎么样？

const ourEmpty4x4Board = [
[" ", " ", " ", " "],
[" ", " ", " ", " "],
[" ", " ", " ", " "],
[" ", " ", " ", " "],
]

const ourFilled4x4Board = [
["R", " ", " ", " "],
[" ", " ", "R", " "],
[" ", " ", " ", "R"],
[" ", "R", " ", " "],
]

这似乎更有帮助，所以让我们继续这样做，我们可以创建一个这样的空板：

const createEmptyBoard = (size) =>
Array .from ({length: size}, () => Array .from ({length: size}, () => ' '))
createEmptyBoard (4)
//=> [[" ", " ", " ", " "], [" ", " ", " ", " "], [" ", " ", " ", " "], [" ", " ", " ", " "]]

如果我们尝试调试我们的工作，这种观点并不是特别有用。 我们希望在开发其余部分时有一个快速而肮脏的电路板预览器。 虽然我们当然可以制作一个生成这样的东西：

+---+---+---+---+
|♜ |   |   |   |
+---+---+---+---+
|   |   |♜ |   |
+---+---+---+---+
|   |♜ |   |   |
+---+---+---+---+
|   |   |   |♜ |
+---+---+---+---+

甚至更花哨的东西，这可能是矫枉过正。 如果我们满足于这样的事情呢？

R···
··R·
·R··
···R

现在我们需要一种方法来将 Rook 添加到给定的板中。 我们将编写一个函数，该函数接受一个板、一行和一列，并返回一个与原始板相同但在给定行和列处带有 Rook 的新板。

这并不难。 像这样的事情可以：

const addRook = (board, row, col) => {
const newBoard = board .map ((r) => [...r])
newBoard [row] [col] = 'R'
return newBoard
}

请注意，我们正在构建一个新板。旧的仍然完好无损。 我发现这是一种有用的工作方式。 您的教师可能会也可能不同意，或者可能认为这只适合课程的后面。 但这就是我的想法。

所以现在我们可以使用这些工具将一些 Rooks 添加到看板中：

const createEmptyBoard = (size) =>
Array .from ({length: size}, () => Array .from ({length: size}, () => ' '))
const addRook = (board, row, col) => {
const newBoard = board .map ((r) => [...r])
newBoard [row] [col] = 'R'
return newBoard
}
const display = (board) => 
board .map (row => row .join ('') .replaceAll (/s/g, '·')) .join ('n') + 'n'
const board = createEmptyBoard (4)
console .log (display (board))
const oneRook = addRook (board, 1, 2)
console .log (display (oneRook))
const twoRooks = addRook (oneRook, 3, 3)
console .log (display (twoRooks))
const threeRooks = addRook (twoRooks, 0, 0)
console .log (display (threeRooks))
const fourRooks = addRook (threeRooks, 2, 1)
console .log (display (fourRooks))

.as-console-wrapper {max-height: 100% !important; top: 0}

现在我们开始解决问题。 我不会为你做这件事。 我把最难实现的部分留给你。 如果我们有这样的板：

······
·R····
······
····R·
······
··R···

并且我们想放置另一个 Rook，我们可以依次查看每个现有的 Rook，并从考虑中消除它们的行和列：

·*····
*R****
·*····
·*··R·
·*····
·*R···

然后

·*··*·
*R****
·*··*·
****R*
·*··*·
·*R·*·

其次

·**·*·
*R****
·**·*·
****R*
·**·*·
**R***

剩下九个方格有待填满。 你可以编写一个函数，它拿一个板子，随机选择一个未填充/未阻塞的方块并填充它，屏蔽其行和列中的方块，并增加你的 Rooks 运行计数，当没有更多的方块需要填充时结束。 这将正常工作，这可能是一个不错的方法。

但另一种方法是实际上简单地从您正在处理的内容中删除匹配的行和列。 然后，当棋盘没有正方形时，您可以结束。 这稍微干净一些，所以我建议你尝试编写一个函数eliminate它接受一个板、一行和一列，并返回一个与第一个相同的板，只是删除了相关的行和列。

使用它，你可以编写一个递归函数，它接受一个板，如果它是空的，则返回零;否则随机选择正方形的行和列，消除该行和列，递归调用这个新板的函数，将一个添加到结果值并返回它。 如果你再写一个函数来接受板大小，创建一个该大小的空板，然后用该板调用主函数，返回结果，你就解决了问题。

但是，正如前面所指出的，所有这些似乎都是一种极其迂回的方式来处理可能只是countRooks = (n) => n的事情。 确实如此。 但它让你做的是，只需稍作改动，就可以计算将nRooks放置在n x n板上或m x n板上的所有方法。 或者你可以接受一个已经放置了一些 Rooks 的板子，并计算有多少种方法可以放置更多的 Rooks。

Answer 2

递归的这一部分

while (n > 1) {
// update solution var?
solutions += n * recursively(n -1);
}

要么永远不会做任何事情，要么永远不会逃脱循环，因为如果 n 大于 1，则不会在函数中更改它。