N Queens - codepath/compsci_guides GitHub Wiki

• 🔗 Leetcode Link: https://leetcode.com/problems/n-queens/
• 💡 Difficulty: Hard
• ⏰ Time to complete: 20 mins
• 🛠️ Topics: Backtracking
• 🗒️ Similar Questions: N-Queens II

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Where can a queen move?
  • A queen can attack horizontally, vertically, or diagonally. A queen can move any number of steps in any direction. The only constraint is that it can’t change its direction while it’s moving.
• Can a queen be in the same row or column?
  • No two queens can be in the same row or column. That allows us to place only one queen in each row and each column.
• How can we check if we've reached the end?
  • If row == N, we've filled in all our rows successfully which implies the current board state is a valid combination

Run through a set of example cases:

Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Example 2:
Input: n = 1
Output: [["Q"]]

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

• How can N queens be placed on an NxN chessboard so that no two of them attack each other? Backtracking can be used since we start with one pos­si­ble move out of many avail­able moves. The three general steps include: the general steps of backtracking are: start with a sub-solution check if this sub-solution will lead to the solution or not. If not, then come back and change the sub-solution and continue again.

The way we try to solve this is by placing a queen at a position and trying to rule out the possibility of it being under attack. We place one queen in each row/column. If we see that the queen is under attack at its chosen position, we try the next position. If a queen is under attack at all the positions in a row, we backtrack and change the position of the queen placed prior to the current position. We repeat this process of placing a queen and backtracking until all the N queens are placed successfully.

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Try a promising Queen position, see how it goes. If it fails, undo that Queen and try again somewhere else.

Check if we've reached the end:
If row == N, we've filled in all our rows successfully which implies the current board state is a valid combination. Let's add it to our output list.
Loop through each column in the current row.
3. If we can't add a Queen at this position, skip this col value.
If we can, add a Queen at this position and adjust our bitmasks respectively.
Continue to the next row (call backtrack for row+1).
Undo our changes so we can try other col values.

⚠️ Common Mistakes

• What are some common pitfalls students might have when implementing this solution?

• For an 8×8 board, we have to choose positions for 8 identical queens from 64 different squares, which can be done in 64C8 = 4426165368 ways. You can tighten this up by enforcing one queen in each row through the use of 8 nested loop. Using such nested loops, we would only have to look at 44=256 configurations for a 4×4 board and 88 configurations for an 8×8 board --- that's still far too many.

• Pay attention to the last inserted value. It can conflict with previous rows if the column difference is 0 (the Queens are on the same column line) or if column difference = row difference (Queens are on one diagonal)

Implement the code to solve the algorithm.

class Solution:
    def solveNQueens(self, n):
        # Making use of a helper function to get the
        # solutions in the correct output format
        def create_board(state):
            board = []
            for row in state:
                board.append("".join(row))
            return board
        
        def backtrack(row, diagonals, anti_diagonals, cols, state):
            # Base case - N queens have been placed
            if row == n:
                ans.append(create_board(state))
                return

            for col in range(n):
                curr_diagonal = row - col
                curr_anti_diagonal = row + col
                # If the queen is not placeable
                if (col in cols 
                      or curr_diagonal in diagonals 
                      or curr_anti_diagonal in anti_diagonals):
                    continue

                # "Add" the queen to the board
                cols.add(col)
                diagonals.add(curr_diagonal)
                anti_diagonals.add(curr_anti_diagonal)
                state[row][col] = "Q"

                # Move on to the next row with the updated board state
                backtrack(row + 1, diagonals, anti_diagonals, cols, state)

                # "Remove" the queen from the board since we have already
                # explored all valid paths using the above function call
                cols.remove(col)
                diagonals.remove(curr_diagonal)
                anti_diagonals.remove(curr_anti_diagonal)
                state[row][col] = "."

        ans = []
        empty_board = [["."] * n for _ in range(n)]
        backtrack(0, set(), set(), set(), empty_board)
        return ans

class Solution {
    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;
    }
    
    // Making use of a helper function to get the
    // solutions in the correct output format
    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[row]);
            board.add(current_row);
        }
        
        return board;
    }
    
    private void backtrack(int row, Set<Integer> diagonals, Set<Integer> antiDiagonals, Set<Integer> cols, char[][] state) {
        // Base case - N queens have been placed
        if (row == size) {
            solutions.add(createBoard(state));
            return;
        }
        
        for (int col = 0; col < size; col++) {
            int currDiagonal = row - col;
            int currAntiDiagonal = row + col;
            // If the queen is not placeable
            if (cols.contains(col) || diagonals.contains(currDiagonal) || antiDiagonals.contains(currAntiDiagonal)) {
                continue;    
            }
            
            // "Add" the queen to the board
            cols.add(col);
            diagonals.add(currDiagonal);
            antiDiagonals.add(currAntiDiagonal);
            state[row][col] = 'Q';

            // Move on to the next row with the updated board state
            backtrack(row + 1, diagonals, antiDiagonals, cols, state);

            // "Remove" the queen from the board since we have already
            // explored all valid paths using the above function call
            cols.remove(col);
            diagonals.remove(currDiagonal);
            antiDiagonals.remove(currAntiDiagonal);
            state[row][col] = '.';
        }
    }
}

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Given n as the number of queens (which is the same as the width and height of the board),

• Time Complexity: O(n!), because we are selecting if we can put or not put a Queen at that place
• Space Complexity: O(n^2), extra memory used includes the 3 sets used to store board state, as well as the recursion call stack