用递归函数计算n×n棋盘无冲突放置n个车的方案数

原代码的核心问题 #

• 无限循环：递归函数里用了while (n > 1)，但循环内n的值从未改变，导致每次调用recursively(n-1)返回后，又会回到循环条件判断，陷入无限递归
• solutions无法更新：递归函数始终返回0，solutions += n * recursively(n-1)等价于加0，所以solutions一直是初始值0
• 未模拟棋盘放置逻辑：代码里的board数组未被使用，没有真正模拟车的放置和冲突检查，偏离了练习要求的回溯思路

正确的递归回溯实现（模拟棋盘放置） #

要实现符合练习要求的递归，需要用回溯法：逐行放置车，每一行尝试所有可行的列（该列未被之前的车占用），当所有行都放满车时，计数加1。

代码实现 #

function calc(size) {
    let solutions = 0;
    // 用数组记录已被占用的列，index为列号，值为true表示该列已有车
    const occupiedColumns = new Array(size).fill(false);

    // 递归函数：处理第row行的车放置
    function backtrack(row) {
        // 终止条件：所有行都已放置车，找到一种有效方案
        if (row === size) {
            solutions++;
            return;
        }

        // 尝试当前行的每一列
        for (let col = 0; col < size; col++) {
            // 检查该列是否未被占用（车只看列冲突，因为逐行放，行不会冲突）
            if (!occupiedColumns[col]) {
                // 标记该列已占用
                occupiedColumns[col] = true;
                // 递归处理下一行
                backtrack(row + 1);
                // 回溯：撤销当前列的占用，尝试下一列
                occupiedColumns[col] = false;
            }
        }
    }

    // 从第0行开始放置
    backtrack(0);
    return solutions;
}

console.log(calc(4)); // 输出24，对应4!的结果

代码解释 #

• occupiedColumns数组：用来记录哪些列已经被车占用，避免同一列放置多个车（车的攻击规则是同行同列，这里逐行放置，所以行不会冲突，只需检查列）
• backtrack递归函数：
  • 终止条件：当row === size时，说明n行都已经放置了车，找到一种有效方案，solutions加1
  • 循环尝试当前行的每一列：如果列未被占用，就标记占用，递归处理下一行，递归返回后再撤销标记（回溯），继续尝试下一列
• 回溯的核心：尝试每一种可能的放置方式，有效则计数，无效则回退到上一步尝试其他选项

为什么不用阶乘但结果一致？ #

n×n棋盘放n个不攻击的车，本质是每行选一个不同的列，等价于n个元素的全排列数，即n!。但通过回溯模拟放置过程，符合练习要求的递归实现逻辑，而不是直接计算阶乘。

内容的提问来源于stack exchange，提问作者dr3nan