Ruby で 数独 の４

はじめに

前回の記事で簡単な問題が解けるようになりましたので、もう少し複雑な問題に取り組みたいと思います。

入力例は、上記wikiの中段の問題例を使用します。

0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9

前回ソースでの解答

p @banmen

# output
Numo::Int32(view)#shape=[9,9] 
[[0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 3, 0, 8, 5], 
 [0, 0, 1, 0, 2, 0, 0, 0, 0], 
 [0, 0, 0, 5, 0, 7, 0, 0, 0], 
 [0, 0, 4, 0, 0, 0, 1, 0, 0],
 [0, 9, 0, 0, 0, 0, 0, 0, 0],
 [5, 0, 0, 0, 0, 0, 0, 7, 3],
 [0, 0, 2, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 4, 0, 0, 0, 9]]

前回ソースでは、1マスも埋まりませんね。

しかし、数独に慣れた人であれば、7列に1があり8行にも1があることから、9行8列のマスが1に決まることを見つけることができます。

今回の判定方法

p @uramen[6..8, 6..8, 0..]

# output
Numo::Int32(view)#shape=[3,3,9]
[[[0, 2, 0, 4, 0, 6, 0, 8, 0],  
  [0, 0, 0, 0, 0, 0, 0, 0, 0],  
  [0, 0, 0, 0, 0, 0, 0, 0, 0]], 
 [[0, 0, 0, 4, 5, 6, 0, 8, 0],  
  [0, 0, 0, 4, 5, 6, 0, 0, 0],
  [0, 0, 0, 4, 0, 6, 0, 8, 0]],
 [[0, 2, 0, 0, 5, 6, 0, 8, 0],
  [1, 2, 0, 0, 5, 6, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0]]]

右下のブロックの残った数値配列を見ますと、このブロックで1が残っているのは3行2列（全体では9行8列）だけだということが分かります。

今回のソース

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 check2(h, w)
  h *= 3
  w *= 3
  f = false
  9.times do |t|
    if @uramen[h..h+2, w..w+2, t].ne(0).count_true == 1
      pos = @uramen[h..h+2, w..w+2, t].reshape(1, 9).ne(0).to_a[0].index(1)
      num = @uramen[h..h+2, w..w+2, t].reshape(1, 9)[pos]
      h2 = h + pos / 3
      w2 = w + pos % 3
      @banmen[h2, w2] = num
      mask(h2, w2, num)
      f = true
      break
    end
  end
  f
end

def calc1
  return false if @banmen.ne(0).count_true == 0
  calc1_flg = false
  @banmen.eq(0).where.each do |num|
    calc1_flg ||= check1(num / 9, num % 9)
  end
  calc1_flg
end

def calc2
  return false if @banmen.ne(0).count_true == 0
  calc2_flg = false
  set = Hash.new(0)
  @banmen.eq(0).where.each do |num|
    set[[num / 9 / 3, num % 9 % 3]] += 1
  end
  set.each do |k, _|
    calc2_flg ||= check2(*k)
  end
  calc2_flg
end

def solve
  calc1_flg = calc2_flg = true
  while calc1_flg || calc2_flg
    if calc1_flg
      calc1_flg = calc1
      calc2_flg ||= calc1_flg
    elsif calc2_flg
      calc2_flg = calc2
      calc1_flg = calc2_flg
    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)
solve

p @banmen

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

ソースが長くなりましたが、今回のポイントは判定処理２を追加し、判定１->判定２の順でチェックを行っています。

今回の問題例は、なかなか難しい様ですが、ブロック単位での判定をもう一つ追加する予定です。

まとめ

今回は、判定処理２　ブロック単位での残数列処理を追加しました。