N Queen Problem

N Queen Problem:

Solutions:

   The entire chessboard should be stored as an 1-dimensional array with the length of N, and is represented with A[N]. The value of the i-th element in A[i] represents the queen column position of the i-th row.

    For example:  A[5] = 3 represents a position of (5,3), the 5th row and the 3rd column.    

So, given arbitrary two rows: i,j (i!=j) and it corresponding two cols should be: A[i], A[j].

The conflict should happen in one of the cases:

1) A[i] == A[j]   column conflict case;

2) A[i] - A[j] == (i - j) or (j - i) two diagonal conflict cases;

So the first step is to find out if we can place a queen in (row, col) the algorithm should be:

[code]

bool OKtoPlace(int row, int col)
{ 
     for (int r = 0; r < row; r++) {
        if (A[r] == col || A[r] - col ==  row - r || A[r] - col == r - row)
               return false;
      }
      return true;
}

   The next step is how to find all possible solutions. This is a classic backtracking algorithm, there are two ways for implementation, recursive and non-recursive. and rescursive method is relatively simple, here is the workflow:

       

[code]
void Queen(int row)
{
    if (n == row) {     // if all row are done, print out result;                  
       count ++;       // a new possible solution found. 
       print_result();
    }
    else {
       for (int col = 0; col < N; col++) {    //try each col on the row
            if (can_place(row, col) {  // is it ok to set the queen on (row, col) ?
                   place(row, col);    // set the queen
                   queen(row + 1);     // move to the next row
             }
        }
}
 

Now combine the above two steps we get
Solution 1:

       

[code]

const int N = 8;
int A[N];
int count = 0;

void print_out(void){
    for(int r=0; r<N; r++){
        for(int c=0; c<N; c++){
            if(c == A[r]) cout<< "Q ";
            else cout<< "0 ";
        }
        cout<<endl;
    }
    cout<<endl;
}

bool OktoPlace(int row, int col)
{
    for (int r= 0; r<row; r++) {
        if (A[r] == col || A[r] -col == row -r || A[r] - col == row - r)
           return false;
    }
    return true;
}

void queen(int row)
{
    if(row == N) {
       count ++;
       print_out();
       return;
    }

    for (int col = 0; col < N; col++) {
         if(OktoPlace(row, col)) {
             A[row] = col;
             queen(row + 1);
        }
    }
}

int main(void)
{
    queen(0);
    cout << count << endl;
    return 0;
}

         

Now let's see if we can optimize the core algorithm.

Solution 2:

As we can see that in the above function OKtoPlace(int row, int col), the time complexity is O(N), we can reduce it to O(1) by introducing two extra 1-dimensional bool arrays: P, Q.  Each represents the diagonal elements of a position, so the sizeof P and Q is 2N-1. Now for any position [row, col] on the board, we need to check if any one of 
[col, row+col, N-1 +col + row]
has a conflict.

So for each given row, we can replace place() function with one compound statement:

[code]

bool C[N], P[2*N-1], Q[2*N-1];

C[col] = true; P[row+col] = true; Q[N-1+col-row] = true;

     

Same with can_place()function, for each given row, we can replace can_place() function with one compound statement:

[code]

if (C[col] == true || P[row+col] == true || Q[N-1+col-row] == true)  //conflict
else  // no conflict and good to place.    

So the whole program becomes:

[code]
const int N = 8;
bool C[N], P[2*N-1], Q[2*N-1];

int count = 0;

void queen(int row)
{
    if (row == N) {
       count ++;
       return;
    }
    for (int col = 0; col < N; col++) {
        if (C[col] || P[row + col] || Q[N-1 + col - row]) continue; //conflict on this position
        C[col] = true; P[row+col] = true; Q[N-1+col-row] = true;
        queen(row + 1);
        C[col] = false; P[row+col] = false; Q[N-1+col-row] = false;
    }
}

Solution 3:
we can replace these three 1 dimensional Boolean arrays with only three integers C,P,Q , each bit in [C,P,Q] represents [col, row+col, N-1 +col + row] like above:

So the whole program becomes:

[code]

const int N = 8;
int C, P, Q;

int count = 0;

void queen(int row)
{
    if (row == N) {
       count ++;
       return;
    }
    for (int col = 0; col < N; col++) {
        if ( (C>>col) &1|| P>>(row + col) & 1 || Q >> (N-1 + col - row) & 1) continue;
        C ^= (1 << col);  P ^=(1 << (row+col)); Q ^= ( 1 << (N-1+col-row));
        queen(row + 1);
        C ^= (1 << col);  P ^=(1 << (row+col)); Q ^= ( 1 << (N-1+col-row));
    }
}