N-皇后问题解数中的误差检测

Question

编程问题描述

n皇后难题是把n皇后放在n x n棋盘上的问题，这样就不会有两个皇后互相攻击。给定整数n，返回n皇后谜题的不同解决方案的数目。1 ≤ n ≤ 9是测试用例的约束。

[取自这里]

我的尝试

我试着用比特掩蔽来解决这个问题。简而言之，我们尝试所有可能的组合，并在解决方案不可能时回溯。

我们放置皇后逐行，每一个位置，我们限制一些位置/框中剩余的皇后不能被放置。

现在，我们可以通过anti-diagonal的index来识别每个列，对角线具有相同row index - column index的属性，而具有相同的row index + column index属性。

因此，在将皇后放置在任何方框后，我们将限制列、对角线和反对角线。这将通过为所有三个参数设置一个位掩码变量来完成。

下面是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上给出了正确的输出。

#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. 评论中的用户将错误归咎于全局变量。有人能更清楚地了解为什么会发生这种情况，并提示如何从这段代码中消除全局变量吗？

Answer 1

主要问题是变量count是如何使用的。

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代码，它可以按照预期“工作”，但是它没有提供，所以我们只能猜测它没有这个bug。

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

注意，我还使用了一个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)的情况下重写代码将导致在线判断是否接受它。