N queens using backtracking

Question

I have implemented a solution for the N queens problem by using backtracking. I am checking whether the position of every queen is safe or not by checking its top left, top right and top and then placing it in the row, otherwise I backtrack.

It is giving a correct solution for some values of N, such as 4 and 8, but incorrect for others, such as 6.

I don't know what I am missing. Any help would be highly appreciated.

Here's the code:

int S;
static int cnt=0;

int safepos(int board[][S+1],int i,int j)
{
    if(i==1)        
    return 1;

    int a,b;
    a=i-1;
    b=j-1;

    //checking for top-left side
    while(a>0 && b>0 )
    {
        if(board[a--][b--]==1)
        return 0;
    }

    a=i-1;
    b=j+1;
    //checking for top-right side    
    while(a>0 && b<=S )
    {
        if(board[a--][b++]==1)
        return 0;
    }

    //checking for the same column        
    for(a=1;a<i;a++)
        if(board[a][j]==1)
            return 0;
    return 1;
}

void Nqueens(int board[][S+1],int N,int n)  //n is the number of the rows
{
    if(n==N+1) //for those which reaches the last position we will have a solution
    {
        cnt++;
        return;    
    }
    int i;    
    for(i=1;i<=N;i++)  //for every column
    {
        if( safepos(board,n,i) )
        {
            board[n][i]=1;    
            Nqueens(board,N,n+1);  //checking for next row
        }
        board[n][i]=0;
    }
}

int main()
{
    int N=6;
    S=N;
    int board[N+1][N+1];    
    Nqueens(board,N,1);
    printf("%d",cnt);
    return 0;
}

Answer 1

Your implementation of the backtracking idea is correct, the problem comes from the fact that the values of the array 'board' have to be initialized to zero manually, by default the array comes with undefined values. If you do that, you should get the correct answer, I tested the code. For more information related to array initialization, see http://www.fredosaurus.com/notes-cpp/arrayptr/array-initialization.html

Answer 2

I know this has an accepted answered but wanted to share my implementation that uses a vector initialized to -1 and not zero as to not interfere with zero offset for row = 0

#include <iostream>
#include <vector>

const int GRID_SIZE = 8;


bool isValid ( int queenNum, int col, std::vector<int>& cols )
{
  // check for other queen number that collide with this one
  for ( int queenRow = 0; queenRow < queenNum; ++queenRow )
  {
    int queenCol = cols[queenRow];

    if ( col == queenCol )  
      return false; // same col

    if ((queenNum - queenRow) == abs( queenCol-col))
      return false; // same diagonal
  }
  return true;
}

void solve( int queenNum, std::vector<int>& cols,  std::vector<std::vector<int> >& results  )
{
  if ( queenNum == GRID_SIZE) 
  {
    // we have a solution 
    results.push_back (cols);
  }

  for ( int i = 0; i < GRID_SIZE; ++ i)
  {
    if ( isValid(queenNum,i,cols) )
    {
      cols[queenNum] = i;
      solve(queenNum + 1,cols, results);
    }
  }
}

void drawLine() {
  std::string line;
  for (int i=0;i<GRID_SIZE*2+1;i++)
    line.append("-");
  std::cout << line << std::endl;
}

void printBoard(std::vector<int>& cols) 
{
  drawLine();
  for(int i = 0; i < GRID_SIZE; i++){
    std::cout << "|";
    for (int j = 0; j < GRID_SIZE; j++){
      if (cols[i] == j) {
        std::cout << "Q|";
      } else {
        std::cout << " |";
      }
    }
    std::cout << std::endl;
    drawLine();
  }
  std::cout << "" << std::endl;;
}

void printBoards(std::vector<std::vector<int> >&  boards) {
  for (int i = 0; i < (int)boards.size(); i++) 
  {
    printBoard(boards[i]);
  }
}



int main ()
{
  std::vector<int> cols ( GRID_SIZE, -1);
  std::vector<std::vector<int> > results;
  solve(0, cols, results );
  printBoards(results);
  std::cout << results.size() << std::endl;
  return 0;
}