【回溯数独】有效的数独（medium）& 解数独（hard）
🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
⭐数独⭐
🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
前言
回溯算法是⼀种经典的递归算法，通常⽤于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想：从⼀个初始状态开始，按照⼀定的规则向前搜索，当搜索到某个状态⽆法前进 时，回退到前⼀个状态，再按照其他的规则搜索。
回溯算法在搜索过程中维护⼀个状态树，通过遍历 状态树来实现对所有可能解的搜索。 回溯算法的核⼼思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜 索；否则，回退到上⼀个状态，重新做出选择。
回溯算法通常⽤于解决具有多个解，且每个解都需要 搜索才能找到的问题。
回溯算法的模板
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Backtracking {
public void backtracking(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
// 如果需要对candidates进行排序
backtrack(result, new ArrayList<>(), candidates, target, 0);
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
if (remain < 0) {
// 如果 remain 小于 0，表示当前的组合不符合要求，直接返回
return;
} else if (remain == 0) {
// 如果 remain 等于 0，表示当前的组合符合要求，加入到结果中
result.add(new ArrayList<>(tempList));
} else {
for (int i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
// 避免重复计算，如果当前数字和上一个数字相同，则跳过
}
tempList.add(candidates[i]); // 将当前数字加入到临时列表中
backtrack(result, tempList, candidates, remain - candidates[i], i + 1);
// 递归调用，继续向下搜索
tempList.remove(tempList.size() - 1);
// 回溯，将最后加入的数字移除，尝试下一个数字
}
}
}
}
回溯算法是⼀种⾮常重要的算法，可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核⼼ 思想是搜索状态树，通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板⾮常简单，但是实 现起来需要注意⼀些细节，⽐如如何做出选择、如何撤销选择等。
1: 数独验证 (LeetCode 36. 有效的数独)
算法思路
算法原理描述
我们需要检查一个9x9的数独板是否有效。有效的数独需要满足以下条件：
- 每一行、每一列以及每一个3x3的小方格中都包含数字1-9且不重复。
- 可以使用三个布尔数组来分别记录行、列以及小方格中的数字出现情况。
类定义及变量初始化
定义一个名为
Solution的类来封装解决方案逻辑。
boolean[][] row: 用于存储每行每个数字是否已经出现过。boolean[][] col: 用于存储每列每个数字是否已经出现过。boolean[][][] grid: 用于存储每个3x3小方格内每个数字是否已经出现过。主方法实现
主方法
isValidSudoku:
- 初始化
row,col和grid。- 遍历整个棋盘，对于非空格的单元格，标记对应的数字在行、列和小方格中已出现。
- 如果发现任何冲突，则返回
false。- 如果遍历完整个棋盘没有发现冲突，则返回
true。
代码实现
class Solution {
public boolean isValidSudoku(char[][] board) {
// 对每一行一列每个小方格记录并判断
boolean[][] row = new boolean[9][10];
boolean[][] col = new boolean[9][10];
boolean[][][] grid = new boolean[3][3][10];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char ch = board[i][j];
if (ch != '.') {
int num = ch - '0';
if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num]) {
return false;
}
row[i][num] = true;
col[j][num] = true;
grid[i / 3][j / 3][num] = true;
}
}
}
return true;
}
}2: 数独求解 (LeetCode 37. 解数独)
题⽬链接：
37. 解数独 - 力扣（LeetCode）
算法思路
算法原理描述
我们使用深度优先搜索（DFS）和回溯法来尝试填充数独板。通过递归地尝试每个空格可能的数字，并在发现冲突时进行回溯，直到找到一个完整的解或遍历完所有可能性。
类定义及变量初始化
定义一个名为
Solution的类来封装解决方案逻辑。
boolean[][] row: 用于存储每行每个数字是否已经出现过。boolean[][] col: 用于存储每列每个数字是否已经出现过。boolean[][][] grid: 用于存储每个3x3小方格内每个数字是否已经出现过。主方法实现
主方法
solveSudoku:
- 初始化
row,col和grid。- 标记已有的数字。
- 调用递归方法
dfs开始求解。
代码实现
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] = true;
col[j][num] = true;
grid[i / 3][j / 3][num] = true;
}
}
}
// 开始深度优先搜索
dfs(board);
}
public 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++) { // 尝试填入1-9的数字
if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) { // 剪枝
// 放置数字
board[i][j] = (char) ('0' + num);
row[i][num] = true;
col[j][num] = true;
grid[i / 3][j / 3][num] = true;
if (dfs(board)) { // 递归调用
return true; // 如果找到了解，直接返回true
}
// 回溯
board[i][j] = '.';
row[i][num] = false;
col[j][num] = false;
grid[i / 3][j / 3][num] = false;
}
}
// 所有数字都尝试过了还没有返回，说明这个路径无效
return false;
}
}
}
// 整个棋盘都被填充，说明找到了一个解
return true;
}
}总结
后续不再更新每日一题了，感觉有的题用不着写博客，后续只更新高质量的题咯，感谢阅览！！
原文地址：https://blog.csdn.net/Y_1215/article/details/142687534
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！