数独解かせてみよう

ただの気分で書き始めたのだけれど、Ruby で数独を解いてくれるプログラム。
ただし、問題は手入力だし１つめのプログラムは必ず解いてくれるわけではない。

１つめ。候補が１つしかないものを入れ続ける感じ。簡単な問題用。２つめよりも早いと思う。

def check_box( data, wid, hei )
  w, h, k = wid*3, hei*3, 
  for i in h..h+2
    for j in w..w+2
      k << data[i][j]
    end
  end
  k
end
def check_width( data, hei )
  k = 
  for i in 0..8
    k << data[hei][i]
  end
  k
end
def check_height( data, wid )
  k = []
  for i in 0..8
    k << data[i][wid]
  end
  k
end

data =
[ [5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9] ]
while true
  data.each_with_index{ |dat, height|
    dat.each_with_index{ |number, width|
    if number == 0
      koho = [1, 2, 3, 4, 5, 6, 7, 8, 9]
      koho -= check_box(data, width / 3, height / 3)
      koho -= check_width(data, height)
      koho -= check_height(data, width)
      if koho.size == 1
        data[height][width] = koho[0]
      end
    end
    }
  }
  r = false
  data.each{ |dat|
    r = r || dat.include?(0)
  }
  break unless r
end
data.each{|d|
  p d
}

２つめ。バックトラック。つまるところ全通り入れてる感じ。どんな問題でも解けるはず。答えが２パターンあるときはどうなるかは不明。

class Sudoku
  def initialize(data)
    @data = data
    solve(0)
  end
  def solve(now)
    if now > 80
      @data.each{ |dat| p dat }
      return
    end
    row, col = now / 9, now % 9
    if @data[row][col] != 0
      solve(now + 1) 
    else
      for i in 1..9
        if check_block(row, col, i) && check_height(row, col, i) && check_width(row, col, i)
          @data[row][col] = i
          solve(now + 1)
          @data[row][col] = 0
        end
      end
    end
  end
  def check_block(row, col, num)
    r, c = row / 3 * 3, col / 3 * 3
    for i in 0..2
      for j in 0..2
        return false if @data[r + i][c + j] == num
      end
    end
    return true
  end
  def check_height(row, col, num)
    for i in 0..8
      return false if @data[i][col] == num
    end
    return true
  end
  def check_width(row, col, num)
    for j in 0..8
      return false if @data[row][j] == num
    end
    return true
  end
end

data =
[ [5,3,0,0,7,0,0,0,0],
[6,0,0,1,9,5,0,0,0],
[0,9,8,0,0,0,0,6,0],
[8,0,0,0,6,0,0,0,3],
[4,0,0,8,0,3,0,0,1],
[7,0,0,0,2,0,0,0,6],
[0,6,0,0,0,0,2,8,0],
[0,0,0,4,1,9,0,0,5],
[0,0,0,0,8,0,0,7,9] ]
Sudoku.new(data)

実行したい場合は、上記をコピーでもしてcodepadに貼り付ければ動くでしょう。違う問題にしたい場合は２次元配列dataをいじって下さい。

これから修正作業などをしていきます。

2つめのプログラムは、このサイトを大いに参考にさせてもらいました。