- 浏览: 584724 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。上文“回溯法入门学习之一”http://128kj.iteye.com/blog/1722216中已给出了一个框架:
"深度优先搜索+回溯"递归框架:
函数DFS(节点){
如果(节点=目标节点) {找到目标,跳出}
遍历所有下一层节点for(int i=0;i<k;i++){
标记下一层节点i已访问;
DFS(下一层的节点i)
恢复i为未访问
}
}
下面使用上面框架再解一例(数独问题):
题目大意,如上图(一):
把一个9行9列的网格,再细分为9个3*3的子网格,要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字,即每行、每列、每个子网格内都不允许出现相同的数字。空格是待填位置,其他均为已填入的数字。
要求填完九宫格并输出(如果有多种结果,则只需输出其中一种),
如果给定的九宫格无法按要求填出来,则输出原来所输入的未填的九宫格。
如上图一中的9个子网络,我们假设子网格的序号如下编排图(二):
先讨论一下上图(一)中第i行j列的数字是属于哪个子网格的,
由于0<=i、j<=8,我们有图(三):
令a= i/3 , b= j/3 ,根据九宫格的行列与子网格(grid)的关系,我们有图(四):
不难发现 3a+b=k,即 3*(i/3)+j/3=k。即图一中第i行j列的数字,属于第k个子网络
算法分析: DFS+回溯
1.把所有空格位置找出来,对他们进行dfs填补(用1,2,3,...9去试填)
2.剪枝方法(九宫格中已有数字的不用试填),把搜索过的相应位置搜索完复位
样例:
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
"深度优先搜索+回溯"递归框架:
函数DFS(节点){
如果(节点=目标节点) {找到目标,跳出}
遍历所有下一层节点for(int i=0;i<k;i++){
标记下一层节点i已访问;
DFS(下一层的节点i)
恢复i为未访问
}
}
下面使用上面框架再解一例(数独问题):
题目大意,如上图(一):
把一个9行9列的网格,再细分为9个3*3的子网格,要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字,即每行、每列、每个子网格内都不允许出现相同的数字。空格是待填位置,其他均为已填入的数字。
要求填完九宫格并输出(如果有多种结果,则只需输出其中一种),
如果给定的九宫格无法按要求填出来,则输出原来所输入的未填的九宫格。
如上图一中的9个子网络,我们假设子网格的序号如下编排图(二):
先讨论一下上图(一)中第i行j列的数字是属于哪个子网格的,
由于0<=i、j<=8,我们有图(三):
令a= i/3 , b= j/3 ,根据九宫格的行列与子网格(grid)的关系,我们有图(四):
不难发现 3a+b=k,即 3*(i/3)+j/3=k。即图一中第i行j列的数字,属于第k个子网络
算法分析: DFS+回溯
1.把所有空格位置找出来,对他们进行dfs填补(用1,2,3,...9去试填)
2.剪枝方法(九宫格中已有数字的不用试填),把搜索过的相应位置搜索完复位
样例:
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
import java.util.Scanner; public class Main{ private int table[][];//用一个二维数组表示九宫格 private int pos[];//记录要填的空格位置 private int posNum;//要填的空格标号(从0开始) private boolean rUsed[][];//rUsed[i][x] 标记在第i行中数字x是否出现了 private boolean cUsed[][];//cUsed[j][y] 标记在第j列中数字y是否出现了 private boolean sUsed[][];//sUsed[k][x] 标记在第k个3*3子格中数字z是否出现子 private boolean finish_dfs;//是否已找到了答案 public void go(){ Scanner in=new Scanner(System.in); int cnt=in.nextInt(); while((cnt--)!=0){ //初始化数据 posNum = 0; pos=new int[90]; table=new int[9][9]; rUsed=new boolean[9][10]; cUsed=new boolean[9][10]; sUsed=new boolean[9][10]; String line=null; finish_dfs = false; for(int i=0;i< 9;i++){ //准备输入数据 line=in.next(); for(int j=0;j< 9;j++){ table[i][j]=line.charAt(j)-'0'; if (table[i][j]!=0 ) { rUsed[i][table[i][j]] = true;//table[i][j]这个数字在i行中已有了 cUsed[j][table[i][j]] = true; int k = (i/3)*3+(j/3); sUsed[k][table[i][j]] = true;//table[i][j]这个数字在第k个小网络中已有了 } else { pos[posNum++] = i*9+j;//记录要填的空格位置及标号 } } } dfs_sudoku(0); } } private void outre(){//输出结果 for ( int i = 0; i < 9; i++ ) { for ( int j = 0; j < 9; j++ ) { System.out.printf( "%d", table[i][j] ); } System.out.println(); } //System.out.println(); } void dfs_sudoku( int n ){//深度优先搜索+回溯,试填第n个空格) if ( n >= posNum ) { finish_dfs = true; outre(); return; } //根据要填的空格位置,计算空格的所在的行,列坐标及处在哪个小网络 int r = pos[n]/9;//空格的行坐标 int c = pos[n]%9;//空格的列坐标 int s = (r/3)*3+(c/3);//小网络的标号 for ( int i = 1; i <= 9 && !finish_dfs; i++ ) {//用1,2,3...9去试填) if ( rUsed[r][i] ) continue;//第r行有i if ( cUsed[c][i] ) continue;//第c列有i if ( sUsed[s][i] ) continue;//第k个小网络有i rUsed[r][i] = cUsed[c][i] = sUsed[s][i] = true; table[r][c] = i;//第r行c列试填数字i dfs_sudoku( n+1 );//递归试填第n+1个空格,成功或失败,如果成功则输出,失败则回溯 table[r][c] = 0;//回溯 rUsed[r][i] = cUsed[c][i] = sUsed[s][i] = false; } return; } public static void main(String[] args){ Main ma=new Main(); ma.go(); } }
发表评论
-
龙抬头
2014-11-10 15:06 551... -
求推箱子的最小步数(java)
2014-05-06 08:32 3664题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2983POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之一
2012-11-10 15:53 1776一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1870很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5822Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3989一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1211一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 1966先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2264一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2225继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4907深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1403如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1102例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1459广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之一
2012-10-13 15:27 1642有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2064再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2222凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1071最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1233矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
九宫格数独100题及答案(初级可打印版)
一个完整的九宫格(数独)游戏代码,内置100多个游戏初始数据
android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码
以前玩九宫格(数独)游戏 怎么都没有成功,就想用程序做一个软件自动填数,花了2天时间做的,大家可以用来生成九宫格的正确答案。
九宫格数独题目生成器,已更新多线程处理。本人原创,请勿转载。
九宫格智力数独200题题+答案.doc
个人写的一个数独九宫格的破解软件,内有注解,喜欢的下载下来研究下,内是项目文件和程序
Sudoku-九宫格-数独matlab代码,matlab需要嵌入凸优化CVX工具包
下载excel后,打开下方的sheet1,即为九宫格题目,复制到word内打印即可。 详细说明: 1.更改sheet2内的A1单元格内的数字(范围1-9),可以调节数独的难度,1难度最低,9难度最高,建议设置为5以下。 2.sheet2内为...
java 数独 九宫格 算法 小游戏 算法研究,程序员高级笔试上机题目
九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,
本文件是九宫格数独游戏源代码,学习游戏编程的好帮手
九宫格数独题目.doc
Sudoku-九宫格-数独matlab代码(含CVX工具包)
九宫格数独题目大全.doc
填充sizes*sizes大小的数独九宫格,利用JavaScript来实现对任意大小的数独九宫格的填充
数独是一种比较费时费脑的游戏,一般难度的数独玩下来也得1个小时左右,本人是伪数独爱好者,碰到难点的数独需要花上若干个小时,于是偷懒写了一套破解程序,特拿出来分享,希望有人喜欢。
Excel制作的九宫格数独游戏,含出题和解题,vba编写。
自己整理的数独九宫格200题(难度系数1-4级).doc
数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。 这种游戏全面考验...