Programming

Here is the same code with added main and other functionalities to make it reprex, it gave correct output on 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);
    }
}

As background, I use to practice mostly in python and not very much skilled in c programming.

---

Doubt(s)

1. What is the error in this code? Is the error logical, syntactical or runtime-error?
2. Why it happens that same code on console is successful, but fails on submitting? Can someone provide good reference for the same?
3. Users in comments blamed Global Variables for the error. Can someone throw more light on why this happen, and provide hint on how to get rid of global variables from this code?

CodePudding user response：

The main problem is how the variable count is used.

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
}

If the function totalNQueens is called more than once, it just accumulates the count, because count is never resetted.

The OP mention a Python code that "works" as expected, but it's not provided, so we can only guess that it doesn't have this bug.

I'd suggest not to use a global variable, in the first place. The following is a possible alternative implementation.

Note that I also used an unsigned type to perform all the bit manipulations.

#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));
  }
}

CodePudding user response：

Rewriting the code with no external variables (N and count) results in the online judging accepting it.