8 Queens Problem with Recursive Function in CPP

/*
* File: queens.cpp
* -----------------
* This program implements a graphical search for a solution to the N
* N queens problem, utilizing a recursive backtracking approach. See
* comments for Solve function for more details on the algorithm.
*/
#include "chessGraphics.h" // routines to draw chessboard & queens
const int NUM_QUEENS = 8;
bool Solve(Grid<bool> &board, int col);
void PlaceQueen(Grid<bool> &board, int row, int col);
void RemoveQueen(Grid<bool> &board, int row, int col);
bool RowIsClear(Grid<bool> &board, int queenRow, int queenCol);
bool UpperDiagIsClear(Grid<bool> &board, int queenRow, int queenCol);
bool LowerDiagIsClear(Grid<bool> &board, int queenRow, int queenCol);
bool IsSafe(Grid<bool> &board, int row, int col);
void ClearBoard(Grid<bool> &board);
int main()
{
Grid<bool> board(NUM_QUEENS, NUM_QUEENS);
InitGraphics();
ClearBoard(board); // Set all board positions to false
DrawChessboard(board.numRows()); // Draw empty chessboard
Solve(board,0); // Attempt to solve the puzzle
return 0;
}

/*
* Function: Solve
* ---------------
* This function is the main entry in solving the N queens problem. It takes
* the partially filled board and the column we are trying to place queen in.
* It will return a boolean value which indicates whether or not we found a
* successful arrangement starting from this configuration.
*
* Base case: if there are no more queens to place, we have succeeded!
*
* Otherwise, we find a safe row in this column, place a queen at (row,col)
* recursively call Solve starting at the next column using this new board
* configuration. If that Solve call fails, we remove that queen from (row,col)
* and try again with the next safe row within the column. If we have tried all
* rows in this column and haven't found a solution, we return false from this
* invocation, which will force backtracking from this unsolvable configuration.
*
* The starting call to Solve has an empty board and places a queen in col 0:
* Solve(board, 0);
*/
bool Solve(Grid<bool> &board, int col)
{
if (col >= board.numCols()) return true; // base case
for (int rowToTry = 0; rowToTry < board.numRows(); rowToTry++) {
if (IsSafe(board, rowToTry, col)) {
PlaceQueen(board, rowToTry, col); // try queen here
if (Solve(board, col + 1)) return true; // recur to place rest
RemoveQueen(board, rowToTry, col); // failed, remove, try again
}
}
return false;
}
/*
* Function: PlaceQueen
* --------------------
* Places a queen in (row,col) of the board by setting value in
* grid to true and drawing a 'Q' in that square on the displayed chessboard.
*/
void PlaceQueen(Grid<bool> &board, int row, int col)
{
board(row, col) = true;
DrawLetterAtPosition('Q', row, col, "Black");
}
/*
* Function: RemoveQueen
* ---------------------
* Removes a queen from (row,col) of the board by setting value in grid to
* false and erasing the 'Q' from that square on the displayed chessboard.
*/
void RemoveQueen(Grid<bool> &board, int row, int col)
{
board(row, col) = false;
EraseLetterAtPosition(row, col);
}

class board {
public:
// Places a queen on the appropriate square
// Pre-conditions: 1 <= row, column <= 8
void setQueen(int row, int column);
// Sets the appropriate square to empty (whether it has a queen or not)
// Pre-conditions: 1 <= row, column <= 8
void removeQueen(int row, int column);
//Determines whether a queen can be placed on a square
// Pre-conditions: 1 <= row, column <= 8
bool legalPosition(int row, int column) const;
}
//Places queens in column col and subsequent columns. Returns true if successful, false otherwise
//Pre-condition: queens have been placed legally in all columns from 1 to col-1 (inclusive)
bool placeQueens(board &b, int col)
{
if (col > 8) return true;
for (int row=1; row<=8; row++)
{
if (b.legalPosition(row, col))
{
b.setQueen(row, col);
bool solved = placeQueens(b, col+1);
if (!solved) b.removeQueen(row, col);
else return true;
}
}
return false;
}