Author Topic: 数独(Sudoku)  (Read 4813 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
数独(Sudoku)
« on: 七月 12, 2012, 05:49:41 pm »
我第一次听说数独还是5年以前。当时觉得很有趣,连它的规则都没搞懂就上了一个贴Sudoku
那时它还不是很流行,现在已经流行很多了。美国几乎各大报纸天天都有。飞机上的杂志也有。
刚开始的时候几乎都是空的,现在几乎都被填过了,可见流行程度。

我热衷了一阵以后就冷了下来。今天再次提起是因为最近有个关于它的新闻。

芬兰一位数学家设计了号称史上最难的数独游戏。



关于这个题目的难度及相关报道可以看这个链接 Hardest Sudoku Ever.

websudoku.com 的题分容易,中等,困难和魔鬼共4级。容易级一星,魔鬼级5星。这个题目
号称11星。我自己验证了一下。我的程序对容易级只需0.043秒。对魔鬼级0.177秒。
log2(0.177/0.044)=2.0082。差不多半个log2算一个星。芬兰那道题用了2.893秒。
log2(2.893/0.177)=4.0307。相差8级,所以应该算13级。

这个题有21个已知数,目前有定理证明有唯一确定解的数独题最少必须有17个已知数数。当然,
已知数个数只能算难度的一个指标,另一个指标是递归深度。这道题的递归深度比有些只有17个
已知数的题目还要深3层,确实够难。

关于数独的一些有趣数据是:所有可能的数独解的个数是 6670903752021072936960 ,这本
身就不是一个简单问题,不是那么容易算。 除去换数换行换列等对称因素后,共有5472730538
种独立解。另外那个关于唯一解必须有至少17个初始数的结果是用计算机验证的。据说用了超级
计算机七百一十万核心小时(Core Hour)。他们用一个超级计算机群分组算,用了将近一年时
间(从一月到11月)。

MATLAB之父Cleve Moler (MATLAB 的原始作者) 最近出了一本书,《用MATLAB做实验》,其
中一章就叫“数独”。讲了很多与数独有关的计算问题。前几天与他聊起芬兰人新设计的这个数独题
目,他说,这个题确实难,比我见过的最难的难一倍。

在网上看到有人说中国网友秒杀那道芬兰题。不知道那个秒杀是什么意思。如果没用程序,一小时
能杀就已经很不错了。我的程序对那道芬兰题用时2.89秒,可以说是“秒杀”。 :-D

我现在对数独已经没有兴趣,更有兴趣的是KenKen,更对数学胃口。有兴趣的可以去看一看
www.kenken.com。我们这里以前也提到过。