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 bruteforce 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.

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.

- Calculate the
- 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.

- If the current row is equal to

## 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**. **What is the most efficient approach to solve the N queens problem?**The backtracking approach is the most efficient approach since it takes O(N!) time.

**Q. How does the backtrack function work?**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.