Ruby で数独

はじめに

@HMMNRST さんが面白そうな記事を投稿されました。
NArrayによる数独の解法（総当たり）の実装／数独を4次元配列と見た場合の様子

NArray や numpy に興味はあるものの取り組んだことは無いので、少しずつ学習したいと思います。

Matrix

まずは、Ruby の標準モジュールの Matrix を使用します。

require.rb

require 'matrix'

new.rb

a = Matrix.zero(r * c)

Matrix.zero(dim)で、初期値0 dim行dim列の行列を生成します。

row.rb

  b = (1..r * c).to_a - a.row(i).to_a

Matrix.row(index)でindex行のベクターを取り出します。
ここでは、配列に変換して使用しています。

column.rb

    d = b - a.column(j).to_a

Matrix.column(index)でindex列のベクターを取り出します。
二次元配列の様にtransposeする必要がなく便利です。

minor.rb

    e = d - a.minor((i / r) * r, r, (j / c) * c, c).to_a.flatten

Matrix.minor(rindex, rsize, cindex, csize)で部分行列を取り出します。

試作１号

ruby.rb

require 'matrix'
r, c = gets.split.map(&:to_i)
a = Matrix.zero(r * c)
(r * c).times do |i|
  b = gets.split.map(&:to_i)
  (r * c).times do |j|
    a[i, j] = b[j]
  end
end
que = []
(r * c).times do |i|
  b = (1..r * c).to_a - a.row(i).to_a
  (r * c).times do |j|
    d = b - a.column(j).to_a
    e = d - a.minor((i / r) * r, r, (j / c) * c, c).to_a.flatten
    if a[i, j] == 0
      if e.size == 1
        a[i, j] = e[0]
      elsif e.size > 1
        que << [i, j, e]
      end
    end
  end
end
while que.size > 0
  p que.size
  i, j, e = que.shift
  f = e - a.row(i).to_a - a.column(j).to_a - a.minor((i / r) * r, r, (j / c) * c, c).to_a.flatten
  if f.size == 1
    a[i, j] = f[0]
  elsif f.size > 1
    que << [i, j, f]
  end
end
(r * c).times do |i|
  puts a.row(i).to_a.join(' ')
end

dif.rb

    b = (1..r * c).to_a - a.row(i).to_a
    d = b - a.column(j).to_a
    e = d - a.minor((i / r) * r, r, (j / c) * c, 

順に、行で使用されていない数字、列で使用されていない数字、ブロックで使用されていない数字の差分を取得しています。

@HMMNRST さんの 例1 と 例2 は正常に動作することを確認しました。

例3 例4 は一向にキューが減らないです。
別のロジックの追加が必要です。

まとめ

• 数独の簡単な問題 を解いた
• Ruby に詳しくなった

参照したサイト
NArrayによる数独の解法（総当たり）の実装／数独を4次元配列と見た場合の様子
class Matrix
Matrix