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:
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:
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:
Same with can_place()function, for each given row, we can replace can_place() function with one compound statement:
So the whole program becomes:
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:
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.
[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));
}
}
