Query about N- Queen problem?

Question

I solved the N- Queen problem with the condition that there can only be one queen per column. So I place a queen in a square in first column, then move onto the next column and place a queen in a square not attacked by the queen on board. I am able to find all solutions with this approach but it starts taking a long time after n=13. Also I found that most of the solutions of the problem can be found by rotations and reflections of a very few distinct solutions.E.g 8 queen problem has 92 total solutions out of which only 12 are distinct. (http://en.wikipedia.org/wiki/Eight_queens_puzzle)

So my question is how do I check for these states of the board and only push those states onto the stack which give a distinct solution?

This is what I am doing right now.

typedef struct state{
    int board[N][N];
    int col;
}state;

state cur;
state next;

stack<state> myS;
myS.push(emptyBoard);

while(!myS.empty()){           
      cur=myS.top(); myS.pop();
      if(cur.col==n){
          count++;
          continue;
      }
      for(i=0;i<n;i++){
          next=cur;
          if(cur.board[i][cur.col]==available){
              next.board[i][cur.col]=occupied;
              markConflicts(i,cur.col);          //mark squares attacked by queen as conflicted
              next.col=cur.col+1;
              myS.push(next);
          }
      }  
  } 

Answer 1

Well, you can only check for a unique solution once you have a solution. The place to check is at the point you increment the count variable. At this point, compare the current board to a set of unique boards and if it's not in the set then add the new solution to it.

As for your speed, your solution has a bottleneck when pushing and popping the state value. The bigger the board, the slower this becomes.

A much faster way is to only have one board and have each square keep a count og the number of queens controlling the square. So you'd have this:

function scan (column)
   if column == number of columns (zero based index)
     check solution
   else
     if there's a free space
       add queen
       increment controlled squares in columns to right of current column
       scan (column+1)
       decrement controlled squares in columns to right of current column
       remove queen

This has far less data being pushed / popped and will greatly increase the speed.