#include <iostream.h> // for cin, cout
#include <iomanip.h> // for setw
#include <stdlib.h> // for abs
typedef int index;
class nQueens {
public:
nQueens(int n) {
this->n = n;
col = new int[n]; // array with coordinates of queens
~nQueens() {
delete col;
}
void start();
void finish();
void queens(index i);
bool promising(index i);
void OutputSolution();
private:
int n; // Dimension of board
index *col; // col[0..n-1]: col[i]=j means queen at row i, column j
// Statistics: count number of solutions and (non)promising nodes examined.
int numSolutions, numNonPromising, numPromising;
};
void nQueens::start() {
numSolutions = 0; // initialize statistics
numNonPromising = 0;
numPromising = 0;
queens(0); // start search for solutions
}
void nQueens::finish() {
// Display statistics
cout << "# solutions = " << numSolutions;
cout << " # promising nodes = " << numPromising;
cout << " # non-promising nodes = " << numNonPromising << endl;
}
// Main routine to traverse nodes of state space tree
void nQueens::queens(index i) {
// Continue only if columns 0,...,i-1 are promising.
if (promising(i-1)) {
numPromising++;
if (i==n) { // Have a complete solution.
numSolutions++;
OutputSolution();
} else {
for (index j=0; j<n; j++) f // place queen in
col[i] = j; // row i, column j
queens(i+1); // and continue to next row
}
}
} else numNonPromising++;
}
// Check if a node is promising
bool nQueens::promising(index i) { // Check if queen in row k threatens queen in row i
for (index k=0; k<i; k++)
if (col[i] == col[k] || abs(col[i]-col[k]) == i-k)
return false; // does threaten, so not promising
return true; // no threats, so promising
}
// Display each solution as it's found, and statistics
void nQueens::OutputSolution() {
cout << setw(3) << numSolutions
<< " " << setw(3) << numPromising
<< " " << setw(3) << numNonPromising << " ";
for (index i=0; i<n; i++)
cout << "(" << i+1 << "," << col[i]+1 << ") ";
cout << endl;
}
int main(int argc, char *argv[]) {
int n;
cout << "n-Queens" << endl;
do {
cout << "Enter n, or 0 to quit: ";
cin >> n;
if (n>0) {
cout << " # #P #P coordinates" << endl;
nQueens *nq = new nQueens(n);
nq->start();
nq->finish();
delete nq;
}
} while (n>0);
return 0;
}