教你怎么用Java回溯算法解数独
作者:趋向_quxiang 发布时间:2021-12-14 02:27:18
标签:Java,回溯,算法,数独
一、题干
输入一个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
0
投稿
猜你喜欢
- 在C#的数字运算过程中,有时候针对十进制decimal类型的计算需要保留2位有效小数,针对decimal变量保留2位有效小数有多种方法,可以
- LinkedBlockingDeque介绍LinkedBlockingDeque是双向链表实现的双向并发阻塞队列。该阻塞队列同时支持FIFO
- 本文实例为大家分享了Android Studio实现简单计算器功能的具体代码,供大家参考,具体内容如下程序步骤:(1)在布局文件定义一些计算
- 概述本文介绍 Spring Boot 项目中整合 ElasticSearch 并实现 CRUD 操作,包括分页、滚动等功能。添加Maven依
- 近日,Eclipse经常挂掉,都是由于JVM崩溃的原因。每次都有以下错误日志:## A fatal error has been detec
- public class LogHelper { &nbs
- 扩展Hibernate注解@CreationTimestamp,@UpdateTimestamp支持Java8新的时间类型Hibernate
- 1、xml代码:<?xml version="1.0" encoding="utf-8"?&g
- Java基础编写猜数游戏,供大家参考,具体内容如下设计内容及要求产生一个100以内的随机数,游戏者进行猜数,猜中即胜,猜不中,提示是大了还是
- 递归出现栈溢出stackoverflow递归是个不断回调方法的过程,使方法一遍遍的压入栈中,递归次数多了,栈满了也就溢出了。默认的栈大小是1
- Java栈之链式栈存储结构实现一、链栈采用单链表来保存栈中所有元素,这种链式结构的栈称为链栈。二、栈的链式存储结构实现package com
- 前言人类建造迷宫已有5000年的历史。在世界的不同文化发展时期,这些奇特的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走,寻找真相
- 前言似乎委托对于C#而言是一种高级属性,但是我依旧希望你就算第一次看我的文章,也能有很大的收获。所以本博客的语言描述尽量简单易懂,知识点也是
- 一、 Sharding-jdbc简介“Sharding-jdbc是开源的数据库操作中间件;定位为轻量级Java框架,在Java的JDBC层提
- 一、JAVA常用APIjava.lang.Math提供sin, cos, tan, exp, log, log10 等类方法,PI和E等类字
- Java 7的这个新特性改变了警告的对象。构建这些类型毕竟有破坏类型安全的风险,这总得有人知道。但 API 的用户对此是无能为力的,不管do
- 前言最近遇到了这样一个工作场景,需要写一批dubbo接口,再将dubbo接口注册到网关中,但是当dubbo接口异常的时候会给前端返回非常不友
- Java 多文件加密压缩 添加文件加密压缩工具包依赖<!-- zip4j压缩工具 --> <dependenc
- 前言无论Spring的XML配置或者Java配置,都可以配置自动扫描,也就是在指定包及其子包下的component,都会被自动扫描并被Spr
- 1、@Select注解基本用法@Select注解的目的是为了取代xml中的select标签,只作用于方法上面。下面看一下@Select注解的