递归实现N皇后时二维数组board未按栈回溯的原因咨询

嗨，我来帮你拆解这个N皇后递归回溯的问题——核心问题出在数组参数的传递方式，以及你漏掉了关键的回溯操作！

为什么placed能正常回溯，而board不行？ #

• 对于placed这类普通变量：C++中函数参数默认是值传递，每次递归调用foo(..., placed+1)时，都会创建一个placed的副本，下层递归对placed的修改完全不会影响上层的变量。所以当递归返回时，上层的placed还是原来的值，自然实现了自动回溯。
• 对于board二维数组：C++里数组作为函数参数时，会自动退化为指针。你写的bool board[100][100]参数，实际等价于bool (*board)[100]——也就是说，所有递归调用操作的都是同一块内存空间的数组！你在递归里设置board[i][j] = true后，如果不手动撤销这个操作，递归返回时数组的状态就会保留，不会自动回溯。

你的代码缺失了什么？ #

在foo函数中，你放置皇后（board[i][j] = true）并进入递归后，递归返回时没有把这个位置改回false，导致数组状态无法恢复到放置皇后之前的样子。这就是board始终保留最后调用状态的根本原因！

修复后的代码（关键部分修改） #

只需要在递归调用结束后，添加一行代码撤销皇后的放置：

void foo(bool board[100][100], int x, int y, int n, int m, int placed) {
    if( placed == n ) {
        display(board, n, m);
        return ;
    }
    int i, j;
    for(i=x; i<=n; i++) {
        for(j=y; j<=m; j++) {
            if( checkBoard(board, n, m, i, j) ) {
                board[i][j] = true;
                display(board, n, m);
                cout<<placed;
                foo(board, 1, 1, n, m, placed+1);
                // 关键：递归返回后，撤销当前皇后的放置，完成数组状态回溯
                board[i][j] = false;
                display(board, n, m);
                cout<<placed;
            }
        }
    }
}

额外小建议（非核心但实用） #

你的checkBoard函数现在会遍历整个数组来检查冲突，其实可以优化：因为我们是按顺序放置皇后，只需要检查当前位置上方的列、左上对角线、右上对角线即可，不需要遍历所有已放置的皇后，能大幅提高效率。比如：

bool checkBoard(bool board[100][100], int n, int m, int x, int y) {
    // 检查同一列上方
    for(int i = 1; i < x; i++) {
        if(board[i][y]) return false;
    }
    // 检查左上对角线
    for(int i = x-1, j = y-1; i >=1 && j >=1; i--, j--) {
        if(board[i][j]) return false;
    }
    // 检查右上对角线
    for(int i = x-1, j = y+1; i >=1 && j <=m; i--, j++) {
        if(board[i][j]) return false;
    }
    return true;
}

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