数独をプログラムで解いてみる

　頭の体操がてらに、数独を解くプログラムを書いてみました。

とりあえず、データ構造はこんな感じで持とうと思います。

cels = [
  0,0,5,3,0,0,0,0,0,
  8,0,0,0,0,0,0,2,0,
  0,7,0,0,1,0,5,0,0,
  4,0,0,0,0,5,3,0,0,
  0,1,0,0,7,0,0,0,6,
  0,0,3,2,0,0,0,8,0,
  0,6,0,5,0,0,0,0,9,
  0,0,4,0,0,0,0,3,0,
  0,0,0,0,0,9,7,0,0
]

同じ列・行・ブロック(太線で囲まれた3×3)に入るマスを取得する関数は必要になるかな、と特に何も考えずコーディング

def mklist start, count, step
  count.times.map{|i| start + i*step}
end
def last_one clist
  clist if clist.size == 1
end
def get_effect_area idx
  get_row_area(idx) +
    get_col_area(idx) +
    get_block_area(idx)
end
def get_row_area idx
  mklist((idx - idx % 9), 9, 1)
end
def get_col_area idx
  mklist(idx%9, 9, 9)
end
def get_block_num idx
  x = idx % 3
  y = idx / 9 % 3
  idx - (x + y*9)
end
def get_block_area idx
  fh = get_block_num idx
  mklist(fh, 3, 1) +
    mklist(fh+9, 3, 1) +
    mklist(fh+18, 3, 1)
end

さて、普段自分が数独を解くときのことを考えると、戦略としては

そのマスに入り得る数字が1つのマスを探す
同じ行のマスのうち、そのマスにしかある数字が入らないようなマスを探す

という2つの観点で解いてる気がします。

そのマスに入り得る数字の候補を各マス毎に持つとすると、こんな感じでしょうか。

work = cels.map{|c| c == 0 ? (1..9).to_a : [c] }

初めは、すべてのマスに１〜９までの数字を持たせておいて、そのマスに入る可能性が消えた数字を配列から取り除きます。このデータ構造を使って上記の2つの考え方を試してみます。

def print_nums nums
  row_sepalater = ['+','+','+','+'].join('-'*7)
  nums.each.with_index do |n, i|
    puts '|' if i % 9 == 0 and i > 0
    puts row_sepalater if i % (9*3) == 0
    print '| ' if i % 3 == 0
    print n.to_s + ' '
  end
  puts '|', row_sepalater
end

def rest_count work
  work.map{|c|c.size}.reduce(:+)
end

def find_comp_cell area, cels, work
  (1..9).each do |i|
    cand = area.select{|r| work[r].include? i}
    cels[cand[0]] = i if cand.size == 1
    return false if cand.size == 0
  end
  return true
end

100.times do 
  cels.each.with_index do |c, idx|
    if c == 0
      cels[idx] = work[idx][0] if work[idx].size == 1
    else
      get_effect_area(idx).each do |ei|
        work[ei].delete(c) if ei != idx
      end
    end
  end

  key_cel.each do |idx|
    find_comp_cell(get_row_area(idx), cels, work)
    find_comp_cell(get_col_area(idx), cels, work)
    find_comp_cell(get_block_area(idx), cels, work)
  end

  break if rest_count(work) <= 9*9
end

print_nums cels

結果

+-------+-------+-------+
| 0 0 5 | 3 0 0 | 0 0 0 |
| 8 0 0 | 0 5 0 | 0 2 0 |
| 0 7 0 | 0 1 0 | 5 0 0 |
+-------+-------+-------+
| 4 0 0 | 0 0 5 | 3 0 0 |
| 0 1 0 | 0 7 3 | 0 0 6 |
| 0 0 3 | 2 0 0 | 0 8 0 |
+-------+-------+-------+
| 0 6 0 | 5 0 0 | 0 0 9 |
| 0 0 4 | 0 0 0 | 0 3 0 |
| 0 0 0 | 0 0 9 | 7 0 0 |
+-------+-------+-------+

駄目か...。そうすんなりとは行きませんでした。後は、残りのマスに、数字を仮置きしてみて、矛盾が起きたらトラックバックという方法がありますが、あまり格好よくないなあ。

先ほど作った処理を関数化し、再起関数呼び出しを使ってトラックバックを実現しました。

def check1 cels, work
  cels.each_with_index do |c, idx|
    if c == 0
      cels[idx] = work[idx][0] if work[idx].size == 1
    else
      get_effect_area(idx).each do |ei|
        work[ei].delete(c) if ei != idx
      end
    end
  end
end

def find_comp_cell area, cels, work
  (1..9).each do |i|
    cand = area.select{|r| work[r].include? i}
    cels[cand[0]] = i if cand.size == 1
    return false if cand.size == 0
  end
  return true
end

def check2 cels, work
  r = true
  key_cel = [0,12,24,28,40,52,56,68,80]
  key_cel.each do |idx|
    r &&= find_comp_cell(get_row_area(idx), cels, work)
    r &&= find_comp_cell(get_col_area(idx), cels, work)
    r &&= find_comp_cell(get_block_area(idx), cels, work)
    return false unless r
  end
  return true
end

def deep_copy obj
  Marshal.load Marshal.dump(obj)
end

def resolve cels, work
  prev = 9**3
  while prev > rest_count(work) do
    prev = rest_count(work)
    check1 cels, work
    return :conflict unless check2 cels, work
    return :resolved if rest_count(work) == 9*9
  end
  return :continue
end

# 仮に数字を置いてみて、矛盾したらトラックバック
# を繰り返し、すべてのパターンを試す
def try_fill cels, work
  # 数字を置ける候補が少ないほうが効率がいいはず
  idx, lst = work.each_with_index.map{|w,i|[i,w]}.
    select{|i,w|w.size > 1}.min_by{|i,w|w.size}

  lst.each do |n|
    cels_new = deep_copy cels
    work_new = deep_copy work
    cels_new[idx] = n
    work_new[idx] = [n]

    case resolve(cels_new, work_new)
    when :resolved
      print_matrix cels_new
      return :resolved
    when :continue 
      if try_fill(cels_new,work_new) == :resolved
        return :resolved 
      end
    end
  end
  :conflict
end

# ---- start ----
case resolve(cels, work)
when :resolved then print_matrix cels
when :continue then try_fill cels,work
when :conflict then raise  
end

解けた！

+-------+-------+-------+
| 1 4 5 | 3 2 7 | 6 9 8 |
| 8 3 9 | 6 5 4 | 1 2 7 |
| 6 7 2 | 9 1 8 | 5 4 3 |
+-------+-------+-------+
| 4 9 6 | 1 8 5 | 3 7 2 |
| 2 1 8 | 4 7 3 | 9 5 6 |
| 7 5 3 | 2 9 6 | 4 8 1 |
+-------+-------+-------+
| 3 6 7 | 5 4 2 | 8 1 9 |
| 9 8 4 | 7 6 1 | 2 3 5 |
| 5 2 1 | 8 3 9 | 7 6 4 |
+-------+-------+-------+

もっといい方法もありそうですが、自分ではこれが限界でした。折を見てまた考えてみようかと思います。

それにしても、コンピュータで解いてもあまり感動がありませんね(^^;