8 Queens Problem with Recursive Function in CPP

Eight Queens Problem with Recursive Function in C++

A fun problem that can be solved using recursion is the Eight Queens Problem. The goal is to place eight queens on a chessboard so that none is in the same row or column or diagonal of the board. The Program for 8 Queens Algorithm will ensure the following operations
1. No two queens share a column
2. No two queens share a row
3. No two queens share a / diagonal
4. No two queens share a \ diagonal

The CPP Program Code for 8 Queens Problem

/*
* 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;
}


Related Topic C Programming 8 Queens Problem with Recursive Function
8 Queens Problem Backtracking Algorithm and Java Program
How to get the Basic Information of the machine Using CentOS
How to Create the Dynamic Folder Tree Links Navigation
The Example PHP Code to Create a User Session ID

nScraps.com 2011   Privacy Policy  Terms of Service  Feedback