数独を解くruby スクリプトです。
#!/usr/local/bin/ruby
#
# 数独 を解く
#
def printd(d)
" +-------+-------+-------+\n".display
(0...9).each {|i|
(0...9).each {|j| ((j%3==0)?" | ":" ").display; ((d[i][j]==0)?"*":d[i][j]).display }
" |\n".display;
" +-------+-------+-------+\n".display if (i%3==2) }end
def suudoku1(d)
s=0;
begin
s0=s;
d.each_index {|i| d[i].each_index {|j| if ((a=d[i][j]).size==1) ## aを候補から消す
(0...9).each {|k| d[k][j]-=a if (i!=k)}
(0...9).each {|k| d[i][k]-=a if (j!=k)}
(i/3*3...i/3*3+3).each {|k| (j/3*3...j/3*3+3).each {|l| d[k][l]-=a if (i!=k && j!=l)}}
end}}
end until (s0==(s=d.inject(0) {|s,i| s+=i.inject(0) {|s,j| s+=j.size}}))
mi=mj=m=10
d.each_index {|i| d[i].each_index {|j| a=d[i][j].size; mi,mj,m=i,j,a if (a!=1 && a<m) }}
if (m==0) ## 解なし
return []
elsif (m<10) ## d[mi][mj] の取り得る値を入れて解を求める
dd=d[mi][mj].collect {|k|
dd=d.collect {|i| i.collect {|j| j.dup}} ##copy
dd[mi][mj]=[k]; dd}
dd=dd.inject([]) {|dd,d| dd+=suudoku1(d)}
return dd
else ## 解けた
return [d]
end
end
def suudoku(d)
printd(d);
d.each_index {|i| d[i].each_index {|j|
if (d[i][j]==0) then d[i][j]=[1,2,3,4,5,6,7,8,9]; else d[i][j]=[d[i][j]];end}}
dd=suudoku1(d)
printf("Number of solutions: %d\n",dd.size);
dd.each {|d| printd(d); "\n".display}
end
#
# 問題は下記のように Array で記述
#
d=[[1,2,0,0,0,0,7,8,9],
[0,0,0,7,0,9,1,0,4],
[7,0,9,1,2,0,0,0,6],
[2,0,0,0,6,7,0,9,1],
[0,0,0,0,0,1,2,0,0],
[0,9,1,2,0,0,5,0,0],
[0,0,0,6,0,0,0,1,2],
[0,7,0,0,0,2,0,0,0],
[9,0,2,0,0,0,0,7,8]]
suudoku(d)
