Backtracking - question 51 Queen n -- a classic backtracking problem that must be overcome

1 Title Description

According to the rules of chess , The queen can attack the pieces on the same row, column or diagonal line .

n queens problem It's about how to make n A queen is placed in n×n On the chessboard , And keep the Queens from attacking each other .

Give you an integer n , Go back to all the different n queens problem Solutions for .

Each solution contains a different n queens problem The chess piece placement scheme of , The scenario ‘Q’ and ‘.’ They represent the queen and the vacant seat .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/n-queens

2 Title Example

Example 2：

Input ：n = 1
Output ：[[“Q”]]

3 Topic tips

1 <= n <= 9

4 Ideas

「N queens problem 」 It's about how to make N A queen is placed in NxN On the chessboard , And keep the Queens from attacking each other .
The Queen's way of walking is : You can go straight and diagonally , There is no limit to the number of lattices . Therefore, the queen is required not to attack each other , Equivalent to requiring that no two Queens can be on the same line 、 Same as — Columns and the same — On a slash .
The intuitive approach is that violent enumeration will N A queen is placed in N×N All possible situations on the chessboard , And judge whether the queen does not attack each other in each case . The time complexity of violent enumeration is very high , Therefore, it must be optimized by using constraints .
obviously , Each queen must be in different rows and columns , So it will N A queen is placed in N xN On the chessboard ,— It must be every — There is only one queen , There is only one queen in each column , And no two Queens can be in the same — On a slash . Based on the above findings , Possible solutions can be found by backtracking .
The specific method of backtracking is : Use an array to record the column subscript of the queen placed in each row , Place a queen in each row in turn . Every time a newly placed queen cannot attack an already placed queen : That is, the newly placed queen cannot be in the same column as any queen that has been placed — On a slash , And update the queen column subscript of the current row in the array . When N All the queens have been placed , Then find a possible solution . When a possible solution is found , Convert an array into a list representing the state of the chessboard , And add the checkerboard status list to the return list .
Because each queen must be in a different column , Therefore, the column of placed queens cannot place other queens . The first queen has N Columns can be selected , The second queen has at most N―1 Columns can be selected , The third queen has at most N-2 Columns can be selected ( If you consider that you can't be on the same slash , There are fewer possible options ), Therefore, all possible situations will not exceed N! Kind of , The time complexity of traversing these cases is O(N!).
To reduce the total time complexity , Each time you place a queen, you need to quickly judge whether each position can place a queen , obviously , The ideal situation is in O(1) Judge whether there is a queen on the column and two slashes where the position is located .

To judge — Whether there is a queen on the column where the two positions are located and the two slashes , Use three sets columns、diagonals, and diagonalsg Record whether there is a queen on each column and each slash in both directions .
The representation of columns is intuitive , Altogether Ⅳ Column , Every time — The subscript range of the column is from О To N -1, Use the subscript of the column to clearly indicate each — Column .
How to represent slashes in two directions ? For slashes in each direction , You need to find the relationship between row and column subscripts at each position on the slash .

The slash in direction 1 is from top left to bottom right , Same as — Each position on the slash satisfies that the difference between row subscript and column subscript is equal , for example （0,0) and (3,3) On a slash in the same direction . Therefore, using the difference between row subscript and column subscript can clearly indicate each — A slash in direction one .

The slash in direction 2 is from top right to bottom left , Each position on the same slash satisfies that the sum of row subscripts and column subscripts is equal , for example (3,0)(3,0) and (1,2)(1,2) On the slash of two in the same direction . Therefore, using the sum of row subscripts and column subscripts can clearly represent the slash in each direction .

Every time the queen is placed , For each location, determine whether it is in three sets , If none of the three sets contains the current location , Then the current position is the position where the queen can be placed .
Complexity analysis

• Time complexity :O(N!), among N It's the number of queens .
• Spatial complexity :O(N), among N It's the number of queens . The space complexity mainly depends on the number of recursive call layers 、 Record the array of column subscripts of the queen placed in each row and three sets , The number of recursive call layers will not exceed N, The length of the array is N, The number of elements in each set will not exceed N.

5 My answer

class Solution {
    
    public List<List<String>> solveNQueens(int n) {
    
        List<List<String>> solutions = new ArrayList<List<String>>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
    
        if (row == n) {
    
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
    
            for (int i = 0; i < n; i++) {
    
                if (columns.contains(i)) {
    
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
    
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
    
                    continue;
                }
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }

    public List<String> generateBoard(int[] queens, int n) {
    
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
    
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}