Given a 8 X 8 chessboard. The task is to place 8 queens on the board, such that no two queens attack each other. Return all distinct possible solutions for the 8 queens problem.
Approach: Bruteforce
A simple brute-force solution would be to generate all possible chess boards with 8 queens. Accordingly, there would be N^2 positions to place the first queen, N^2 – 1 position to place the second queen and so on.
The total time complexity, in this case, would be O(N^(2N)), which is too high.
Confused about your next job?
In the above image, suppose we place the first two queens adjacently. The other 6 queens can have 62! = 62 * 61 * 60 *….. = 44,261,653,680 ways to place in the board, but these all are invalid since the first two queens would attack each other. This leads to unnecessary calculations, therefore we need to optimise the above approach.
Efficient Approach: Backtracking
The idea is to apply a backtracking approach to solve the problem. The backtracking function does the following:
- Places only 1 queen per row satisfying the conditions.
- Places only 1 queen per column satisfying the conditions.
For the diagonals, the value of (row – col) is constant and the main diagonal is 0.
Similarly, for anti-diagonal, the value of (row + col) is constant.
From, the above, we can keep track of the rows and columns which have been used already. Therefore, no more queens can be placed in such rows/columns.
Algorithm:
- Create a function backtrack that simply places the queens on corresponding rows and columns and marks them visited.
- The working of backtrack is as follows:
- If the current row is equal to 8, then a solution has been found. Therefore, add this to the answer.
- Traverse through the columns of the current row. At each column, try to place the queen in (row, col):
- Calculate the diagonal and anti-diagonal which the current square belongs to. If it is unvisited, place the queen in the (row, col).
- Skip this column, if the queen cannot be visited.
- If the queen has been placed successfully, call the backtrack function of row + 1.
- Since, all paths have now been explored, clear the values of the queens placed so far and the visiting arrays, so that next distinct solution can be found.
Implementation of the Approach
C++ Implementation
std::vector<std::vector<std::string> > solveNQueens(int n) {
std::vector<std::vector<std::string> > res;
std::vector<std::string> nQueens(n, std::string(n, '.'));
solveNQueens(res, nQueens, 0, n);
return res;
}
private:
void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) {
if (row == n) {
res.push_back(nQueens);
return;
}
for (int col = 0; col != n; ++col)
if (isValid(nQueens, row, col, n)) {
nQueens
= 'Q';
solveNQueens(res, nQueens, row + 1, n);
nQueens
= '.';
}
}
bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) {
for (int i = 0; i != row; ++i)
if (nQueens[i]
== 'Q')
return false;
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
if (nQueens[i][j] == 'Q')
return false;
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
if (nQueens[i][j] == 'Q')
return false;
return true;
}
JavaImplementation
private int size;
private List<List<String>> solutions = new ArrayList<List<String>>();
public List<List<String>> solveNQueens(int n) {
size = n;
char emptyBoard[][] = new char[size][size];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
emptyBoard[i][j] = '.';
}
}
backtrack(0, new HashSet<>(), new HashSet<>(), new HashSet<>(), emptyBoard);
return solutions;
}
private List<String> createBoard(char[][] state) {
List<String> board = new ArrayList<String>();
for (int row = 0; row < size; row++) {
String current_row = new String(state
);
board.add(current_row);
}
return board;
}
private void backtrack(int row, Set<Integer> diagonals, Set<Integer> antiDiagonals, Set<Integer> cols, char[][] state) {
if (row == size) {
solutions.add(createBoard(state));
return;
}
for (int col = 0; col < size; col++) {
int currDiagonal = row - col;
int currAntiDiagonal = row + col;
if (cols.contains(col) || diagonals.contains(currDiagonal) || antiDiagonals.contains(currAntiDiagonal)) {
continue;
}
cols.add(col);
diagonals.add(currDiagonal);
antiDiagonals.add(currAntiDiagonal);
state
= 'Q';
backtrack(row + 1, diagonals, antiDiagonals, cols, state);
cols.remove(col);
diagonals.remove(currDiagonal);
antiDiagonals.remove(currAntiDiagonal);
state
= '.';
}
}
PythonImplementation
def solveNQueens(self, n):
def create_board(state):
board = []
for row in state:
board.append("".join(row))
return board
def backtrack(row, diagonals, anti_diagonals, cols, state):
if row == n:
ans.append(create_board(state))
return
for col in range(n):
curr_diagonal = row - col
curr_anti_diagonal = row + col
if (col in cols
or curr_diagonal in diagonals
or curr_anti_diagonal in anti_diagonals):
continue
cols.add(col)
diagonals.add(curr_diagonal)
anti_diagonals.add(curr_anti_diagonal)
state
= "Q"
backtrack(row + 1, diagonals, anti_diagonals, cols, state)
cols.remove(col)
diagonals.remove(curr_diagonal)
anti_diagonals.remove(curr_anti_diagonal)
state
= "."
ans = []
empty_board = [["."] * n for _ in range(n)]
backtrack(0, set(), set(), set(), empty_board)
return ans
- Time Complexity: O(N!), where N is the size of the board.
- Space Complexity: O(N^2), since visiting array is used.
Practice Questions
FAQ
Q.1: What is the most efficient approach to solving the N queens problem?
Ans: The backtracking approach is the most efficient approach since it takes O(N!) time.
Q.2: How does the backtrack function work?
Ans: The backtrack function explores all paths possible by placing the queens on the rows and the columns. It keeps a visiting set to keep track of the rows and columns which have been already used.
