Backtracking Algorithm N Queens C++ Explanation

EXPLANATION:

Question Link

Today we will learn the backtracking algorithm N-Queens, using code, real-life chessboard and the movie Breakfast Club.

Notes:

1.Backtracking is when we use recursion to build a solution, one piece at a time, and keep removing those solutions which fail at any stage. A solution fails when it doesn’t satisfy the constraint set up by the problem, and then we stop expanding it further from the stage where it dissatisfied the problem constraint. Which can be represented quite well by search trees.

2.Queens in chess are quite powerful and can move any paces up or down, left or right, diagonally 45 degrees or 135 degrees. This means any two queens which happen to be in the same column, or row or diagonal can attack each other.

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Below is a C++ code which uses backtracking to solve this question. I have tried to make it as clear as possible in terms of code and explanation (check out the video!)
The chessboard plays an important role in understanding this algorithm. We can do this for any number of tiles, and many solutions can be found for the same N-Queens in the N X N  chessboard.

If you want a much more visual explanation, check out this video.

If you have any doubts, feel free to ask in the comments below.

CODE:

class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > res;
vector<string> nQueens(n, string(n, ‘.’));
solveNQueens(res, nQueens, 0, n);
return res;
}

private:
void solveNQueens(vector<vector<string> > &res, vector<string> &nQueens, int row, int &n) {
//return if all rows are filled
if (row == n) {
res.push_back(nQueens);
}
for (int col = 0; col != n; ++col)
if (isValid(nQueens, row, col, n)) {
nQueens[row][col] = ‘Q’;
solveNQueens(res, nQueens, row + 1, n);
nQueens[row][col] = ‘.’; //backtracking step
}

}

bool isValid(vector<string> &nQueens, int row, int col, int &n) {


//check if the column had a queen before.
for (int i = 0; i != row; ++i)
if (nQueens[i][col] == ‘Q’)
return false;


//check if the 45° diagonal had a queen before.
for (int i = row – 1, j = col – 1; i >= 0 && j >= 0; i–, j–)
if (nQueens[i][j] == ‘Q’)
return false;


//check if the 135° diagonal had a queen before.
for (int i = row – 1, j = col + 1; i >= 0 && j < n; i–, j++)
if (nQueens[i][j] == ‘Q’)
return false;

return true;
}
};

 

For more such solutions check out our CODING section.

Leave a Reply

Your email address will not be published. Required fields are marked *