代码随想录 Q82. N皇后

题目要求N皇后问题约束条件是N个皇后之间不能同行、不能同列、也不能同斜线使用回溯法解决。思路可以将搜索皇后的位置抽象为一棵树用皇后的约束条件来回溯搜索这棵树如果搜索到树的叶子节点就说明找到了皇后们的合理位置。以3*3的棋盘为例在二维矩阵中矩阵的高就是这棵树的高度矩阵的宽就是树形结构中每个节点的宽度。回溯三部曲1.递归函数参数1全局变量二维数组res用来记录最终结果boolean数组表示已经占用的直斜线。ListListString res new ArrayList(); boolean[] usedCol,usedDiag45,usedDiag135; //boolean数组中每个元素代表一条直斜线。2参数board[]索引号表示行号(row)、数组值表示该行皇后所在的列号columnn表示棋盘的大小row用来记录当前遍历到第几层了。private void backtracking(int[] board,int n,int row)2.递归终止条件当递归到棋盘最底层也就是叶子节点时可以收集结果并返回。if(row n){ //收集结果 ListString temp new ArrayList(); //增强for循环等价于 //for(int idx 0;idx board.length;idx ) //{ //int i board[idx]; //循环体 //} // i是当前皇后所在的列号 for(int i : board){ char[] str new char[n]; //创建长度为n的字符数组 Arrays.fill(str,.); //全部填充为“.” str[i] Q; //在皇后位置放置“Q” temp.add(new String(str)); //将字符数组转换为字符串表示本行的结果用temp暂时接住 } res.add(temp); //将本行结果存入res数组 return; }3.单层搜索的逻辑递归深度是用row控制棋盘的行每一层里for循环的col控制棋盘的列一行一列确定了放置棋盘的位置。每次都是从新的一行的起始位置开始搜所以都是从0开始。for(int col 0;col n;col ){ //如果当前列45°对角线或135°对角线有任何一条已经被其他皇后占用则跳过这个位置 //usedCol[col]表示当前列 //usedDiag45[row col]表示45°对角线从左上到右下 //usedDiag135[row - col n - 1]表示135°对角线从右上到左下 n - 1是为了将负值转换为正数作为数组索引 // |是按位或运算这里是用作逻辑或因为操作数是boolean类型| 等价于 ||但前者计算所有条件后者短路计算 if(usedCol[col] | usedDiag45[row col] | usedDiag135[row - col n - 1]){ continue; } board[row] col; usedCol[col] true; usedDiag45[row col] true; usedDiag135[row - col n - 1] true; backtracking(board,n,row 1); usedCol[col] false; usedDiag45[row col] false; usedDiag135[row - col n - 1] false; }4.验证棋盘是否合法按照以下标准去重不能同行、不能同列、不能同斜线45°和135°。在验证棋盘是否合法的逻辑中不需要再进行同行检查了这是因为代码逻辑中在每一行row中只会在一个列位置放置皇后放置后立刻递归到下一行row 1而回溯时当前行的皇后会被移除因此同一行永远不会出现两个皇后。if(usedCol[col] | usedDiag45[row col] | usedDiag135[row - col n - 1]){ continue; }board[]数组用于收集结果是一个长度为n棋盘大小的int[]数组数组的索引表示行号row数组的值表示该行皇后所在的列号column。例如board [1,3,0,2]表示第0行皇后在第1列第1行皇后在第3列第2行皇后在第0列第3行皇后在第2列。因为棋盘board是一个固定长度的二维数组不是动态增长的链表每次递归调用时board[row]都会被新的col值覆盖因此不需要path.add和path.removeLast而是直接用简单的直接覆盖方式回溯。核心思想通过递归回溯收集一个符合条件的一维数组board如board[2] 3表示第2行中的皇后在第三列当走到最后一列的时候即row n即可开始收集利用board数组描述的皇后的位置重建Q和.组成的棋盘temp并用res收集这个结果。注意是先找到一个合法的位置然后再进入下一行进行递归探索。附代码class Solution { ListListString res new ArrayList(); boolean[] usedCol,usedDiag45,usedDiag135; //boolean数组中每个元素代表一条直斜线。 public ListListString solveNQueens(int n) { usedCol new boolean[n]; //列方向的直线条数为n。 usedDiag45 new boolean[2 * n - 1]; //45°方向的斜线条数为2 * n - 1。 usedDiag135 new boolean[2 * n - 1]; //135°方向的斜线条数为2 * n - 1。 //用于收集结果数组的索引表示行号row数组的值表示该行皇后所在的列号column。 //例如board [1,3,0,2]表示第0行皇后在第1列第1行皇后在第3列第2行皇后在第0列第3行皇后在第2列。 int[] board new int[n]; backtracking(board,n,0); return res; } private void backtracking(int[] board,int n,int row){ // 通过递归回溯收集一个符合条件的一维数组board // 如board[2] 3表示第2行中的皇后在第三列 // 当走到最后一列的时候即row n即可开始收集 // 利用board数组描述的皇后的位置重建Q和.组成的棋盘temp并用res收集这个结果 if(row n){ //收集结果 ListString temp new ArrayList(); //增强for循环等价于 //for(int idx 0;idx board.length;idx ) //{ //int i board[idx]; //循环体 //} // i是当前皇后所在的列号 for(int i : board){ char[] str new char[n]; //创建长度为n的字符数组 Arrays.fill(str,.); //全部填充为“.” str[i] Q; //在皇后位置放置“Q” temp.add(new String(str)); //将字符数组转换为字符串表示本行的结果用temp暂时接住 } res.add(temp); //将本行结果存入res数组 return; } for(int col 0;col n;col ){ //如果当前列45°对角线或135°对角线有任何一条已经被其他皇后占用则跳过这个位置 //usedCol[col]表示当前列 //usedDiag45[row col]表示45°对角线从左上到右下 //usedDiag135[row - col n - 1]表示135°对角线从右上到左下 n - 1是为了将负值转换为正数作为数组索引 // |是按位或运算这里是用作逻辑或因为操作数是boolean类型| 等价于 ||但前者计算所有条件后者短路计算 if(usedCol[col] | usedDiag45[row col] | usedDiag135[row - col n - 1]){ continue; } // 因为棋盘board是一个固定长度的二维数组不是动态增长的链表 // 每次递归调用时board[row]都会被新的col值覆盖 // 因此不需要path.add和path.removeLast而是直接用简单的直接覆盖方式回溯 // 找到了一个合法的位置 board[row] col; // 进入下一行进行递归探索注意要回溯 usedCol[col] true; usedDiag45[row col] true; usedDiag135[row - col n - 1] true; backtracking(board,n,row 1); usedCol[col] false; usedDiag45[row col] false; usedDiag135[row - col n - 1] false; } } }