Ruby で 数独 の３

はじめに

前回の記事で初期値の設定が終わりましたので、判定処理に移ります。

入力例は、wikiの数独の問題例を使用します。

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

初期値設定後の状態

require 'numo/narray'
include Numo

h = w = 9
@banmen = UInt32.zeros(h, w)
@uramen = NArray.cast(Array.new(h){ Array.new(w){ (1..9).to_a } })

def mask(h, w, num)
  return if num == 0
  h2 = (h / 3) * 3
  w2 = (w / 3) * 3
  maskarray = @uramen[h, w, 0..].eq(num)
  @uramen[h, w, 0..] *= maskarray            # 数値の設置用マスク
  maskarray = @uramen[h, 0.., 0..].ne(num)
  @uramen[h, 0.., 0..] *= maskarray          # 行のマスク
  maskarray = @uramen[0.., w, 0..].ne(num)
  @uramen[0.., w, 0..] *= maskarray          # 列のマスク
  maskarray = @uramen[h2..h2+2, w2..w2+2, 0..].ne(num)
  @uramen[h2..h2+2, w2..w2+2, 0..] *= maskarray # ブロックのマスク
end

h.times do |i|
  a = gets.chomp.split('').map(&:to_i)
  a.each_with_index do |x, j|
    @banmen[i, j] = x
    mask(i, j, x)
  end
endi

p @uramen[0.., 4, 0..]

# output
Numo::Int32(view)#shape=[9,9] 
[[0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 3, 4, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 5, 0, 0, 0, 0], # 可能性のある数値が1つだけ
 [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 3, 0, 5, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0]]

ここでは初期値設定後の5列目（ソース上はw=4）を取り出しますが、5行5列のマスの可能性のある数値が5のみとなっています。
よって、このマスに5の数値が入り、それによって、7行5列のマスが3に決まり、次に3行5列のマスが4に決まります。

今回のソース

narray01.rb

require 'numo/narray'
include Numo

def mask(h, w, num)
  h2 = (h / 3) * 3
  w2 = (w / 3) * 3
  @uramen[h, w, 0..] *= @uramen[h, w, 0..].eq(num)
  @uramen[h, 0.., 0..] *= @uramen[h, 0.., 0..].ne(num)
  @uramen[0.., w, 0..] *= @uramen[0.., w, 0..].ne(num)
  @uramen[h2..h2+2, w2..w2+2, 0..] *= @uramen[h2..h2+2, w2..w2+2, 0..].ne(num)
end

def input(h, w)
  h.times do |i|
    a = gets.chomp.split(' ').map(&:to_i)
    a.each_with_index do |x, j|
      @banmen[i, j] = x
      mask(i, j, x) if x != 0
    end
  end
end

def check1(h, w)
  if @uramen[h, w, 0..].ne(0).count_true == 1
    num = @uramen[h, w, 0..].sum
    @banmen[h, w] = num
    mask(h, w, num)
    true
  else
    false
  end
end

def loop_func(h, w)
  loop_flg = true
  while loop_flg
    loop_flg = false
    h.times do |i|
      w.times do |j|
        if @banmen[i, j] == 0
          loop_flg ||= check1(i, j)
        end
      end
    end
  end
end

h = w = 9
@banmen = UInt32.zeros(h, w)
@uramen = NArray.cast(Array.new(h){ Array.new(w){ (1..9).to_a } })
input(h, w)
loop_func(h, w)

p @banmen

# output
Numo::UInt32#shape=[9,9]      
[[5, 3, 4, 6, 7, 8, 9, 1, 2], 
 [6, 7, 2, 1, 9, 5, 3, 4, 8], 
 [1, 9, 8, 3, 4, 2, 5, 6, 7], 
 [8, 5, 9, 7, 6, 1, 4, 2, 3], 
 [4, 2, 6, 8, 5, 3, 7, 9, 1], 
 [7, 1, 3, 9, 2, 4, 8, 5, 6],
 [9, 6, 1, 5, 3, 7, 2, 8, 4],
 [2, 8, 7, 4, 1, 9, 6, 3, 5],
 [3, 4, 5, 2, 8, 6, 1, 7, 9]]

今回のポイントは判定処理１です。

  if @uramen[h, w, 0..].ne(0).count_true == 1

あるh行w列で0ではない数値が1個の場合、そのマスに当てはまる可能性のある数値が1個となりますので、そのマスを埋めることができます。

wikiの数独の問題例は、なんとかcheck1で解くことができました。

としますと、前々記事の試作１号と同機能になりますが、今回のソースはメソッド単位で確認することができますので、見通しがいいと思われます。

まとめ

今回は、判定処理１を追加し、簡単な問題を解きました。