#include using namespace std; #include "tmatrix.h" #include "prompt.h" class Queens { public: Queens(int size); bool Solve(); void Print(ostream& out) const; private: int mySolutionCount; bool NoQueensAttackingAt(int r, int c) const; bool SolveAtCol(int col); tmatrix myBoard; }; bool Queens::NoQueensAttackingAt(int r, int c) const // pre: column c is clear // post: return true if row clear and diagonals crossing at // (r,c) clear { int k, row,col; // check row r for(k=0; k < myBoard.numcols(); k++) { if (k != c && myBoard[r][k]) return false; } // check diagonal northwest row = r-1; col = c-1; while (0 <= row && 0 <= col) { if (myBoard[row][col]) return false; row--; col--; } // check diagonal southeast row = r+1; col = c+1; while (row < myBoard.numrows() && col < myBoard.numcols()) { if (myBoard[row][col]) return false; row++; col++; } // check diagonal northeast row = r-1; col = c+1; while (0 <= row && col < myBoard.numcols()) { if (myBoard[row][col]) return false; row--; col++; } // check diagonal southwest row = r+1; col = c-1; while (row < myBoard.numrows() && 0 <= col) { if (myBoard[row][col]) return false; row++; col--; } return true; } Queens::Queens(int size) : myBoard(size,size,false) // post: board initialized to hold no queens { } bool Queens::Solve() // post: returns true if n queens can be placed, false otherwise { mySolutionCount = 0; return SolveAtCol(0); } bool Queens::SolveAtCol(int col) // pre: queens placed at columns 0,1,...,col-1 // post: returns true if queen can be placed in column col // if col == size of board, then n queens are placed { int k; int rows = myBoard.numrows(); if (col == rows) { mySolutionCount++; return true; } for(k=0; k < rows; k++) { if (NoQueensAttackingAt(k,col)) { // row k is clear, try it myBoard[k][col] = true; // place the queen if (SolveAtCol(col+1)) { // try remaining columns // return true; // placed them all! } myBoard[k][col] = false; // couldn't place, remove queen } } return false; } void Queens::Print(ostream& out) const // post: board printed, 'X' for queen { cout << mySolutionCount << " solutions" << endl; return; int j,k; for(j=0; j < myBoard.numrows(); j++) { for(k=0; k < myBoard.numcols(); k++) { out << (myBoard[j][k] ? 'X' : '.'); } out << endl; } } int main() { int size = PromptRange("size of board: ",2,100); Queens nq(size); nq.Solve(); nq.Print(cout); return 0; if (nq.Solve()) { nq.Print(cout); } else { cout << "no solution found" << endl; } return 0; }