注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TOTO

Think and Be Different

 
 
 

日志

 
 

关于数独的求解方法  

2009-01-02 10:50:52|  分类: 看看书 写写笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
数独是一个很有魅力的数学游戏,在玩的时候,发现这个网站的数独不错,可以在线做:http://www.sudoku.name/index-cn.php

言归正传,数独是9*9的方阵,其中可以分为9个3*3的小方阵,可以在里面填1-9的数字,限制条件是:
每行每列不得出现两个相同的数字,并且所在的小方阵内也不能出现两个相同的数字,也就是说,1-9都必须出现并出现一次。

采用非递归的方式来写DFS(深度优先搜索),难点在于当前状态和保存和下一个状态的生成。
为什么是DFS而不是BFS(广度优先搜索)呢?这里主要的原因在于BFS要求保存的状态很多(?),而且很难生成下一个状态。
我们把方阵的数字分为两种类型,一种是固定的,题目中给出的;一种是猜测值,计算机猜的值。
(1)如何有效地保存当前的状态呢? 如果死板的把所有方阵的所有数字都保存,很明显这个做法不好,状态的保存太耗空间。因为我们一般是用栈来保存状态,那么不妨用栈来保存操作序列,比如push(2,3,5)就是把[2, 3]的猜测值为5。这个时候,整个方阵的状态,必须和已经入栈的操作序列形成的结果一致。所以这个时候需要对操作结果在整个方阵中记录,在入栈和出栈的时候,修改方阵中对应小方格的值。
(2)根据一般的DFS:
while(!stack.isEmpty()){
now = stack.peek()
        根据now生成下一个状态next
如果成功,那么将next进栈;
否则,看看now状态是否能够修改,变成另外一个状态,如果可以修改状态,否则pop
}

但是这里面有一个问题是:now如果可以生成下一个状态next,但是next在下一次循环中没有办法生成下一个状态,而且也不能修改当前状态,那么就出现了一个死循环。
出现这个问题的根本原因在于:对于从栈中peek的一个状态来说,不知道前面发生了什么事情,比如由它生成的状态无法前进的时候,这个情况无法反馈到那个状态中。
分析一下:peek一个状态,那么这个状态可能有两种情况,它是由前面一个状态生成的,另外一个就是它是前面状态pop出来的当前状态。特别是第二种情况,我们可以得到当前状态是必须进行修改的,有必要对第二种情况设立一个标签mark。那么就有了以下的逻辑思路:
while(栈不为空){
检查是否已经得到答案;
now = stack.peek();
// 如果是前面一个状态pop出来的结果,那么修改当前状态
if(mark){
mark = false;  //表明有效期结束
now = modifyState(now); 
如果生成失败,那么pop,mark=true;// 表明是pop出来的
否则,修改状态
}
next = generateState(now);
if(next生成失败){
mark = true;//表明当前的状态必须要变化或者弹出
}else{
push(next);
}
}
这样实现了知道当前的状态,可以很明确知道下一步该做什么,有点类似于状态转换。


  评论这张
 
阅读(601)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017