Search code examples
cbit-manipulationbacktrackingbitmaskn-queens

Detecting error in Number of Solutions in N-Queens Problem

Programming Problem Description

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle. The 1 ≤ n ≤ 9 are the constraints of Test Cases.

[Taken from here]

My Attempt

I tried to solve the problem using bit-masking. In short, we try all possible combination, and backtrack whenever solution is not possible.

We place queen row-by-row, and with each placement, we restrict some positions/box where remaining queens cannot be placed.

Now, we can identify each column by it's index, diagonal have property of same row index - column index, and anti-diagonal have property of same row index + column index.

Thus, after placing queen at any box, we will restrict columns, diagonals and anti-diagonals identified by that box. This will be done by having a bit-mask variable for all three parameters.

Here is the code in c for the same (which was submitted on Online Judge).

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++;
}

This code was working fine on Console, but on submitting it produced error. For n=1, code was giving correct output in Console, but giving wrong answer on submitting. I tried to code same technique in python and it worked fine.

Attached is the screenshot of error.

Screenshot

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?
Solution

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