N皇后解数统计算法C语言位掩码实现提交OJ报错排查

n-queens（N皇后） 谜题要求在n x n的棋盘上放置n个皇后，满足任意两个皇后无法互相攻击。给定整数n，返回* n皇后谜题 的不同解的总数*，测试用例约束为1 ≤ n ≤ 9。

内容摘自LeetCode题目页

我尝试使用bit-masking（位掩码）方法求解该问题，核心思路是枚举所有可能的放置组合，遇到不可行场景时执行回溯。

我采用逐行放置皇后的策略，每次放置皇后后，标记剩余皇后不可放置的棋盘位置。

位置判定规则：每个列（column） 可通过其index（索引）唯一标识；对角线（diagonal） 上的位置满足行索引 - 列索引值相等的特性；反对角线（anti-diagonal） 上的位置满足行索引 + 列索引值相等的特性。

因此在任意位置放置皇后后，可通过三个位掩码变量分别标记该位置占用的列、对角线、反对角线，实现位置合法性校验。

以下是我提交到在线评测平台的C语言实现代码：

int N;
int count=0;

void rowExpansion(int r, int cols, int diags, int aDiags);

int totalNQueens(int n)
{    
    N=n;
    rowExpansion(0,0,0,0);
    
    return count;
}

void rowExpansion(int r, int cols, int diags, int aDiags)
{   
    if (r<N)
    {
        for (register int c=0; c<N; c++)
        {
            // current Diagonal, current antidiagonal
            int cD = r - c + N, cAd= r + c;
            
            /* Check if (r,c) is valid, Checking ith bits of Three Bit Masks.  
            If any of them is set, don't include this (r,c) */

            if ((cols & (1 << c)) || (diags & (1 << cD)) || (aDiags & (1 << cAd))) 
            continue;
            
            //Next Row traversal with updated bit-masks
            rowExpansion(r+1, cols | 1<<c, diags | 1<<cD, aDiags | 1<<cAd);
        }
    }
    
    else count++;
}

该代码在本地控制台运行时结果正常，例如n=1时可输出正确结果，但提交到在线评测平台后返回错误答案。我使用Python实现完全相同的算法逻辑可正常通过所有测试用例。

错误截图如下：

以下是补充了main函数的最小可复现示例（reprex），该代码在CodeBlocks IDE中运行可输出正确结果：

#include <stdio.h>

int N;
int count=0;

void rowExpansion(int r, int cols, int diags, int aDiags);

int totalNQueens(int n)
{
    N=n;
    rowExpansion(0,0,0,0);

    return count;
}

void rowExpansion(int r, int cols, int diags, int aDiags)
{
    if (r<N)
    {
        for (register int c=0; c<N; c++)
        {
            // current Diagonal, current antidiagonal
            int cD = r - c + N, cAd= r + c;

            /* Check if (r,c) is valid, Checking ith bits of Three Bit Masks.
            If any of them is set, don't include this (r,c) */

            if ((cols & (1 << c)) || (diags & (1 << cD)) || (aDiags & (1 << cAd))) 
            continue;

            //Next Row traversal with updated bit-masks
            rowExpansion(r+1, cols | 1<<c, diags | 1<<cD, aDiags | 1<<cAd);
        }
    }

    else count++;
}

void main()
{
    int n;
    printf("Enter Number of Queens (1-9) : ");
    scanf("%d",&n);

    if (n<1 || n>9)
    {
        printf("Wrong Input!");
    }
    else
    {
        int D[] = {0, 1, 0, 0, 2, 10, 4, 40, 92, 352};
        int x = totalNQueens(n);

        printf("Desired Output : %d\nGiven Output   : %d\n", D[n],x);
    }
}

补充背景：我平时主要使用python进行编程练习，对C语言的掌握并不熟练。

1. 上述代码的错误属于什么类型？是逻辑错误、语法错误还是运行时错误？
2. 为什么同一段代码在本地控制台运行结果正确，提交到在线评测平台却运行失败？是否有相关参考资料可以解释该现象？
3. 有评论指出该错误由全局变量导致，希望解释全局变量引发该问题的具体原理，以及如何修改代码移除全局变量？

1. 错误类型判定 #

这是逻辑错误。代码不存在语法问题，也不会触发崩溃、内存越界类的运行时错误，核心是状态残留导致计算结果不符合预期。

2. 本地与在线评测运行结果不一致的原因 #

本地测试时，你每次运行程序只会调用一次totalNQueens函数，程序启动时全局变量会被默认初始化为0，跑完一次程序就直接退出，状态不会残留。
但在线评测平台的运行逻辑是：同一个程序进程内会连续多次调用totalNQueens函数跑不同的测试用例，不会每次调用都重启进程重置全局状态。举个例子，平台先跑n=4的用例，跑完后全局变量count已经累加到2，接下来跑n=1的用例时，你没有把count重置为0，最终返回的结果就是2+1=3，和正确答案1不符，自然判错。
这种问题本质是没有保证函数的可重入性——带状态的全局变量导致函数多次调用时会互相干扰。

3. 全局变量的问题原理与修复方案 #

C语言中全局变量存储在全局数据区，生命周期和整个程序的运行周期一致，不会因为函数调用结束就销毁重置，所有对该变量的修改都会一直保留，直到程序退出。
你的代码里定义了两个全局变量：

• N：每次调用totalNQueens时你都会给它赋新值，所以不会引发问题
• count：你只在递归到终止条件时做累加操作，从来没有在每次调用totalNQueens的初始阶段把它重置为0，所以多次调用时计数会不断叠加之前测试用例的结果。

修复方案 #

方案1：保留全局变量但每次调用重置（不推荐）

只需要在totalNQueens函数开头加一行count = 0;即可，每次进入函数先把计数清零，再开始递归。但这种写法依然依赖全局变量，函数不可重入，多线程场景下还是会出问题。

方案2：彻底移除全局变量（推荐）

把N和count都改成函数内的局部变量，通过参数传递给递归函数。C语言函数参数默认是值传递，计数变量通过指针传递，每次调用的状态完全独立，不会互相干扰。修改后的可提交代码如下：

void rowExpansion(int n, int r, int cols, int diags, int aDiags, int *count)
{   
    if (r < n)
    {
        for (int c=0; c<n; c++)
        {
            int cD = r - c + n, cAd= r + c;
            if ((cols & (1 << c)) || (diags & (1 << cD)) || (aDiags & (1 << cAd))) 
                continue;
            rowExpansion(n, r+1, cols | 1<<c, diags | 1<<cD, aDiags | 1<<cAd, count);
        }
    }
    else {
        (*count)++;
    }
}

int totalNQueens(int n)
{    
    int count = 0; // 局部变量，每次函数调用都会独立初始化为0
    rowExpansion(n, 0, 0, 0, 0, &count);
    return count;
}

这个版本没有任何全局变量，不管连续调用多少次、甚至多线程同时调用，每个调用的计数都是独立的，完全不会出现状态污染问题，可以正常通过所有在线评测用例。

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