教你怎么用Java回溯算法解数独
作者:趋向_quxiang 时间:2021-12-14 02:27:18
一、题干
输入一个9*9二维数组表示数独,已经填入的数字用1-9表示,待填入的数字用0表示,试写一个算法解出数独并输出。
二、思路
容易想到回溯法,即以人的思维的解数独,遍历数组,如果是空白就从1-9依次选一个数判断本行、列、3*3宫格内是否有重复,如果有就进行下一个数字的选择;如果该数暂时满足条件,那么进行下一个格子的选择,递归的终止条件是遍历完所有格子。
三、代码分段演示
输入数组
Scanner sc = new Scanner(System.in);
int[][] board = new int[9][9];
// 输入
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
board[i][j] = sc.nextInt();
}
}
dfs回溯
(r, c)
是当前正在判断的格子坐标,board[r][c] == 0
判断这个格子是否还没有填数,如果没有,就从1-9依次选取一个数,先判断选的这个数是否合法,如果合法就做选择,并开始下一个格子的判断,决定完下一个格子之后就撤销选择(这是回溯法基本框架);如果该格子已填数,直接开始下一个格子的判断。终止条件就是r==9
,也就是二维数组遍历完。
public static void dfs(int[][] board, int r, int c) {
// 所有数填完了,输出
if (r == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
return;
}
// 空白填数
if (board[r][c] == 0) {
// 从 1-9 中依次选数
for (int k = 1; k <= 9; k++) {
// 先判断放进去是否满足条件再选择
if (isValid(board, r, c, k)) {
// 做选择
board[r][c] = k;
// 决定下一个格子
next(board, r, c);
// 撤销选择
board[r][c] = 0;
}
}
}
// 非空白直接决定下一个格子
else next(board, r, c);
}
在二维数组中,下一个格子有两种可能:一是就在本行只需列+1即可,二是当前格子是本行最后一个,那么下一个格子就是下一行第一个。
// 递归下一个格子
public static void next(int[][] board, int r, int c) {
if (c + 1 == 9) dfs(board, r + 1, 0);
else dfs(board, r, c + 1);
}
判断是否满足条件
行和列的判断就不必细说了,关键是3*3宫格的判断,行 / 3 * 3 和 列 / 3 * 3 就是所在的3*3宫格左上角格子的坐标,其中 / 是地板除法
// 判断是否合法
public static boolean isValid(int[][] board, int r, int c, int val) {
// 列
for (int i = 0; i < 9; i++) {
if (board[i][c] == val) return false;
}
// 行
for (int j = 0; j < 9; j++) {
if (board[r][j] == val) return false;
}
// 3 * 3
for (int x = r / 3 * 3, i = x; i < x + 3; i++) {
for (int y = c / 3 * 3, j = y; j < y + 3; j++) {
if (board[i][j] == val) return false;
}
}
return true;
}
四、完整代码
public static void main(String[] args) {
solveSudoku();
}
public static void solveSudoku() {
Scanner sc = new Scanner(System.in);
int[][] board = new int[9][9];
// 输入
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
board[i][j] = sc.nextInt();
}
}
dfs(board, 0, 0);
}
// 回溯填数
public static void dfs(int[][] board, int r, int c) {
// 所有数填完了,输出
if (r == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
return;
}
// 空白填数
if (board[r][c] == 0) {
for (int k = 1; k <= 9; k++) {
if (isValid(board, r, c, k)) {
// 做选择
board[r][c] = k;
// 决定下一个格子
next(board, r, c);
// 撤销选择
board[r][c] = 0;
}
}
}
// 非空白直接决定下一个格子
else next(board, r, c);
}
// 递归下一个格子
public static void next(int[][] board, int r, int c) {
if (c + 1 == 9) dfs(board, r + 1, 0);
else dfs(board, r, c + 1);
}
// 判断是否合法
public static boolean isValid(int[][] board, int r, int c, int val) {
// 列
for (int i = 0; i < 9; i++) {
if (board[i][c] == val) return false;
}
// 行
for (int j = 0; j < 9; j++) {
if (board[r][j] == val) return false;
}
// 3 * 3
for (int x = r / 3 * 3, i = x; i < x + 3; i++) {
for (int y = c / 3 * 3, j = y; j < y + 3; j++) {
if (board[i][j] == val) return false;
}
}
return true;
}
顺便提供几个示例输入输出
输入:
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9
输出:
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
输入:
0 0 0 5 0 0 9 0 0
6 0 4 2 0 3 0 0 0
5 0 0 0 6 0 0 3 2
0 0 0 0 9 0 4 0 0
4 2 0 1 0 5 0 7 9
0 0 9 7 0 0 1 0 0
9 0 0 0 0 6 0 1 8
2 0 0 0 4 0 0 0 5
0 0 0 0 0 0 6 0 0
输出:
7 3 2 5 8 1 9 6 4
6 9 4 2 7 3 5 8 1
5 1 8 4 6 9 7 3 2
1 7 5 6 9 8 4 2 3
4 2 6 1 3 5 8 7 9
3 8 9 7 2 4 1 5 6
9 4 7 3 5 6 2 1 8
2 6 1 8 4 7 3 9 5
8 5 3 9 1 2 6 4 7
输入:
0 0 9 7 4 8 0 0 0
7 0 0 0 0 0 0 0 0
0 2 0 1 0 9 0 0 0
0 0 7 0 0 0 2 4 0
0 6 4 0 1 0 5 9 0
0 9 8 0 0 0 3 0 0
0 0 0 8 0 3 0 2 0
0 0 0 0 0 0 0 0 6
0 0 0 2 7 5 9 0 0
输出:
5 1 9 7 4 8 6 3 2
7 8 3 6 5 2 4 1 9
4 2 6 1 3 9 8 7 5
3 5 7 9 8 6 2 4 1
2 6 4 3 1 7 5 9 8
1 9 8 5 2 4 3 6 7
9 7 5 8 6 3 1 2 4
8 3 2 4 9 1 7 5 6
6 4 1 2 7 5 9 8 3
来源:https://blog.csdn.net/qq_45822970/article/details/117414590
标签:Java,回溯,算法,数独
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Spring Boot集成Spring Cache过程详解
2023-08-02 19:20:16
![](https://img.aspxhome.com/file/2023/3/84583_0s.png)
C#中判断、验证字符串是否为日期格式的实现代码
2021-06-05 01:57:26
Unity实现场景加载功能
2021-09-15 12:27:45
![](https://img.aspxhome.com/file/2023/5/94565_0s.jpg)
基于Java Springboot + Vue + MyBatis实现音乐播放系统
2023-07-09 16:01:41
![](https://img.aspxhome.com/file/2023/1/106131_0s.png)
springcloud eureka切换nacos的配置方法
2022-05-19 01:58:47
Springmvc模式上传和下载与enctype对比
2022-11-08 09:14:17
Android itemDecoration接口实现吸顶悬浮标题
2023-03-14 00:58:31
![](https://img.aspxhome.com/file/2023/8/100618_0s.gif)
Java方法的返回值及注意事项小结
2022-10-02 16:55:28
java实现大文件分割与合并的实例代码
2023-11-11 04:31:21
spring-boot-maven-plugin:打包时排除provided依赖问题
2023-07-18 02:12:11
![](https://img.aspxhome.com/file/2023/5/72545_0s.png)
详解OAuth2 Token 一定要放在请求头中吗
2022-05-01 09:43:15
![](https://img.aspxhome.com/file/2023/3/76543_0s.jpg)
JAVA swing布局管理器实例解析
2022-01-11 05:05:15
![](https://img.aspxhome.com/file/2023/6/94216_0s.png)
一文带你了解C#中抽象方法与虚方法的区别
2023-07-23 00:14:32
浅谈Java 继承接口同名函数问题
2023-07-22 13:28:47
![](https://img.aspxhome.com/file/2023/0/57720_0s.jpg)
SpringBoot重写addResourceHandlers映射文件路径方式
2022-05-26 19:02:40
![](https://img.aspxhome.com/file/2023/3/66183_0s.jpg)
Struts2相关的面试题整理分享
2022-04-06 08:02:20
Android仿微信联系人字母排序效果
2021-10-01 16:06:25
![](https://img.aspxhome.com/file/2023/1/90121_0s.gif)
java swing 创建一个简单的QQ界面教程
2022-09-08 06:51:39
![](https://img.aspxhome.com/file/2023/4/67154_0s.jpg)
C#多线程之Thread类详解
2023-07-23 05:34:46
![](https://img.aspxhome.com/file/2023/1/100181_0s.png)
Spring Boot项目如何同时支持HTTP和HTTPS协议的实现
2023-11-19 19:57:05
![](https://img.aspxhome.com/file/2023/1/59321_0s.jpg)