星期日, 四月 29, 2007

邪恶的Sudoku

近Automated Reasoning of AI的一篇报告,研究计算机解SUDOKU的难易度问题。
从WebSudoku上找了800道题目,simple,medium,hard,evil各200道,然后分别解800遍,计算时间。这四种分类是WebSudoku上的解题专家给出的。计算机解题用的是zChaff,这不是一个专门解SUDOKU的程序,而是一个命题逻辑可满足性问题的解算器。所以它解题的思路和人类是不一样的,没有各种技巧或策略之类的东西。
分析主要是看时间和初始数字的关系。下面的图中,横坐标是平均每行的初始数字数,纵坐标是800题的时间。红点是simple题,蓝点是medium题,绿点是hard题,黑点是evil题。时间超过6秒的题都被去掉了。

很明显的可以看出,这四种难度对初始数字数目有着强烈的依赖关系。数目越少,难度越高。而且一个很有趣的现象是:点的分布代表了计算机解题的难度,而颜色则代表了人类解题的难度,这两种难度之间没有必然的关系,但却表现出了明显的一致性。
更有趣的是下图,其中红点是给定初始数字数目时计算机解题时间的平均值。

可以看到,平均时间大致上有三个跳跃点:分别是横坐标值从3.66667到3.55556,3.22222到3.11111,3到2.8889。而这三个跳跃点,恰好与人类难度的三条分界线吻合!
无论是否巧合,这都是个令人印象深刻的结果。
此外,我还试图分析初始数字集中或分散对难度的影响。结果很遗憾的发现,集中或分散无论对人还是机器解题的难度,都没有直接的关系,这多少与我们的直觉相违背。直观上来说,数字集中的话代表有些行、列或块比较空,难度应该上升,但实际不是这样。
从第二张图里还能看到有道题是extremly evil的,一骑绝尘,难度远超其它题目,是最高平均难度的三倍。这道题是这样的
X X 7|X X X|4 X 9
X 5 X|4 X X|X X X
3 X X|X 2 7|X X 5

X X X|X X X|6 X X
X X 8|5 X 4|9 X X
X X 3|X X X|X X X

6 X X|2 1 X|X X 3
X X X|X X 3|X 4 X
1 X 5|X X X|8 X X
大家来试试吧:-)
确实不是一般的邪恶啊T.T