『AtCoderでRubyの数値配列 Numo::NArray を利用…する前の基礎勉強』の続きみたいなもの。NArrayにもっと慣れるため、数独（ナンバープレース、ナンプレ）の単純な解法に使ってみる。
※数独を効率よく解きたいわけではないので注意
元々はNArrayを使うだけの予定だったが、2次元配列より4次元配列のほうが数学的に面白そうだったため、その話も追加している。
問題の入力形式
AtCoder的な形にしておく。
- 1行目はブロック内の行数 R と列数 C
- 2 ≦ R, C ≦ 5
- 数独全体の大きさは、 N = R×C として N×N
- （※本記事の解法は、標準的な N = 3×3 でも膨大な時間がかかる場合がある）
- 以降の N = R×C 行は各マスの値 Ai,j
- 1 ≦ i, j ≦ N
- 0 ≦ Ai,j ≦ N 、ただし 0 は空白マスを表す
- 数独の解が1個であることを保証する
R C
A_{1,1} ⋯ A_{1,N}
⋮
A_{N,1} ⋯ A_{N,N}
出力はお好みで。
例1
出典：ミニ ナンプレ（数字ロジックパズル）６✕６マス｜ちびむすドリル【幼児の学習素材館】
2 3
2 0 0 0 0 3
4 0 0 5 2 1
3 0 6 0 0 0
0 0 0 3 0 2
6 3 4 0 0 5
5 0 0 0 0 6
ブロックが 2×3 の小さなバージョン。
例2
出典：Sudoku solving algorithms - Wikipedia
3 3
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
普通の数独はブロックが 3×3 。
例3
出典：Sudoku solving algorithms - Wikipedia
3 3
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
今回の解法の天敵。手元では終わらず諦めた。
例4
出典：Glossary of Sudoku - Wikipedia
（英文字は2桁の整数に変換した）
25×25 Sudoku the Giant.
5 5
19 4 23 0 0 0 0 0 0 0 0 12 0 11 2 22 25 0 0 0 14 0 17 0 24
17 13 0 24 0 6 0 0 0 0 0 8 0 0 1 10 11 16 12 14 5 21 0 0 15
0 8 0 18 0 10 20 24 3 11 22 0 21 15 5 1 0 17 7 0 12 0 0 6 19
11 0 0 10 0 0 0 16 21 0 23 19 0 17 6 8 0 0 0 0 13 22 1 2 7
0 21 1 5 0 22 0 4 2 23 0 0 25 0 0 0 13 19 0 6 9 11 8 10 0
15 17 0 23 24 4 5 0 0 0 13 0 0 0 22 19 0 18 0 0 6 0 9 12 8
5 0 0 0 22 0 6 15 0 0 0 0 0 0 20 9 10 12 0 0 0 1 0 21 0
0 1 0 0 0 18 2 0 19 20 0 7 0 10 11 0 0 0 0 23 0 17 24 0 0
6 10 0 14 16 9 0 0 12 0 21 0 0 24 0 2 5 7 1 8 15 0 19 20 22
18 19 0 0 20 13 21 0 0 0 0 1 0 0 0 14 16 0 3 17 0 0 0 11 5
22 5 3 21 7 23 10 12 18 0 0 15 11 0 16 0 0 20 14 0 0 24 2 19 17
0 15 0 0 0 11 16 0 24 0 1 9 0 0 14 0 7 0 21 5 20 13 6 0 0
20 0 0 0 0 0 0 1 0 0 5 24 17 0 0 6 0 0 9 0 23 0 0 0 0
13 16 0 0 0 0 19 5 17 3 0 0 20 25 0 11 0 0 23 0 1 12 14 8 0
1 0 12 0 11 7 15 6 20 13 2 0 22 0 23 0 0 4 0 19 0 0 0 5 9
21 18 0 0 5 0 0 10 14 0 11 0 1 7 0 15 0 23 19 0 0 0 12 0 13
8 6 10 17 0 0 0 0 0 12 24 0 0 0 0 0 18 0 0 0 0 15 5 7 0
3 12 11 1 0 0 0 21 0 15 9 0 0 0 10 4 0 0 0 7 8 2 23 0 6
0 0 14 16 0 0 7 0 1 5 12 0 0 21 0 0 2 0 0 0 17 0 0 0 20
0 0 15 0 0 24 0 0 0 0 0 17 19 0 4 12 0 0 0 13 3 14 18 1 21
0 23 6 15 17 0 0 0 0 22 14 20 3 0 0 0 9 25 0 0 0 0 16 24 2
16 24 5 3 12 25 0 14 8 0 15 0 6 0 0 0 0 0 0 4 11 19 7 0 18
0 9 18 13 8 21 11 0 6 0 16 0 0 4 17 5 19 0 0 12 10 0 15 0 1
0 0 19 0 1 16 0 0 15 7 0 0 0 5 9 23 21 0 2 10 0 6 0 0 12
0 11 0 0 0 12 0 0 9 0 0 0 10 0 0 16 0 8 0 0 0 0 20 13 14
純粋に大きい。これも手元では終わらなかった。
コード
単純に左上のマスからあり得る数字を入れていき、もし制約により数字を入れられなくなったらバックトラックする（例2の出典にあるアニメーションを参照）。 #solve を再帰関数にして実装した。
注意：
- 問題の正当性はチェックしていない：与えられた数字同士が既に制約違反を起こしていても気付かない
- 解が複数ある場合には全て出力する（解が見つかっても探索を続ける）
-
#each_solutionに与えるブロック内でbreakすれば打ち切れる
-
require 'numo/narray'
class Sudoku
BLANK = 0
def initialize(io = $stdin)
@r, @c = io.gets.split.map!(&:to_i)
@n = @r * @c
@board = Numo::Int8.parse(io.take(@n).join).reshape!(@c, @r, @r, @c)
@given = @board.ne(BLANK).freeze
@elements = [*1..@n].freeze
end
def each_solution(&block)
solve(0, &block)
self
end
private
# 盤面のkマス目（左上が0）に値を入れて次のマスに進む再帰関数
def solve(k, &block)
# 全マスが埋まっていたら、解をブロックに渡す
if k == @n * @n
yield @board.copy
return
end
# 値の与えられているマスなら、そのまま次のマスに進む
if @given[k] != 0
solve(k + 1, &block)
return
end
# 空白マスなら、現時点で可能な数をひとつ入れて進む
# 再帰が戻ってきたら次の候補を入れて進む…を繰り返す
candidates_at(k).each do |i|
@board[k] = i
solve(k + 1, &block)
end
@board[k] = BLANK # 空白に戻す
end
def candidates_at(k)
# 配列の添字を1次元 [k] から多次元 [i3, i2, i1, i0] に直す
k, i0 = k.divmod(@c)
k, i1 = k.divmod(@r)
k, i2 = k.divmod(@r)
k, i3 = k.divmod(@c)
row = @board[i3, i2, true, true].flatten.to_a
column = @board[true, true, i1, i0].flatten.to_a
block = @board[i3, true, i1, true].flatten.to_a
@elements - row - column - block
end
end
if $0 == __FILE__
sudoku = Sudoku.new
sudoku.each_solution do |board|
n = Integer.sqrt(board.size)
p board.reshape!(n, n)
end
end
NArrayの活用方法
多次元配列への1次元アクセス
盤面を配列で表すことを考えたとき、左上から順に走査するなら連続した1次元配列のほうが楽だが、行・列・ブロックのグループを抜き出すなら多次元配列のほうが直感的になる。どちらを選ぶかで実装方法が多少変わる。
NArrayは多次元配列であっても1次元配列のように参照・更新できるので、多次元配列を選んでおいて問題ない。
配列のスライス
Arrayによる多次元配列（配列の配列）で盤面を表した場合、ある行を抽出するのは楽だが、列やブロックを抽出するには異なる書き方が必要になる。
NArrayは多次元配列の操作を多数サポートしていて、配列の断面や範囲などを抜き出すのは何次元であっても同じようにできる。
条件に一致する要素の一括選択
今回の実装では「問題として与えられた数字のマス目」を記憶しておく必要がある。NArrayは配列に対して比較演算子（または相当するメソッド）を用いて、Rubyレベルでループを回さずに各要素の真偽を判定できる。
なお、真偽値の配列である Numo::Bit の要素は 0 か 1 でありRubyにとっては両方とも真なので、要素を参照しただけでは条件式に使えない。
4次元配列の利用
数独は N×N マスで出題されるので、普通に考えれば2次元配列が適している。
わざわざ4次元配列を利用したのは数独のブロックの扱いが簡単になると考えたから。2次元配列だとブロックの抽出には範囲指定が必要になる（これもNArrayなら難しくないが）。
# @board.shape == [@n, @n] の場合
def candidates_at(k)
i, j = k.divmod(@n)
ii = i / @r * @r
jj = j / @c * @c
row = @board[i, true].to_a
column = @board[true, j].to_a
block = @board[ii...(ii+@r), jj...(jj+@c)].flatten.to_a
@elements - row - column - block
end
一方で4次元配列なら、先に示したように数値指定で済む。行・列と同様の構造になっていて綺麗にも感じる。
またNArrayではないが、数独を出力する際にブロック単位の整形を加えるときにも役立つ。配列が既にブロック単位で区切られているため、要素のインデックスを数えずに区切り文字列を追加できる。
sudoku.each_solution do |board|
n = Integer.sqrt(board.size)
num_digit = Math.log10(n).to_i + 1
ary = board.format_to_a("%#{num_digit}d")
sep = nil
ary.map! do |ary2|
ary2.map! do |ary1|
ary1.map! do |cells|
" " + cells.join(" ") + " "
end
"|" + ary1.join("|") + "|" + "\n"
end
sep ||= ary2[0].tr("|\n 0-9", "+\n-")
ary2.join
end
puts sep, ary.join(sep), sep
end
おまけ：4次元配列で見えるもの
数独は「ある N マスのグループ内で同じ値が無いこと」という制約に基づき、そのグループは基本的に「同じ行」・「同じ列」・「同じブロック」の3通りで構成される。実際に #candidates_at で4次元配列 @board から2次元断面をとっているのは、全て大きさ N = R×C になっている。
ところで、大きさ N = R×C の2次元断面はもうひとつ作れる ： @board[true, i2, true, i0] 。これが表しているのは**「各ブロックの同じ位置」というグループ分け**であり、基本的な数独であればどのサイズでもこのグループの制約を自然に追加できる。（ただし実際に出題されると、同じグループのマスが盤面全体に分散しているので人間には解きにくいと思う。）
この手の問題が実際にあるか探したら、 "disjoint groups" というバリエーション名で出てきた。
http://www.menneske.no/sudoku/dg/2x3/eng/さらに R = C なら2次元断面を2通り追加でき（計6通り）、 "4 dimensional" や "hypercube" という名前になっていた。数独を正方形 9×9 と見るというより4次元超立方体 3×3×3×3 と見て、あらゆる2次元断面 3×3 で 1～9 の数字が重ならないという制約。
http://forum.enjoysudoku.com/su-doku-s-maths-t44-390.html#p11216
また、数独は行と列を入れ替えて（転置して）も必ず問題として成り立つが、行or列とブロックを入れ替えることはできるだろうか？ これは4次元配列で見ると制約に非対称性があり成り立たないことがわかる。「各ブロックの同じ位置」というグループ分けを有効にしたとき初めて各グループ分けが対等になり入れ替え可能となる。