はじめに
@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