豆丁微信公众号
君，已阅读到文档的结尾了呢~~
广告剩余8秒
文档加载中
数独解题方法之候选数法,数独解题方法大全,数独解题方法,数独的解题方法,数独解题器,数独解题,数独解题技巧,数独在线解题,数独候选数法,数独解题步骤
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数独解题方法之候选数法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口回溯法解数独游戏
回溯法解数独游戏
采用回溯法最经典的例子是解决8皇后和迷宫的问题。不习惯走别人的路，所以下面介绍下用回溯法解数独游戏。写这个算法的起因是之前在玩数独游戏时，遇到了难解的专家模式，就想着写程序来暴力破解，是不是很无赖，啊哦……
数独（すうどく，Sūdoku），是源自18世纪瑞士发明，流传到美国，再由日本发扬光大的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。下图是一个完整的数独例子。
下图是iPad上一个数独游戏专家模式下的截图。81个格子，只给了17个数字，确实有点难度哈。
将上图转化成程序能够识别的输入，{1,1,9}表示第一行第一列的格子数字是9。
{1,1,9},{1,2,1},{1,8,4},{3,4,5},{3,6,3},{4,1,5},{4,3,6},{4,6,8},{4,7,3},{6,5,1},{6,8,2},{6,9,4},{7,1,8},{7,3,5},{8,3,3},{9,5,4},{9,9,1}
运行程序，得出如下解：
~~~~~~~~~~~~
~~~~~~~~~~~~
仔细观察不难发现，每一行、每一列和每一个九宫格里都是数字1~9不重复。这就构成了一个数独的解。也证明，算法通过测试。
算法在解数独题时，在依次决定每个格子的数字时会根据之前已经填入的数字判断当前格子可能填入的数字，然后选择其中一个再去跳到下一个格子。当后面出现无解的情况（一个格子没有可填入的数字），就依次回退到上一个格子，选取下一个可能填入的数字，再依次执行下去。直到填入了最后一个格子，才算完成了数独的一个解。
回溯法思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
* 填充数字。实质上是深度遍历一棵具有9分支的树，直至遍历到它的第81层。一定要通过一些判断剪断其无用分支，不然该算法的时间复杂度相当可怕
void set_item(Item* items, int position) {
if (position==ROW*COLUMN) {
printf("第%d个\n",++count);
for (int i = 0; i & COLUMN * ROW; i++) {
printf("%3d", items[i].numbers[0]);
if ((i + 1) % COLUMN == 0)
printf("\n");
printf("\n");
if(items[position].choose!=0){
set_item(items, position + 1);
int num =0;
while (( num= getUseableNum(items, position)) != 0) {
if (is_can_set(items, num, position) == 1) {
set_item(items, position + 1);
if (position != 0&&items[position].numbers[0]!=0)
goback(items, position);
测试算法代码段
//定义好17个已经确认的格子
Point points[17]={{1,1,9},{1,2,1},{1,8,4},{3,4,5},{3,6,3},{4,1,5},{4,3,6},{4,6,8},{4,7,3},{6,5,1},{6,8,2},{6,9,4},{7,1,8},{7,3,5},{8,3,3},{9,5,4},{9,9,1}};
//初始化数独矩阵
init_matrix(items, COLUMN * ROW);
//将17个格子填入数独矩阵中
init_point(items, points, 17);
//从第一个格子开始遍历
set_item(items, 0);
附上用到的自定义的函数，用来决定当前格子可填入的数字的判断。
* 获取可用的数字
int getUseableNum(Item* items, int position) {
for (int i = 1; i & SCALE * SCALE + 1; i++) {
if (items[position].used[i] == 0 && items[position].numbers[i] == 0) {
* 判断一个数字在指定的格子中是否可以插入，返回0表示不能插入，寻找下一个，
int is_can_set(Item* items, int num, int position) {
find_row(row_matrix, position);
for (int i = 1; i & SCALE * SCALE + 1; i++) {
if(items[row_matrix[i]].numbers[0]==num&&(items[row_matrix[i]].used[num]*items[row_matrix[i]].numbers[num])!=0){
items[position].used[num]=1;
find_column(column_matrix, position);
for (int i = 1; i & SCALE * SCALE + 1; i++) {
if(items[column_matrix[i]].numbers[0]==num&&(items[column_matrix[i]].used[num]*items[column_matrix[i]].numbers[num])!=0){
items[position].used[num]=1;
find_block(block_matrix, position);
for (int i = 1; i & SCALE * SCALE + 1; i++) {
if(items[block_matrix[i]].numbers[0]==num&&(items[block_matrix[i]].used[num]*items[block_matrix[i]].numbers[num])!=0){
items[position].used[num]=1;
if (items[position].numbers[0] != 0) {
changeItemNum(items, row_matrix, items[position].numbers[0],
SCALE * SCALE + 1, -1);
changeItemNum(items, column_matrix, items[position].numbers[0],
SCALE * SCALE + 1, -1);
changeItemNum(items, block_matrix, items[position].numbers[0],
SCALE * SCALE + 1, -1);
items[position].numbers[0] =
changeItemNum(items, row_matrix, num, SCALE * SCALE + 1, 1);
changeItemNum(items, column_matrix, num, SCALE * SCALE + 1, 1);
changeItemNum(items, block_matrix, num, SCALE * SCALE + 1, 1);
items[position].used[num] = 1;
* 清空当前格子输入的信息
void goback(Item* items, int position) {
int currentNum = items[position].numbers[0];
find_row(row_matrix, position);
changeItemNum(items, row_matrix, currentNum, SCALE * SCALE + 1, -1);
find_column(column_matrix, position);
changeItemNum(items, column_matrix, currentNum, SCALE * SCALE + 1, -1);
find_block(block_matrix, position);
changeItemNum(items, block_matrix, currentNum, SCALE * SCALE + 1, -1);
items[position].numbers[0]=0;
for (int i = 1; i & SCALE * SCALE + 1; i++) {
items[position].used[i] = 0;
*修改item中的数字，items表示整个数独。matrix表示需要修改的下标，length表示需要修改个数。flag +1表示设置，-1 表示重置
void changeItemNum(Item* items, int* matrix, int num, int length, int flag) {
for (int i = 1; i & i++) {
int position = matrix[i];
items[position].numbers[num] +=
这个算法，不仅可以用来解数独题，还可以用来遍历数独所有的终盘，由于9x9的数独，终盘数量巨大，共6,670,903,752,021,072,936,960（约为6.67×10^21）种组合，程序一直运行不完结果。如果对这个值没有概念，请试想将所有的终盘存在txt文本中，只存储数字将占用6.07x10^9 TB存储空间，相信没有哪台电脑能够做到。换句话说，我电脑CPU的主频是2.4GHz，意思是1秒钟执行2.4x10^12条指令，假设解出一种终盘需要一条指令（事实上远大于1条），消耗的时间是88年，本宝宝等不了那么久。庆幸的是4x4 的数独只有288个终盘，程序还是能够很快的完美输出所有解。为什么两者差别这么大，因为穷举法数独的算法时间复杂度是T= n^(n^2).
n = 4时，T = 。n = 9时，T= 1.97Ex10^77。呵呵哒……
回溯算法高效解标准数独
回溯法解数独题
【算法分析】回溯法解数独（九宫格）算法
数独算法-递归与回溯
算法之6-回溯法解数独问题
回溯法简单应用--解数独
回溯法------ 解数独游戏（2）
数独求解算法（回溯法和唯一解法）java实现
没有更多推荐了，数独解题方法大全_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&100W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数独解题方法大全
阅读已结束，下载本文需要
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩18页未读，
定制HR最喜欢的简历
你可能喜欢数独中奇特的解法——关键数删减法
在进入到解题后期，利用前面讲到的方法都无法有进展时，可以考虑使用关键数删减法。关键数删减法就是在后期
找到一个数，这个数在行、列或九宫格只出现两次，我们假定这个数在其中一个宫格里，继续求解，如果产生矛
盾，则假设错误，这就是关键数删减法。
关键数删减法的本质是让我们一个个去测试，逐渐排除不可能的候选数，从而求解的过程。
责任编辑：
声明：该文观点仅代表作者本人，搜狐号系信息发布平台，搜狐仅提供信息存储空间服务。
今日搜狐热点【入门】数独的候选数法解题技巧——第四课
【A+研究所】荣誉会员☆网校制霸
数独的候选数法解题技巧——第四课区块删减法应用显式唯一法和隐式唯一法只能解决简单的谜题，遇到稍复杂的谜题，还是要靠其他的方法。区块删减法也是比较常用的方法，它的目的是尽量删减候选数，而不一定要生成某一单元格的唯一解（当然，产生唯一解更好）。区块删减法是利用区块中的候选数和行或列上的候选数之间的交互影响而实现的一种删减方法，它分为两种情况：·区块对行或列的影响观察下图：可以看到在起始于[A7]的区块中，数字9只出现在[A9]和[C9]的候选数中，更巧的是，[A9]和[C9]正好都在同一列上，即第9列。这时就可以应用区块删减法了。具体地说，在起始于[A7]的区块中，数字9只能填在[A9]或是[C9]中，又因为这两个单元格都在第9列上，所以无论数字9填在哪个单元格中，第9列的其他单元格中都不能再填数字9，所以要把9从它们的候选数中删除。在上图中，位于第9列的单元格[E9]中的候选数9将被删除。下图说明的是区块对行的影响：在起始于[G1]的区块中，只有[H2]和[H3]可以填入数字3，而这两个单元格正好都在行H中。同样的道理，在这个区块中无论数字3填入[H2]还是[H3]，行H中的其他单元格中都不可能再填入3，所以在单元格[H4]，[H6]和[H7]的候选数中的3将被删除。·行或列对区块的影响与“区块对行或列的影响”相近但却不同，“行或列对区块的影响”着重于先对行或列进行分析。观察下图：在第5列中，8只出现在[D5]和[F5]的候选数中；也就是说，第5列中的数字8只能填入这两个单元格其中的一个。碰巧的是，这两个单元格正好都位于起始于[D4]的区块中，结果使得这一区块中的数字8也不能填入区块的其他单元格中，所以[D4]，[E4]，[E6]和[F6]的候选数中的8将被删除。同样，下图说明了行对区块的影响：在行E中，只有[E5]和[E6]能填入数字6，而这两个单元格又刚好都在起始于[D4]的区块中，所以该区块中的其他单元格内不能再填入数字6，即6将从单元格[D5]和[F5]的候选数中删除。总结一下区块删减法的条件，就是1. 在某一区块中，当所有可能出现某个数字的单元格都位于同一行时，就可以把这个数字从该行的其他单元格的候选数中删除。2. 在某一区块中，当所有可能出现某个数字的单元格都位于同一列时，就可以把这个数字从该列的其他单元格的候选数中删除。3.
在某一行（列）中，当所有可能出现某个数字的单元格都位于同一区块中时，就可以把这个数字从该区块的其他单元格的候选数中删除。虽然区块删减法应用比较广泛，但是还是要先给大家泼盆冷水。因为在很多时候，即使满足了区块删减的条件，也可能会发生没有候选数可以删减的情况，让人空欢喜一场。其实，这个问题对其他稍复杂的方法都是普遍存在的。选编自网络.
本帖来源社刊
数独（すうどく，Sūdoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。可以提高你的逻辑推理能力哟～
相关社刊：数独题http://st.hujiang.com/mag/16549
你需要登录后才可以回帖
扫一扫分享朋友圈
需要先加入社团哦
复制到我的社团}