在N-Queens問題中檢測解數中的錯誤

編程

這是相同的代碼，添加了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. 評論中的用戶將錯誤歸咎于全域變數。有人可以更清楚地說明為什么會發生這種情況，并提供有關如何從該代碼中洗掉全域變數的提示嗎？

uj5u.com熱心網友回復：

主要問題是如何使用變數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 代碼，但它沒有提供，所以我們只能猜測它沒有這個錯誤。

我建議首先不要使用全域變數。以下是一種可能的替代實施方式。

請注意，我還使用了一種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));
  }
}

uj5u.com熱心網友回復：

在沒有外部變數（N和count）的情況下重寫代碼會導致在線判斷接受它。

標籤：C 位操作 回溯 位掩码 n皇后

上一篇：用亂數初始化一個const陣列

下一篇：當我嘗試獲取用戶輸入并列印出字串時發生了一些奇怪的事情