数独游戏

对于简单难度的数独,找到缺数字最少的行列或3×3格,基本上可选的数字是一个,填进去就可以了.对于更难的数独,这种方法就不适用了,一个格子往往有3-5个可选的数.其实完成这种题目也有规律,只要一行一行地试就可以了:
  1. 找到第一个空白格,根据行列判断,填放最小的可以满足行列格的数字,
  2. 找到下一个空白格,填入满足的最小数字,
  3. 如果遇到无法找到满足的数字的情况,说明前边添错了;这时找到上一个填了值的格,找一个比原数字大又尽可能小的数字. 比如一个格可以填2,3,5,并且填了2,这时无法给下一格空白格找到合适的数字,就依次去试3,5. 如果无法找到满足的数字就一直回退.

问题解决的关键其实是保留填表的步骤,并且在适当的时候回退. 如果没有规律没有记录的乱试肯定找不到答案.

思路清楚后很容易地用Orcas beta2写一个小程序帮我做数独.

 

———————————–2008年1月21日更新————————————-

已经过去几个月了, 已经用上了VS2008 RTM, 数独的算法也有了提高. 以前那个方法太笨了, 这就是过度依赖计算机的后果, 手工做了几个高难度的题目后找到了更好的方法. 它基于搜索两种格子: 一种是只有一个可选数字, 另一种是在3×3格子里可选数字只出现过一次. 基于这种判断,解题速度能提高10倍.

Advertisements
This entry was posted in 计算机与 Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s