回溯----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;}}