jmouse 2008-5-4 11:15
2008-05-04 Ruby 测试题(00015)
青年节，我是挨不上边了，上班了，出题。
今天做数独，最近比较流行的一个小游戏。
数独的游戏规则：
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上的一道题目，况且我拿这个来说事，也是为了延续“回溯”这个话题。
司马睿风 2008-5-4 15:13
帖个不完整的，最近心情不好，想不出好方法[code]class Array < Object
def devide
all = [[nil,nil,nil],[nil,nil,nil],[nil,nil,nil]]
self.clone.each {|v|
all[0][self.index(v)] = v if self.index(v) < 3
all[1][self.index(v) - 3] = v if [3,4,5].include?(self.index(v))
all[2][self.index(v) - 6] = v if self.index(v) > 5
}
return all
end
end[/code]
司马睿风 2008-5-4 15:14
看错题了，这是3*3的，呃，不过9*9应该一样的说
bbschat 2008-5-4 19:07
这题难度很高，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秒左右才出答案。
核心伪代码如下[code] 读取输入，构建数独对象（以下简称对象）
对该对象进行检查（持续填入可能情况只有1个的数字，同时判断冲突），设定对象的解决状态。
while 对象未解决
break if 对象无解并且尝试列表为空
if 对象解决状态为可以继续尝试
选取该对象可选值最少的单元
删除并记录该单元的第一个尝试值
尝试列表（数组）追加该对象
对设定尝试值的对象进行检查（调用上面使用的检查函数）
else
尝试列表 pop，除非尝试列表最后一个对象的可选值最少的那个单元有尝试值
设定对象为尝试列表的最后一个对象
end
end[/code]说穿了就是用计算机模仿一般人解数独的实际做法，想看完整代码的话，请短消息沟通？:)
追加2个Case
Grid 41
000900002
050123400
030000160
908000000
070000090
000000205
091000050
007439020
400007000
Grid 49
000003017
015009008
060000000
100007000
009000200
000500004
000000020
500600340
340200000
[[i] 本帖最后由 bbschat 于 2008-5-4 19:53 编辑 [/i]]
jmouse 2008-5-5 10:12
我用一维数组来回溯解的，所以时间差很大，但是笨也有笨的好处，比如，49我只要1秒。。。
[[i] 本帖最后由 jmouse 于 2008-5-5 10:14 编辑 [/i]]
jmouse 2008-5-13 11:34
最近比较忙，这里也不够火热。
先把我的96贴上来[code]def Euler96()
arr = IO.readlines("sudoku.txt")
sum = 0
ii = 1
for k in (0...arr.size/10)
tmp=[]
(0).upto(8){|i|
tmp[i] = arr[k*10 + i+1]
}
$matrix = ""
$ori = ""
0.upto(8) {|x|
0.upto(8) {|y|
$ori += tmp[x][y].chr
$matrix += tmp[x][y].chr
}
}
#puts k
t0 = Time.now
sum += solve()
printf "i=%d, time=%d\n",ii,Time.now-t0
ii+=1
STDOUT.flush
end
puts sum
end
def solve()
n = 0
while true
if $ori[n] == 48
$matrix[n] += 1
if $matrix[n] == 58
$matrix[n] = 48
j = n - 1
while j >= 0
break if $ori[j] == 48
j -= 1
end
if j == -1
puts "No"
break
end
n = j
else
if check(n)
j = n + 1
while j < 81
break if $matrix[j] == 48
j += 1
end
if j == 81
=begin
0.upto(8) {|x|
0.upto(8) {|y|
nn = x * 9 + y
printf "%s",$matrix[nn].chr
}
printf "\n"
}
=end
tt = $matrix[0].chr + $matrix[1].chr + $matrix[2].chr
return tt.to_i
end
n = j
end
end
else
n += 1
end
end
end
def check(n)
x = n / 9
y = n % 9
count_x = 0
count_y = 0
0.upto(8) {|i|
count_x += 1 if $matrix[n] == $matrix[i * 9 + y]
count_y += 1 if $matrix[n] == $matrix[x * 9 + i]
}
return false if count_x > 1 or count_y > 1
xx = (x / 3)*3
yy = (y / 3)*3
count = 0
0.upto(2) {|i|
count += 1 if $matrix[n] == $matrix[xx*9+yy + i]
count += 1 if $matrix[n] == $matrix[(xx+1)*9+yy + i]
count += 1 if $matrix[n] == $matrix[(xx+2)*9+yy + i]
}
return false if count > 1
return true
end
#test
Euler96()[/code]