LeetCode_ 51_ Queen n

Topic link

• https://leetcode.cn/problems/n-queens/

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 .

Example 1：

 Input ：n = 4
 Output ：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 explain ： As shown in the figure above ,4  There are two different solutions to the queen problem .

Example 2：

 Input ：n = 1
 Output ：[["Q"]]

Tips ：

• 1 <= n <= 9

Their thinking

backtracking

There are three main restrictions on placing queens

• I can't go with you
• Not in the same column
• Cannot be the same slash

Let's say 3 * 3 Chessboard of , Explain the use of backtracking

The retrospective trilogy

• Recursive function parameters
  • n： Chessboard size
  • row: Record the current level of traversal to the chessboard
  • path： Save qualified results
  • ans： Save a collection of results
• Recursive termination condition
  • Find the leaf node
• Single layer logic
  • The depth of recursion is row Control the line of the chessboard , Every floor for Cyclic col Control the columns of the chessboard , Line by line , Determined the position to prevent the queen
  • Search every time from the beginning of a new line , So it's all from 0 Start

Verify whether the chessboard is legal

• I can't go with you
• Not in the same column
• It can't be diagonal , Include 45 Degree and 135 Degree angle

AC Code

class Solution {
    
    public List<List<String>> solveNQueens(int n) {
    
        List<List<String>> ans = new ArrayList<>();
        char[][] chess = new char[n][n];
        for (char[] c : chess) {
    
            Arrays.fill(c, '.');
        }
        backTracing(n, 0, chess, ans);
        return ans;
    }

    private void backTracing(int n, int row, char[][] chess, List<List<String>> ans) {
    
        if (row == n) {
    
            ans.add(Array2List(chess));
            return;
        }
        for (int col = 0; col < n; col++) {
    
            if (isValid(row, col, n, chess)) {
    
                chess[row][col] = 'Q';
                backTracing(n, row + 1, chess, ans);
                chess[row][col] = '.';
            }
        }
    }

    private List<String> Array2List(char[][] chess) {
    
        List<String> list = new ArrayList<>();
        for (char[] c : chess) {
    
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    private boolean isValid(int row, int col, int n, char[][] chess) {
    
        // Check column 
        for (int i = 0; i < row; i++) {
    
            if (chess[i][col] == 'Q') {
    
                return false;
            }
        }
        // Check 45 Degree diagonal 
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
    
            if (chess[i][j] == 'Q') {
    
                return false;
            }
        }
        // Check 135 Degree diagonal 
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
    
            if (chess[i][j] == 'Q') {
    
                return false;
            }
        }
        return true;
    }
}