检测N- Queens问题中解决方案数量的误差

Question

编程问题描述

n-Queens 难题是将n Queens放在nx N棋盘上的问题，因此没有两个皇后区相互攻击。给定 整数n，返回 n-Queens难题 。 1≤n≤9是测试用例的约束。

[取自在这里]

---

我的尝试

我尝试使用位掩盖来解决问题。简而言之，我们尝试所有可能的组合，并在无法解决方案时回溯。

我们将女王放置划行，在每个位置时，我们都会限制某些位置/盒子，剩下的皇后区都无法放置。

现在，我们可以通过它的列 index，对角具有相同行索引 - 列索引 - 列索引， 抗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和其他功能的相同代码> preprex ，它在

#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. 为什么会发生相同的代码在 console 上是成功的，但在上失败了？有人可以为此提供良好的参考吗？
3. 注释中的用户指责该错误的全局变量。有人能否阐明为什么会发生这种情况，并提供有关如何摆脱此代码中全球变量的提示？

---

Answer 1

主要问题是如何使用变量计数。

int N;
int count=0;           // <-- Declaration of count as a GLOBAL variable

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

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

    return count;            // <-- Here it's returned
}

void rowExpansion(int r, int cols, int diags, int aDiags)
{
    if (r<N)
    {
        for (register int c=0; c<N; c++)
        {
            // ...

            rowExpansion(r+1, cols | 1<<c, diags | 1<<cD, aDiags | 1<<cAd);
        }
    }
    else count++;  // <-- Here it's modified
}

如果函数totalnqueens被称为多次，则它只是累积了计数，因为count永远不会重置。

OP提及的Python代码可以按预期进行“工作”，但没有提供，因此我们只能猜测它没有此错误。

我建议首先不要使用全局变量。 是可能的替代实现。

请注意，我还使用了unsigned类型来执行所有位操作。

#include <stdio.h>
#include <limits.h>

long long int rowExpansion( unsigned N
                          , unsigned r
                          , unsigned cols
                          , unsigned diags
                          , unsigned aDiags )
{   
  long long int count = 0;
  if ( r < N )
  {
    for ( unsigned c = 0; c < N; c++ )
    {
      unsigned cD = r - c + N;
      unsigned cAd = r + c;

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

      count += rowExpansion( N, r+1
                           , cols | 1u << c
                           , diags | 1u << cD
                           , aDiags | 1u << cAd );
    }
  }
  else {
    count++;
  }
  return count;
}

long long int totalNQueens(int n)
{    
  if ( n < 0 ) {
    return 0;
  }
  if ( (unsigned)n > sizeof(unsigned) * CHAR_BIT ) {
    puts("Too big.");
    return 0;
  }
  return rowExpansion(n, 0, 0, 0, 0);
}

int main(void)
{
  // https://oeis.org/A000170
  // 1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724 
  for (int i = 0; i <= 10; ++i)
  {
    printf("%lld\n", totalNQueens(i));
  }
}

Answer 2

重写没有外部变量的代码（n和count）会导致在线判断接受它。