⚡刷题计划day26 回溯（五）继续，回溯最后一个专题，今天的是hard题，也是比较经典的题型，可以点个免费的赞哦~
目录
题目一：N 皇后
51. N 皇后
(https://leetcode.cn/problems/n-queens/description/)
n皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列问题之后，遇到这种二维矩阵还会有点不知所措。
首先来看一下皇后们的约束条件：
不能同行
不能同列
不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
下面我用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：
从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。
法一：简明版
回溯三部曲
1.递归函数参数
我依然是定义全局变量二维数组result来记录最终结果。
参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。
代码如下：
List<List<String>> res = new ArrayList<>();
void backatracking(int n,int row,char[][] chessboard)2.递归终止条件
当递归到叶子节点，就可以收集结果返回了。
if(n==row){
res.add(Array2List(chessboard));
return;
}3.单层搜索逻辑
递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
每次都是要从新的一行的起始位置开始搜，所以都是从0开始。
代码如下：
for(int i=0;i<n;i++){
if(isValid(n,row,i,chessboard)){
chessboard[row][i] = 'Q';
backatracking(n,row+1,chessboard);
chessboard[row][i] = '.';
}
}4.验证棋盘是否合法
按照如下标准去重：
不能同行
不能同列
不能同斜线 （45度和135度角）
代码如下：
public boolean isValid(int n,int row,int col,char[][] chessboard){
// 检查列
for(int i=row-1;i>=0;i--){
if(chessboard[i][col]=='Q'){
return false;
}
}
// 检查45度对角线
for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
if(chessboard[i][j]=='Q'){
return false;
}
}
// 检查135度对角线
for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){
if(chessboard[i][j]=='Q'){
return false;
}
}
return true;
}在这份代码中，细心的同学可以发现为什么没有在同行进行检查呢？
因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了
完整代码：
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for (char[] c : chessboard){
Arrays.fill(c,'.');
}
backatracking(n,0,chessboard);
return res;
}
public void backatracking(int n,int row,char[][] chessboard){
if(n==row){
res.add(Array2List(chessboard));
return;
}
for(int i=0;i<n;i++){
if(isValid(n,row,i,chessboard)){
chessboard[row][i] = 'Q';
backatracking(n,row+1,chessboard);
chessboard[row][i] = '.';
}
}
}
public boolean isValid(int n,int row,int col,char[][] chessboard){
// 检查列
for(int i=row-1;i>=0;i--){
if(chessboard[i][col]=='Q'){
return false;
}
}
// 检查45度对角线
for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
if(chessboard[i][j]=='Q'){
return false;
}
}
// 检查135度对角线
for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){
if(chessboard[i][j]=='Q'){
return false;
}
}
return true;
}
public List<String> Array2List(char[][] chessboard){
List<String> list = new ArrayList<>();
for(char[] c : chessboard){
list.add(new String(c));
}
return list;
}
}我们可以发现关于验证棋盘是否合法时，我们用了三个for循环,3n的复杂度，好像不是很好，那我们能不能使用O(1)的复杂度来解决呢，答案是可以的，见法二
法二：优化版
主要优化部分就是验证棋盘是否合法：
对于棋盘，有以下的性质：
1.对于对于 ↗ 方向的格子，行号加列号是不变的。
2.对于 ↖ 方向的格子，行号减列号是不变的。
可以结合下列棋盘理解一下：
所以我们就可以使用三个辅助数组来标记之前皇后所在的行号列号，如下：
boolean[] isColChoose = new boolean[n];//代表第c列是否被选
boolean[] r_diag = new boolean[2*n-1];//代表右对角线是否有元素，r+c
boolean[] l_diag = new boolean[2*n-1];//代表左对角线是否有元素,r-c。注意r-c对应的数组下标可能为负数，所以我们后面判断需要将r-c加上n-1，使其从0开始。
完整代码如下：
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
boolean[] isColChoose = new boolean[n];//代表第c列是否被选
boolean[] r_diag = new boolean[2*n-1];//代表右对角线是否有元素，r+c
boolean[] l_diag = new boolean[2*n-1];//代表左对角线是否有元素,,r-c
for(char[] c : chessboard){
Arrays.fill(c,'.');
}
bcaktracking(n,0,chessboard,isColChoose,r_diag,l_diag);
return res;
}
public void bcaktracking(int n,int row,char[][] chessboard,boolean[] isColChoose,boolean[] r_diag,boolean[] l_diag){
if(row==n){
res.add(charToListString(chessboard));
return;
}
for(int col=0;col<n;col++){
if(!isColChoose[col] && !r_diag[row+col] && !l_diag[row-col+n-1]){
chessboard[row][col]='Q';
isColChoose[col]=true;
r_diag[row+col]=true;
l_diag[row-col+n-1]=true;
bcaktracking(n,row+1,chessboard,isColChoose,r_diag,l_diag);
//回溯
chessboard[row][col]='.';
isColChoose[col]=false;
r_diag[row+col]=false;
l_diag[row-col+n-1]=false;
}
}
}
public List<String> charToListString(char[][] chessboard){
List<String> path = new ArrayList<>();
for (char[] c : chessboard){
path.add(String.copyValueOf(c));
}
return path;
}题目二：解数独
37. 解数独
(https://leetcode.cn/problems/sudoku-solver/description/)
本题建议先做一下n皇后问题，
本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了，我抽取一部分，如图所示：
法一：简明版
回溯三部曲
1.递归函数以及参数
递归函数的返回值需要是bool类型，为什么呢？
因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。
boolean backtracking(char[][] board)2.递归终止条件
本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
不用终止条件会不会死循环？
递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！
那么有没有永远填不满的情况呢？
这个问题我在递归单层搜索逻辑里再来讲！
3.递归单层搜索逻辑
在树形图中可以看出我们需要的是一个二维的递归 （一行一列）
一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！
代码如下，详见注释：
public boolean backtracking(char[][] board){
for(int i=0;i<board.length;i++){// 遍历行
for(int j=0;j<board[0].length;j++){// 遍历列
if(board[i][j]!='.'){
continue;
}
for(char k='1';k<='9';k++){
if(isValid(i,j,k,board)){
board[i][j]=k;// 放置k
if(backtracking(board)){
return true; // 如果找到合适一组立刻返回
}
board[i][j]='.';
}
}
return false; // 9个数都试完了，都不行，那么就返回false
}
}
return true;// 遍历完没有返回false，说明找到了合适棋盘位置了
}4.判断棋盘是否合法
判断棋盘是否合法有如下三个维度：
同行是否重复
同列是否重复
9宫格里是否重复
代码如下：
public boolean isValid(int row,int col,char val,char[][] board){
//行
for(int i=0;i<9;i++){
if(board[row][i]==val){
return false;
}
}
//列
for(int j=0;j<9;j++){
if(board[j][col]==val){
return false;
}
}
//九宫格
int startRow = row/3*3;
int startCol = col/3*3;
for(int i=startRow;i<startRow+3;i++){
for(int j=startCol;j<startCol+3;j++){
if(board[i][j]==val){
return false;
}
}
}
return true;
}整体代码如下：
class Solution {
public void solveSudoku(char[][] board) {
backtracking(board);
}
public boolean backtracking(char[][] board){
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(board[i][j]!='.'){
continue;
}
for(char k='1';k<='9';k++){
if(isValid(i,j,k,board)){
board[i][j]=k;
if(backtracking(board)){
return true;
}
board[i][j]='.';
}
}
return false;
}
}
return true;
}
public boolean isValid(int row,int col,char val,char[][] board){
//行
for(int i=0;i<9;i++){
if(board[row][i]==val){
return false;
}
}
//列
for(int j=0;j<9;j++){
if(board[j][col]==val){
return false;
}
}
//九宫格
int startRow = row/3*3;
int startCol = col/3*3;
for(int i=startRow;i<startRow+3;i++){
for(int j=startCol;j<startCol+3;j++){
if(board[i][j]==val){
return false;
}
}
}
return true;
}
}法二：简明略优化版
上面做了n皇后问题，很显然我们也可以使用之前法二的辅助数组来优化，直接详细见代码注释。
额外说一下关于九宫格的判断，可能很多同学开始很难理解为什么int k = row/3*3 + col/3;这样就可以判断是哪一个九宫格，网上也没有看到有题解有对其进行了较直观详细的解释，
可以理解理解这段话再加上图就很清晰了：
i / 3 得到行索引，然后乘以3是因为每个小格子有3列，这样可以得到当前行索引对应的小格子的起始列索引。然后，加上 j / 3 就可以得到当前元素在九宫格中的确切位置。比如以第一列的4，带进去算一下就明白了。
class Solution {
public void solveSudoku(char[][] board) {
boolean[][] isRow = new boolean[9][9];
boolean[][] isCol = new boolean[9][9];
boolean[][] isSquare9 = new boolean[9][9];
//初始化
for(int row=0;row<9;row++){
for(int col=0;col<9;col++) {
if(board[row][col]=='.'){
continue;
}
int num = board[row][col]-'1';//数字从0开始，如果减0就是原数，但是构造二维数组就是new boolean[9][10];
int k = row/3*3 + col/3;
isRow[row][num]=true;
isCol[col][num]=true;
isSquare9[k][num]=true;
//i / 3 得到行索引，然后乘以3是因为每个小格子有3列，这样可以得到当前行索引对应的小格子的起始列索引。然后，加上 j / 3 就可以得到当前元素在九宫格中的确切位置。
}
}
backtracking(board,0,isRow,isCol,isSquare9);
}
public boolean backtracking(char[][] board,int n,boolean[][] isRow,boolean[][] isCol,boolean[][] isSquare9){
if(n==81) return true;
int i=n/9,j=n%9;
if(board[i][j] != '.'){
return backtracking(board,n+1,isRow,isCol,isSquare9);
}
int k = i/3*3+j/3;
for(int num=0;num<9;num++){
if(isRow[i][num] || isCol[j][num] || isSquare9[k][num]) continue;
board[i][j] = (char) (num+'1');
isRow[i][num]=isCol[j][num]=isSquare9[k][num]=true;
if(backtracking(board,n+1,isRow,isCol,isSquare9)) return true;
isRow[i][num]=isCol[j][num]=isSquare9[k][num]=false;
}
board[i][j] = '.';
return false;
}
}法三：极致优化版
这个方法比较难理解，时间充裕的同学可以尝试尝试，来自leetcode题解，代码及注释如下：
class Solution {
// 二进制中1表示 对应位置已经有值了
private int[] rows = new int[9];
private int[] cols = new int[9];
private int[][] cells = new int[3][3];
public void solveSudoku(char[][] board) {
int cnt = 0;
for(int i=0; i<board.length; i++){
for(int j=0; j<board[i].length; j++){
char c = board[i][j];
if(c == '.'){
cnt++;
}else{
int n = c - '1';
// rows[i] |= (1 << n);
// cols[j] |= (1 << n);
// cells[i/3][j/3] |= (1 << n);
fillNumber(i, j, n, true);
}
}
}
backtrace(board, cnt);
}
private boolean backtrace(char[][] board, int cnt){
if(cnt == 0){
return true;
}
// 获取当前 候选项最少（即限制最多）的格子下标
int[] pos = getMinOkMaskCountPos(board);
int x = pos[0], y = pos[1];
// okMask 值为1的 位 表示 对应的数字 当前可以填入
int okMask = getOkMask(x, y);
for(char c='1'; c<='9'; c++){
int index = c - '1';
if(testMask(okMask, index)){
fillNumber(x, y, index, true);
board[x][y] = c;
if(backtrace(board, cnt-1)) return true; // 题目假定唯一解
board[x][y] = '.';
fillNumber(x, y, index, false);
}
}
return false;
}
// n 0..8
private void fillNumber(int x, int y, int n, boolean fill){
// 因为回溯先选择后撤销，所以fill先true后false, false时对应位置一定是1，所以异或可行
// rows[x] = fill ? rows[x] | (1<<n) : rows[x] ^ (1<<n);
// cols[y] = fill ? cols[y] | (1<<n) : cols[y] ^ (1<<n);
// cells[x/3][y/3] = fill ? cells[x/3][y/3] | (1<<n) : cells[x/3][y/3] ^ (1<<n);
// ture set 1, false set 0
rows[x] = fill ? rows[x] | (1<<n) : rows[x] & ~(1<<n);
cols[y] = fill ? cols[y] | (1<<n) : cols[y] & ~(1<<n);
cells[x/3][y/3] = fill ? cells[x/3][y/3] | (1<<n) : cells[x/3][y/3] & ~(1<<n);
}
private int getOkMask(int x, int y){
return ~(rows[x] | cols[y] | cells[x/3][y/3]);
}
// mask 二进制 低9位 中 1的个数
private int getOneCountInMask(int mask){
int res = 0;
for(int i=0; i<9; i++){
int test = 1 << i;
if((mask & test) != 0){
res++;
}
}
return res;
}
// mask 二进制 低index位 是否为 1
private boolean testMask(int mask, int index){
return (mask & (1 << index)) != 0;
}
// 获取候选项最少的位置
private int[] getMinOkMaskCountPos(char[][] board){
int[] res = new int[2];
int min = 10;
for(int i=0; i<board.length; i++){
for(int j=0; j<board[i].length; j++){
if(board[i][j] == '.'){
int okMask = getOkMask(i, j);
int count = getOneCountInMask(okMask);
if(count < min){
min = count;
res[0] = i;
res[1] = j;
}
}
}
}
return res;
}
}