ricefish

数独 解法 ruby スクリプト

数独を解く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) }enddef 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]  endenddef 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)