文档章节

Java解决“数独”之三

dreamcloudz
 dreamcloudz
发布于 2017/01/11 15:16
字数 959
阅读 15
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

数独是一个我们都非常熟悉的经典游戏,运用计算机我们可以很快地解开数独难题,现在有一些简单的数独题目,请编写一个程序求解。

输入描述:

输入9行,每行为空格隔开的9个数字,为0的地方就是需要填充的。

输出描述:

输出九行,每行九个空格隔开的数字,为解出的答案。

分析:

      这里的数独就是9行9列的数组,满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复

这里粗线宫要分清楚,开始我以为是任意的九宫格内的1-9都不重复,实际这里是自己想复杂了,只需要满足如下图所示的阴影区域划分出的九个宫格1-9不重复就好了,总共就9共宫格,不是自己理解的7*7=49个小宫格,这里要弄清楚。

   解题思路:DFS深度填数检测+回溯法

     1,先把有数字的地方设置标记位为true

     2,循环遍历数组中没有标记位true的地方,也就是需要填数的地方

          1) 如果当前为0,即a[i][j]==0,判断当前所在的九宫格,然后从数字1-9依次检测是否在行、列、宫中唯一。

                (1) 满足唯一的话,则吧数字赋值给a[i][j]=l+1;然后继续深度遍历为true的话就返回true,否则回溯a[i][j]==0等。

                  (2) 不满足满足唯一则判断下一个数字,直到1-9都判断不满足则返回false,会回溯到上一层。

            2) 如果当前没有0,说明都已经填满且符合唯一条件,则返回true;结束。

                          

具体代码如下:

import java.util.Scanner;

/**
 * 创建时间:2017-1-11
 * 
 * @author Dsz
 */
public class ShuDu3 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int[][] a = new int[9][9];
			boolean[][] cols = new boolean[9][9];
			boolean[][] rows = new boolean[9][9];
			boolean[][] blocks = new boolean[9][9];// 九大宫的九个数字

			for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < a.length; j++) {
					a[i][j] = sc.nextInt();
					if (a[i][j] != 0) {
						// 划分九宫格,这里以行优先,自己也可以列优先
						int k = i / 3 * 3 + j / 3;
						int val = a[i][j] - 1;
						rows[i][val] = true;
						cols[j][val] = true;
						blocks[k][val] = true;
					}
				}
			}
			// 数据装载完毕

			DFS(a, cols, rows, blocks);
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 8; j++) {
					System.out.print(a[i][j] + " ");
				}
				System.out.println(a[i][8]);
			}
		}
	}

	public static boolean DFS(int[][] a, boolean[][] cols, boolean[][] rows,
			boolean[][] blocks) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (a[i][j] == 0) {
					int k = i / 3 * 3 + j / 3;
					for (int l = 0; l < 9; l++) {
						// l对于的数字l+1没有在行列块中出现
						if (!cols[j][l] && !rows[i][l] && !blocks[k][l]) {
							rows[i][l] = cols[j][l] = blocks[k][l] = true;
							// 下标加1
							a[i][j] = 1 + l;
							if (DFS(a, cols, rows, blocks))
								// 递进则返回true
								return true;
							// 递进失败则回溯
							rows[i][l] = cols[j][l] = blocks[k][l] = false;
							a[i][j] = 0;
						}
					}
					// a[i][j]==0时,l发现都不能填进去
					return false;
				}// the end of a[i][j]==0
			}
		}
		return true;// 没有a[i][j]==0,则返回true
	}
}

输出结果:

8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

 

本文转载自:http://blog.csdn.net/hll174/article/details/51090461

dreamcloudz
粉丝 1
博文 22
码字总数 2322
作品 0
海淀
程序员
私信 提问
自己做的数独软件,带解题技巧

奕数独2.0采用C++和Java开发,有8种类型的数独,自带多种解题技巧。目前可以支持Android2.3以上版本。 云盘下载地址:http://pan.baidu.com/s/1jGMfa4Y,多个市场均可以下载。...

天下伯爵
2014/11/27
429
1
linux web篇---之三--tomcat

一、java概述 1、java的四个独立却又相关的技术: java程序设计语言: java源程序 java API: 以连接java的库文件,官方提供很多库文件,以提高java的开发速度,通过API连接到相应的库文件。...

kuang_hp
2018/07/04
0
0
红帽正在秘密筹划“Java杀手”项目Ceylon

Hibernate项目、Java EE 5应用框架Seam的创始人,来自红帽(Red Hat)的Gavin King最近透露了他过去两年从事的超级机密项目,一种设计替代Java的新语言和SDK。 Gavin King在上周日QCon北京2...

红薯
2011/04/14
3K
31
Java多线程学习(五)线程间通信知识点补充

系列文章传送门: Java多线程学习(一)Java多线程入门 Java多线程学习(二)synchronized关键字(1) java多线程学习(二)synchronized关键字(2) Java多线程学习(三)volatile关键字 Ja...

一只蜗牛呀
2018/04/16
0
0
grails 环境找不到java_home

这几天在网上找了开发grails的各种IDE,Eclipse,netbeans,IntelliJ IDEA ,最后选择IntelliJ IDEA 。 使用IntelliJ IDEA 8.1.2生成grails control,结果出现以下错误: ERROR: JAVAHOME is...

greki
2014/05/16
71
0

没有更多内容

加载失败,请刷新页面

加载更多

超过了最大请求长度。

尝试在网站上上传视频时,出现错误“ 最大请求长度超出” 。 我该如何解决? #1楼 我认为这里没有提到它,但是要使其正常工作,我必须在web.config中提供以下两个值: 在system.web <httpRun...

javail
8分钟前
3
0
宝塔好用吗?

不少新手站长对服务器运维知识不擅长,不知道怎样管理好云服务器。如果有一个简单易用的面板,站长们就不需要去学习运维技巧,把这些就交给后端工程师就好。 宝塔算是目前市面上使用用户较多...

BirdCloud
14分钟前
3
0
第二代网关GateWay搭建流程

Spring Cloud第二代网关GateWay是由纯Netty开发,底层为Reactor,WebFlux构建,不依赖任何Servlet容器,它不同于Zuul,使用的是异步IO,性能较Zuul提升1.6倍。搭建过程如下(本次搭建的为子项目...

算法之名
16分钟前
10
0
Drools规则引擎详解-常用的drl实例

package droolsDemo//说明:每个 drl 都必须声明一个包名,这个包名与 Java 里面的不同,它不需要与文件夹的层次结构一致,//主要用于可以根据kmodule.xml中不同的package属性来指定加载...

蜗牛伊
19分钟前
4
0
如何在Android Studio中“选择Android SDK”?

将Eclipse-Android-Project成功导入“ Android Studio 1.4”后,出现错误 “请选择Android SDK” 当我单击该按钮以在模拟器中运行该应用程序时,但找不到任何方法。 当我单击“运行”时,此对...

技术盛宴
23分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部