2008-05-04 Ruby 测试题(00015)

青年节，我是挨不上边了，上班了，出题。
今天做数独，最近比较流行的一个小php?name=%D3%CE%CF%B7" onclick="tagshow(event)" class="t_tag">游戏。
数独的游戏规则：
9x9个格子里，已有若干数字，其它宫位留白，玩家需要自己按照逻辑推敲出剩下的空格里是什么数字，使得每一行与每一列都有1到9的数字，每个小九宫格里也有1到9的数字，并且一个数字在每个行列及每个小九宫格里都只能出现一次。
输入及输出方式随意，能说明清楚就行。
测试用例一：
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
测试用例二：
000000907
000420180
000705026
100904000
050000040
000507009
920108000
034059000
507000000

PS：数独也是EULER上的一道题目，况且我拿这个来说事，也是为了延续“回溯”这个话题。

帖个不完整的，最近心情不好，想不出好方法

看错题了，这是3*3的，呃，不过9*9应该一样的说

这题难度很高，PU目前能答出的也就1000人左右，
最近比较忙，我也一直没做这题，既然J出题了，还是做一下吧。
但是直接贴程序感觉有违 PU 的宗旨。

先贴答案吧

"483921657"
"967345821"
"251876493"
"548132976"
"729564138"
"136798245"
"372689514"
"814253769"
"695417382"
""
"462831957"
"795426183"
"381795426"
"173984265"
"659312748"
"248567319"
"926178534"
"834259671"
"517643892"

PS：全50题出解在我机器上大约150秒左右，平均3秒解出一道，难题一般也在10秒以内，最慢的是第41和49题，要花11，12秒左右才出答案。
核心伪代码如下

我用一维数组来回溯解的，所以时间差很大，但是笨也有笨的好处，比如，49我只要1秒。。。

[ 本帖最后由 jmouse 于 2008-5-5 10:14 编辑 ]

最近比较忙，这里也不够火热。
先把我的96贴上来