Ruby で 数独 の５

はじめに

前回の記事は、下記の入力で、次の出力になったところまででした。

# input
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

# 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]]

今回のロジック

0	0	0	0	0	0	0	0	1
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	4	0	1	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	1	9

例えば、下中央ブロック[[0, 0, 0][0, 1, 0][0, 4, 0]]についてみますと、全体の7行と4列に5があることから、8行6列もしくは9行6列のいずれかに5が入ることが分かります。

これにより、6列の5が下中央ブロックで使用されますので、上中央ブロックの1行5列に5が入ります。
この様に、行と列の双方が確定せずとも、いずれかが確定した場合に、マスを埋めることができるロジックが今回のソースになります。

今回のソース

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 vmask(h, w, num)
  f = false
  if h / 3 != 0 && @uramen[0..2, w, 0..].ne(num).count_true > 0
    f = true
    @uramen[0..2, w, 0..] *= @uramen[0..2, w, 0..].ne(num)
  end
  if h / 3 != 1 && @uramen[3..5, w, 0..].ne(num).count_true > 0
    f = true
    @uramen[3..5, w, 0..] *= @uramen[3..5, w, 0..].ne(num)
  end
  if h / 3 != 2 && @uramen[6..8, w, 0..].ne(num).count_true > 0
    f = true
    @uramen[6..8, w, 0..] *= @uramen[6..8, w, 0..].ne(num)
  end
  f
end

def hmask(h, w, num)
  f = false
  if w / 3 != 0 && @uramen[h, 0..2, 0..].ne(num).count_true > 0
    f = true
    @uramen[h, 0..2, 0..] *= @uramen[h, 0..2, 0..].ne(num) 
  end
  if w / 3 != 1 && @uramen[h, 3..5, 0..].ne(num).count_true > 0
    f = true
    @uramen[h, 3..5, 0..] *= @uramen[h, 3..5, 0..].ne(num) 
  end
  if w / 3 != 2 && @uramen[h, 6..8, 0..].ne(num).count_true > 0
    f = true
    @uramen[h, 6..8, 0..] *= @uramen[h, 6..8, 0..].ne(num) 
  end
  f
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 check3(h, w)
  h1 = h * 3
  w1 = w * 3
  f = false
  9.times do |t|
    if @uramen[h1..h1+2, w1..w1+2, 0..].eq(t + 1).count_true == 2
      b1, b2 = *(@uramen[h1..h1+2, w1..w1+2, 0..].eq(t + 1).where.to_a)
      if (b1 / 9 / 3) == (b2 / 9 / 3)
        f = hmask(h1 + b1 / 9 / 3, w1, t + 1)
      elsif (b1 / 9 % 3) == (b2 / 9 % 3)
        f = vmask(h1, w1 + b1 / 9 % 3, t + 1)
      end
    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 calc3
  calc3_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, _|
    t_flg = check3(*k)
    calc3_flg ||= t_flg
  end
  calc3_flg
end

def solve
  calc1_flg = calc2_flg = calc3_flg = true
  cnt = 0
  while calc1_flg || calc2_flg || calc3_flg
    if calc1_flg
      calc1_flg = calc1
      calc2_flg ||= calc1_flg
      calc3_flg ||= calc1_flg
    elsif calc2_flg
      calc2_flg = calc2
      calc1_flg ||= calc2_flg
      calc3_flg ||= calc2_flg
    elsif calc3_flg
      calc3_flg = calc3
      calc1_flg ||= calc3_flg
      calc2_flg ||= calc3_flg
      cnt += 1
      break if cnt > 10
    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]      
[[9, 8, 7, 6, 5, 4, 3, 2, 1], 
 [2, 4, 6, 1, 7, 3, 9, 8, 5], 
 [3, 5, 1, 9, 2, 8, 7, 4, 6], 
 [1, 2, 8, 5, 3, 7, 6, 9, 4], 
 [6, 3, 4, 8, 9, 2, 1, 5, 7],
 [7, 9, 5, 4, 6, 1, 8, 3, 2],
 [5, 1, 9, 2, 8, 6, 4, 7, 3],
 [4, 7, 2, 3, 1, 9, 5, 6, 8],
 [8, 6, 3, 7, 4, 5, 2, 1, 9]]

コードとしてぁゃしぃところもありますが、難易度 中の問題が解けました。
リファクタリング希望

まとめ

今回は、判定処理３　ブロック単位でのマスク処理を追加し、難易度 中の問題を解きました。