000000 ランダム
 ホーム | 日記 | プロフィール 【お気に入りブログ登録】 【ログイン】

ricefish

2007年08月29日
XML
カテゴリ:パズル

数独を解く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)








最終更新日  2007年08月29日 22時02分54秒

PR

プロフィール


ricefish

カレンダー


Copyright (c) 1997-2018 Rakuten, Inc. All Rights Reserved.