2015年2月18日水曜日

Rubyで数独を解く

数独(ナンプレ)を解くコードをRubyで書いてみました。
バックトラック法というアルゴリズムで解いていきます。


ソースコード

?
sudoku.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# 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

アルゴリズム
  1. 空白のマスに順番に、行、列、3x3ブロックに重複が無い数字を適当に入れていきます
  2. 途中でその空白に入れることができる数字の候補が無くなった場合、前の空白に戻り入れる数字を変えてみます
…ということを繰り返してる内にいつか埋まるだろうという方法です。
このように、ある組み合せで条件を満たせなかった場合、探索木を戻って別の組み合せを試すことをバックトラッキングというそうです。

 空白に入れる数字の候補ですが、n番目のマスに入れることができる数字の候補の配列を candidates_set(*COORDINATES[n]) で取得しています。ここを (1..9).to_a のように総当たりにすると、自分の環境では4秒ほど実行時間が遅くなります。

  candidates_set ではそのマスがある行、列、3x3ブロックを見てまだ入っていない数字を要素にもつ配列を返すようにしました。

 全マスとそこに入っている数値をどのように扱うかという点に苦労しました。
再帰的に書くなら0から80番目までのネストしていない配列の方が扱いやすいのですが、そのマスに数字を入れる際、行、列、3x3ブロックに重複が無いかを調べるには第何行目の第何列目のマスであるかという情報ももっていてほしかったのです。そこは結局 Sudoku::COORDINATES という定数を用意してその中に、第何番目のマスは第何行第何列であるという要素をもたせるようにして解決しました。

 solve メソッド内のコメントを外せば値をセットする度に、マスがどの程度埋まっているのかという状態を表示させることができます。それを表示する関係で、解が見つかった時点でそれ以降の状態は表示させたくなかったので catch/throw で無理矢理脱出しています。

 自分の力不足でなんだかとっ散らかったコードになってしまいましたが、参考になれば幸いです。

実行結果

空白は空白で埋めた以下のようなテキストファイルを用意し、さっそく実行してみます。
?
problem.txt
1
2
3
4
5
6
7
8
9
  53    
8      2
 7  1 5 
4    53 
 1  7   6
  32   8
 6 5    9
  4    3
     97 


 まず、実行の様子がよくわかるように、値をセットする度にその時点での状態をsleepも挟んで表示させてみた結果です。


めっちゃバックトラッキングを感じる!!
いい感じですね。ではsleepを挟まずに最後まで走らせてみましょう。


楽しい!!✌('ω'✌ )三✌('ω')✌三( ✌'ω')✌

おわりに

 再帰的に何かをしようとすると毎回のデバッグ作業が大変ですね。
今どの辺りにいるのかとかなんで抜け出さないんだとか考えるのが難しいです。

 無限に数独の問題を生成し続けるプログラムも書いて、それを無限に解いていく様子を眺めていたいですね。

参考サイト

Ruby で世界一難しい数独

投稿者 時刻:
ラベル: ,

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)