回溯----8.N皇后

题目链接

/**

            将n个棋子放在n*n的棋盘上,不同列,不同行,不同斜线

            大致执行流程:

                    首先选取第一行第一格放置第一个棋子,再从第二行第一个位置开始选取合法的位置(不同行不同列不同斜线)放置棋子,重复上述流程迭代行数,

                    直到放置n个棋子。

                    若放置途中出现无合法位置的情况,回溯将上一行棋子放置在其他合法位置,再重复上述流程继续放置直到n个棋子。

                    成功放置n个棋子后得到第一种情况,开始回溯重复上述流程,直到回溯至第一行的每个格子都尝试过,得到所有结果

            额外方法:

                    boolean isValid 检查欲放置位置的合法性

                    List<String> BoardToList 棋盘格式转换

 */

class Solution {
    //棋盘
    private char[][] board;
    //保存结果
    private List<List<String>> res = new ArrayList<>();
    //避免重复传参
    private int n;

    public List<List<String>> solveNQueens(int n) {
        /**
            将n个棋子放在n*n的棋盘上,不同列,不同行,不同斜线
            大致执行流程:
                    首先选取第一行第一格放置第一个棋子,再从第二行第一个位置开始选取合法的位置(不同行不同列不同斜线)放置棋子,重复上述流程迭代行数,
                    直到放置n个棋子。
                    若放置途中出现无合法位置的情况,回溯将上一行棋子放置在其他合法位置,再重复上述流程继续放置直到n个棋子。
                    成功放置n个棋子后得到第一种情况,开始回溯重复上述流程,直到回溯至第一行的每个格子都尝试过,得到所有结果
            额外方法:
                    boolean isValid 检查欲放置位置的合法性
                    List<String> BoardToList 棋盘格式转换
        */

        this.n = n;
        this.board = new char[n][n];

        //初始化棋盘
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }

        //开始放置
       backtrack(0);

       return res;


    }

    private void backtrack(int row) {
        //已放置n个棋子,保存结果
        if(row == n) {
            res.add(BoardToList());
            return;
        }

        for(int col = 0; col < n; col++) {
            //当前位置合法
            if(isValid(row,col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);

                //回溯
                board[row][col] = '.';
            }
        }
        
    }

    //判断合法性 判断不同列不同斜线即可,同行已由index控制
    private boolean isValid(int row, int col) {
        //检查列冲突 row可体现出已放置棋子数 i < row 避免不必要的检查
        for(int i = 0; i < row; i++) {
            if(board[i][col] == 'Q') {
                return false;
            }
        }

        //左下对角(上方无棋子,无需检查左上)
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        //右下对角(上方无棋子,无需检查右上)
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;

    }

    // 将棋盘转换为结果格式（List<String>）
    private List<String> BoardToList() {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new String(board[i])); //按行批量转化
        }
        return list;
    }
    
}