LeetCode 51.N皇后

1、题目

image.png

2、分析

这道题目的主要困难，是在于怎么记住上一层选择的状态，这里定义一个char[][] 数组作为棋盘。
这道题要注意下char怎么转成题目要求的List数组回去。

其他的直接套用回溯算法的框架即可：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

3、 代码

class Solution {
    List<List<String>> res = new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n]; //注意
        for(char[] c : board){
            Arrays.fill(c, '.');
        }
        backTack(0, board);
        return res;
    }
    private void backTack(int row, char[][] board){
        int n = board.length;
        //结束条件
        if(row == n){
            res.add(charToList(board)); //注意
            return;
        }
        for(int i = 0; i < n; i++){
            if(!isValid(row, i, board)){
                continue;
            }
            //做出选择
            board[row][i] = 'Q';
            //递归下一层
            backTack(row + 1, board);
            //撤销选择
            board[row][i] = '.';
        }
    }

    private boolean isValid(int row, int col, char[][] board){
        int n = board.length;
        //判断这一列上方是否有Q
        for(int i = 0; i < row; i++){
            if(board[i][col] == 'Q')
               return false;
        }
        //判断左上方是否有Q
        int i = row, j = col;
        while(true){
            if(--i < 0 || --j < 0) break;
            if(board[i][j] == 'Q')
               return false;
        }
        //判断右上方是否有Q
        i = row; j = col;
        while(true){
            if(--i < 0 || ++j == n) break;
            if(board[i][j] == 'Q')
               return false;
        }
        return true;
    }

    public List<String> charToList(char[][] board){
        List<String> list = new ArrayList<>();
        for(char[] c : board){
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}