8 Queens Problem

8 Queens Problem

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.

8 queens

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.

bruteforce solution

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.

diagonals

Similarly, for anti-diagonal, the value of (row + col) is constant.

anti-diagonal

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

NQueens

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.

Previous Post
water jug problem

Water Jug Problem

Next Post
Difference Between CSS and CSS3

Difference Between CSS and CSS3

Total
0
Share