算法系列--递归,回溯,剪枝的综合应用(3)（上）
https://developer.aliyun.com/article/1480885?spm=a2c6h.13148508.setting.14.5f4e4f0euaAisj
💕"对相爱的人来说，对方的心意，才是最好的房子。"💕
作者：Lvzi
文章主要内容：算法系列–递归,回溯,剪枝的综合应用(3)
大家好,今天为大家带来的是
算法系列--递归,回溯,剪枝的综合应用(3),带来几个比较经典的问题N皇后和解数独,这两道都是hard级别的题目,但是不要被吓到!请看我的分析
2.有效的数独
注:本题只是一个引子,是为了给解数独这道题目做引入
链接:
https://leetcode.cn/problems/valid-sudoku/description/
分析:
本题需要判断已经填入数字的数独是否有效,判断条件和N皇后那道题目的剪枝策略很像,具体的判断条件如下:
- 当前数字所在位置的相同
行不能有相同的数字 - 当前数字所在位置的相同
列不能有相同的数字 - 当前数字所在位置所处的
九宫格不能有相同的数字
行和列只需要使用两个二维的布尔类型的数组进行标记即可,但是九宫格这个判断条件如何标记呢?这里用到了一个比较巧妙的策略,将连续的三个位置看成一个数字,
代码:
class Solution { boolean[][] row, col; boolean[][][] grid; public boolean isValidSudoku(char[][] board) { row = new boolean[9][10]; col = new boolean[9][10]; grid = new boolean[3][3][10]; for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { if(board[i][j] != '.') { int num = board[i][j] - '0'; if(col[j][num] == true || row[i][num] == true || grid[i / 3][j / 3][num] == true) return false; col[j][num] = row[i][num] = grid[i / 3][j / 3][num] = true; } } } return true; } }
3.解数独
链接:
https://leetcode.cn/problems/sudoku-solver/description/
分析:
很容易分析出本题是一个递归问题,因为每一步做的事情都是相同的
- 存入数字,判断是否符合条件
递归的策略也容易想出–以一个一个的空格进行枚举
1.设计代码
全局变量
row[][],col[][]分别用于标记行和列grid[][][]:用于标记九宫格
dfs:
- 函数头:只需要传递原始的棋盘即可,返回值设置为boolean
- 函数体:关注每一个子问题具体干的事情,在当前空位置从数字1枚举到数字9,判断是否符合添加的条件,如果可以,就填入,并递归下一个空位置
- 递归出口:全部填充完毕
2.剪枝
注意有可能上一步的策略会导致当前位置无法填入任何数字,也就是上一步的策略是否有效需要递归到后面的子问题才能知道,一旦某个子问题中发现无法填入任何数字,证明上一步的策略是失败的,没有必要继续递归下去,此时就发生了剪枝,对于每一次递归来说,都需要返回一个布尔类型的数据,用于记录策略成功与否
3.回溯
回溯的策略和N皇后很像,恢复原状即可
代码:
class Solution { boolean[][] row, col; boolean[][][] grid; public void solveSudoku(char[][] board) { row = new boolean[9][10]; col = new boolean[9][10]; grid = new boolean[3][3][10]; // 初始化 for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { if(board[i][j] != '.') { int num = board[i][j] - '0'; row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; } } } // 递归 dfs(board); } private boolean dfs(char[][] board) { // 这里采用的递归的策略是一个一个空位置进行递归的 for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { if(board[i][j] == '.') { for(int num = 1; num <= 9; num++) { if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) {// 剪枝 board[i][j] = (char)('0' + num); row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; // 递归下一个位置 if(dfs(board) == true) return true;// 当前位置的策略是成功的 board[i][j] = '.';// 回溯 row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false; } } return false;// 走到这里证明当前位置一个数字也填不了,需要更换上一步的策略 } } } return true;// 所有的空位都被填充 } }
一定要重点理解代码中三个return的实际含义
(本题真的很有意思,你可以利用上述代码快速的完成一道大师级的数独题目哦~笔者已经试过一次,真的很爽!!!)
