バックトラック法というアルゴリズムで解いていきます。
ソースコード
# coding: utf-8 class Sudoku COORDINATES = (0..8).map{|i| (0..8).map{|j| [i,j]}}.flatten(1) def initialize(file_name) @rows = File.open(file_name, "r").map do |line| next if line.chomp.empty? || line.chomp.include?("#") line.chomp.split("").map(&:to_i) end.compact update_instance_val end # バックトラッキング def solve(n) throw :exit if n == 81 if @board[n] == 0 candidates_set(*COORDINATES[n]).each do |val| unless duplicate?(*COORDINATES[n], val) @rows[COORDINATES[n][0]][COORDINATES[n][1]] = val update_instance_val # sleep 0.1 # print_state # printf "\e[#{13}A"; STDOUT.flush solve(n + 1) end @rows[COORDINATES[n][0]][COORDINATES[n][1]] = 0 update_instance_val end else solve(n + 1) end end # 現在の状態を表示する def print_state puts "#{"-"*21}\n" << @rows.map{|e| e.map{|e| e == 0 ? " " : e}}.map{|e| e.join(" ")} .map{|e| e.scan(/.{1,6}/) }.map{|e| e.join("| ") }.each_slice(3).to_a .map{|e| e.join("\n")}.join("\n------+-------+------\n") << "\n#{"-"*21}\n" end private # @rowsが変更されたときそれ以外のインスタンス変数も更新する def update_instance_val @cols = @rows[0].zip(*@rows[1..8]) @blocks = @rows.each_slice(3).map{|e| e[0].zip(*e[1..2]) } .map{|e| e.flatten.each_slice(9).to_a }.flatten(1) @board = @rows.flatten end # 第i行目第j列目のマスに入れることができる数字の配列を返す def candidates_set(i, j) block_num = case i when 0..2 then case j; when 0..2 then 0; when 3..5 then 1; when 6..8 then 2 end when 3..5 then case j; when 0..2 then 3; when 3..5 then 4; when 6..8 then 5 end when 6..8 then case j; when 0..2 then 6; when 3..5 then 7; when 6..8 then 8 end end (1..9).to_a - @rows[i] - @cols[j] - @blocks[block_num] end # 第i行目第j列目のマスにvalを入れることができるかを判断する # falseであれば重複していないので入れることができる def duplicate?(i, j, val) !candidates_set(i, j).include?(val) end end problem = Sudoku.new("./problem.txt") catch :exit do problem.solve(0) end problem.print_state
アルゴリズム
- 空白のマスに順番に、行、列、3x3ブロックに重複が無い数字を適当に入れていきます
- 途中でその空白に入れることができる数字の候補が無くなった場合、前の空白に戻り入れる数字を変えてみます
このように、ある組み合せで条件を満たせなかった場合、探索木を戻って別の組み合せを試すことをバックトラッキングというそうです。
空白に入れる数字の候補ですが、n番目のマスに入れることができる数字の候補の配列を
candidates_set(*COORDINATES[n])
で取得しています。ここを (1..9).to_a
のように総当たりにすると、自分の環境では4秒ほど実行時間が遅くなります。 candidates_set
ではそのマスがある行、列、3x3ブロックを見てまだ入っていない数字を要素にもつ配列を返すようにしました。全マスとそこに入っている数値をどのように扱うかという点に苦労しました。
再帰的に書くなら0から80番目までのネストしていない配列の方が扱いやすいのですが、そのマスに数字を入れる際、行、列、3x3ブロックに重複が無いかを調べるには第何行目の第何列目のマスであるかという情報ももっていてほしかったのです。そこは結局
Sudoku::COORDINATES
という定数を用意してその中に、第何番目のマスは第何行第何列であるという要素をもたせるようにして解決しました。 solve
メソッド内のコメントを外せば値をセットする度に、マスがどの程度埋まっているのかという状態を表示させることができます。それを表示する関係で、解が見つかった時点でそれ以降の状態は表示させたくなかったので catch/throw
で無理矢理脱出しています。自分の力不足でなんだかとっ散らかったコードになってしまいましたが、参考になれば幸いです。
実行結果
空白は空白で埋めた以下のようなテキストファイルを用意し、さっそく実行してみます。
53 8 2 7 1 5 4 53 1 7 6 32 8 6 5 9 4 3 97
まず、実行の様子がよくわかるように、値をセットする度にその時点での状態をsleepも挟んで表示させてみた結果です。
めっちゃバックトラッキングを感じる!!
いい感じですね。ではsleepを挟まずに最後まで走らせてみましょう。
楽しい!!✌('ω'✌ )三✌('ω')✌三( ✌'ω')✌
おわりに
再帰的に何かをしようとすると毎回のデバッグ作業が大変ですね。
今どの辺りにいるのかとかなんで抜け出さないんだとか考えるのが難しいです。
無限に数独の問題を生成し続けるプログラムも書いて、それを無限に解いていく様子を眺めていたいですね。
参考サイト
Ruby で世界一難しい数独
0 件のコメント:
コメントを投稿