More than 3 years have passed since last update.

敷き詰めパズルの解をアルゴリズム「DLX」で探索

Posted at 2020-02-04

以前にアルゴリズム問題として敷き詰めパズルを社内のSlackで出題したのですが、軽く解説できるものではなかったので、記事に纏めることにしました。

地図の空き領域に、その下に列挙したピースを全て収めてください。ピースは回転させてもいいですが、裏返してはいけません。
snippet: puzzle#42
puzzle#42
###########
###.....###
##.###...##
#..#......#
#.........#
##.......##
###.....###
####...####
#####.#####
###########

.......
.#####.
.......
.#.....
.####..
.......
.##....
..###..
.......
.###...
..##...
.......
.#.....
.##....
..##...
.......
.#.....
.###...
..#....
.......
.##....
.##....
.......
.###...
..#....
.......
.##....
..##...
.......

※問題の出典：ニンテンドー3DS内蔵ソフト『すれちがいMii広場』 > 追加コンテンツ『すれちがい迷宮』 > ミニゲーム「パズルボックス」 > No.42

この手の問題を解くのに有用なアルゴリズム「DLX」について、日本語でのわかりやすい解説は既にいくつかあります（→参考リスト）。本記事の特徴は以下くらいですが、理解の足しになれば幸いです。

「1次元の問題」で解法を手を動かして確認します
- 単純な深さ優先探索
- Algorithm X
DLXの実装をミスしにくいように工夫します
最後に、冒頭の形式の問題を解くコードを添付します

1次元の場合で勉強

いきなり冒頭の問題を解くのはきついので、まずは簡略化した1次元の問題で解法を確認します（ピースの回転も不要とします）。

puzzle-1D

#.#.........#..#

#..#.##
#.#..##
##...##

この解のひとつは以下の通りです。どの列にも # がひとつだけある（重複も抜け落ちも無い）ことが確認できます。最下行は各ピースを異なる英文字で表したもので、コンパクトなため以降ではこの表記にします。

puzzle-1D-solution

#.#.........#..# // 設問
: :         :  :
: :     #..#.##: // ピースaを置く位置
:#.#..##    :  : // ピースbを置く位置
: : ##...## :  : // ピースcを置く位置
: :         :  :
#b#bccbbacca#aa# // 各ピースを英文字で表した場合

単純な深さ優先探索

愚直に探索するならピースを片っ端から入れてみる方法があります。ピースがひとつ収まれば、空き領域と残りのピースが少なくなるため、より小さな敷き詰めパズルとして捉えられます。これを再帰的に繰り返して全ピースが埋まれば解が得られます。

探索の様子を以下に示します。ピースを収められなくなったら前のピースをずらしてまた試す、という繰り返しです。

search tree

#.#.........#..#
├── #a#.a.aa....#..#
│   ├── #a#babaabb..#..#
│   └── #a#.a.aab.b.#bb#
├── #.#a..a.aa..#..#
│   └── #.#a.babaabb#..#
├── #.#.a..a.aa.#..#
├── #.#..a..a.aa#..#
│   └── #b#b.abba.aa#..#
└── #.#.....a..a#aa#
    ├── #b#b..bba..a#aa#
    │   └── #b#bccbbacca#aa#
    │       └── // solution
    └── #.#.b.b.abba#aa#

ピースが収まる位置を見つけると言うと難しく感じるかもしれませんが、実際は「左端から全て試す」だけで十分でしょう。それも含めた図を以下に示します。 * で表したところはピースが重なっているため解にならず、次のピースを試すのをスキップすることになります。

深さ優先探索の全容（122行）

search tree (all)

#.#.........#..#
├── *.#a.aa.....#..#
├── #a#.a.aa....#..#
│   ├── *a*.ab*a....#..#
│   ├── #*#ba.**....#..#
│   ├── #a*.*.a*b...#..#
│   ├── #a#babaabb..#..#
│   │   ├── **#ba**abb..#..#
│   │   ├── #**bab**bb..#..#
│   │   ├── #a**aba**b..#..#
│   │   ├── #a#**baa**..#..#
│   │   ├── #a#b**aab*c.#..#
│   │   ├── #a#ba**abbcc#..#
│   │   ├── #a#bab**bb.c*..#
│   │   ├── #a#baba**b..*c.#
│   │   ├── #a#babaa**..#cc#
│   │   └── #a#babaab*c.#.c*
│   ├── #a#.*.*a.bb.#..#
│   ├── #a#.aba*..bb#..#
│   ├── #a#.a.*ab..b*..#
│   ├── #a#.a.a*.b..*b.#
│   ├── #a#.a.aab.b.#bb#
│   │   ├── **#.ac*ab.b.#bb#
│   │   ├── #**.a.**b.b.#bb#
│   │   ├── #a*ca.a**.b.#bb#
│   │   ├── #a#c*.aa*cb.#bb#
│   │   ├── #a#.*caabc*.#bb#
│   │   ├── #a#.ac*ab.*c#bb#
│   │   ├── #a#.a.**b.bc*bb#
│   │   ├── #a#.a.a**.b.**b#
│   │   ├── #a#.a.aa*cb.#**#
│   │   └── #a#.a.aabc*.#b**
│   └── #a#.a.aa.b.b#.b*
├── #.*..a.aa...#..#
├── #.#a..a.aa..#..#
│   ├── *.*a.b*.aa..#..#
│   ├── #b#*..*baa..#..#
│   ├── #.*ab.ab*a..#..#
│   ├── #.#*.ba.**..#..#
│   ├── #.#ab.*.a*b.#..#
│   ├── #.#a.babaabb#..#
│   │   ├── *c#a.**baabb#..#
│   │   ├── #c*a.b**aabb#..#
│   │   ├── #.**.ba**abb#..#
│   │   ├── #.#*cbab**bb#..#
│   │   ├── #.#ac*aba**b#..#
│   │   ├── #.#a.**baa**#..#
│   │   ├── #.#a.b**aab**..#
│   │   ├── #.#a.ba**abb*c.#
│   │   ├── #.#a.bab**bb#cc#
│   │   └── #.#a.baba**b#.c*
│   ├── #.#a..*.*a.b*..#
│   ├── #.#a..aba*..*b.#
│   ├── #.#a..a.*ab.#bb#
│   └── #.#a..a.a*.b#.b*
├── #.#.a..a.aa.#..#
│   ├── *.*.abba.aa.#..#
│   ├── #b#ba.b*.aa.#..#
│   ├── #.*.*..*baa.#..#
│   ├── #.#bab.ab*a.#..#
│   ├── #.#.*.ba.**.#..#
│   ├── #.#.ab.*.a*b#..#
│   ├── #.#.a.babaab*..#
│   ├── #.#.a..*.*a.*b.#
│   ├── #.#.a..aba*.#bb#
│   └── #.#.a..a.*ab#.b*
├── #.#..a..a.aa#..#
│   ├── *.*..*b.a.aa#..#
│   ├── #b#b.abba.aa#..#
│   │   ├── **#b.**ba.aa#..#
│   │   ├── #**b.a**a.aa#..#
│   │   ├── #b**.ab**.aa#..#
│   │   ├── #b#*cabb*caa#..#
│   │   ├── #b#bc*bbac*a#..#
│   │   ├── #b#b.**ba.**#..#
│   │   ├── #b#b.a**a.a**..#
│   │   ├── #b#b.ab**.aa*c.#
│   │   ├── #b#b.abb*caa#cc#
│   │   └── #b#b.abbac*a#.c*
│   ├── #.*.ba.b*.aa#..#
│   ├── #.#b.*..*baa#..#
│   ├── #.#.bab.ab*a#..#
│   ├── #.#..*.ba.**#..#
│   ├── #.#..ab.*.a**..#
│   ├── #.#..a.babaa*b.#
│   ├── #.#..a..*.*a#bb#
│   └── #.#..a..aba*#.b*
├── #.#...a..a.a*..#
├── #.#....a..a.*a.#
├── #.#.....a..a#aa#
│   ├── *.*..bb.a..a#aa#
│   ├── #b#b..bba..a#aa#
│   │   ├── **#b.c*ba..a#aa#
│   │   ├── #**b..**a..a#aa#
│   │   ├── #b**..b**..a#aa#
│   │   ├── #b#*c.bb*c.a#aa#
│   │   ├── #b#bccbbacca#aa#
│   │   │   └── // solution
│   │   ├── #b#b.c*ba.c*#aa#
│   │   ├── #b#b..**a..**aa#
│   │   ├── #b#b..b**..a**a#
│   │   ├── #b#b..bb*c.a#**#
│   │   └── #b#b..bbacca#a**
│   ├── #.*.b..b*..a#aa#
│   ├── #.#b.b..*b.a#aa#
│   ├── #.#.b.b.abba#aa#
│   │   ├── *c#.bc*.abba#aa#
│   │   ├── #c*.b.*cabba#aa#
│   │   ├── #.*cb.bc*bba#aa#
│   │   ├── #.#c*.b.**ba#aa#
│   │   ├── #.#.*cb.a**a#aa#
│   │   ├── #.#.bc*.ab**#aa#
│   │   ├── #.#.b.*cabb**aa#
│   │   ├── #.#.b.bc*bba**a#
│   │   ├── #.#.b.b.**ba#**#
│   │   └── #.#.b.b.a**a#a**
│   ├── #.#..b.ba.b*#aa#
│   ├── #.#...b.*..**aa#
│   ├── #.#....bab.a**a#
│   ├── #.#.....*.ba#**#
│   └── #.#.....ab.*#a**
└── #.#......a..*.a*

コード

この探索をRubyで実装してみます。新しいピースが収まるか判定するためには、既に埋まっている位置を記録するデータ構造が必要です。位置と添字を対応させたboolean配列や整数（＝ビット配列）という手もありますが、今回は埋まっている位置の番号を要素とする集合クラス¹で行きます。 Solver#each_solution が再帰の部分で、再帰呼び出し前は問題を小さくするよう操作し、呼び出し後は復元操作をしています。

require "set"

class Solver
	def initialize(field)
		@field = field
		@filled_set = @field.set
		@pieces = []
		@selected_list = []
	end

	def add_piece(piece)
		@pieces << piece
		self
	end

	def each_solution(&block)
		return to_enum(__method__) unless block

		if @pieces.empty?
			block.call(@selected_list)
			return self
		end

		piece = @pieces.shift
		(0..(@field.width - piece.width)).each do |offset|
			piece_set = piece.set.to_set { |x| x + offset }
			next unless (@filled_set & piece_set).empty?

			@selected_list.push([piece, offset])
			@filled_set += piece_set
			each_solution(&block)
			@filled_set -= piece_set
			@selected_list.pop
		end
		@pieces.unshift(piece)

		self
	end
end

class MapData
	attr_reader :set, :width

	def initialize(str, char = "#")
		@set = str.each_char.with_index.select { |c, i| c == "#" }.to_set { |c, i| i }
		@char = char
		@width = str.length
	end

	def write(base = nil, offset = 0)
		base ||= "." * @width
		@set.each { |i| base[i + offset] = @char }
		base
	end
end

field = MapData.new("#.#.........#..#")
Solver.new(field)
		.add_piece(MapData.new("#..#.##", "a"))
		.add_piece(MapData.new("#.#..##", "b"))
		.add_piece(MapData.new("##...##", "c"))
		.each_solution do |selected_list|
			str = field.write
			selected_list.each { |piece, offset| piece.write(str, offset) }
			puts str
		end

効率

1次元の問題だとあまり気になりませんが、いきなりピースを中央に置いてみるというのは人間なら絶対にしない方法です。「ピースを順番に試す」というのは初期の分岐が増えてしまい、結果として探索木も大きくなりがちです。

もっと賢く、それでいてアルゴリズム（＝コンピューターに指示する手順）としても複雑ではない解法を次で見ていきます。

Algorithm X

計算機科学の分野で有名なクヌース先生が論文の中で述べた、厳密被覆問題の全ての解を探索するアルゴリズムです。名前は「他にいいのが思いつかなかった」²らしいです。

厳密被覆問題への変換

厳密被覆（exact cover）は数学の集合（set）の用語です。専門用語だらけで翻訳に自信はありませんが、Wikipedia英語版には以下のように書いてあります。

In mathematics, given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in S*. One says that each element in X is covered by exactly one subset in S*. An exact cover is a kind of cover.

数学において、集合 X の部分集合の族 S が与えられるとき、厳密被覆とは次の性質を満たす S の部分集合族 S* のことである： X の各要素は S* の1つの部分集合にのみ含まれる。 X の各要素は S* の厳密に1つの部分集合で被覆されると言う。厳密被覆は被覆の一種である。

わかりやすく配列で例を作れば、全体集合 x = [1, 2, 3] およびその部分集合のリスト s = [[1, 2], [1, 3], [2], [2, 3]] があるとき、リストから抽出した s_star = [[1, 3], [2]] は x の要素をちょうどひとつずつ含んでいるため x の厳密被覆です。（厳密被覆になる選び方は1通りとは限りません）

敷き詰めパズルを厳密被覆問題と捉えるには、マス目の位置を要素とする集合に対し、候補となる部分集合としてピースの全配置を用意します。ただし、ピースは1回のみ使うという制約があるため、ピースの種類も集合の要素に追加します。

百聞は一見に如かずということで、実際に例題を変換したものを以下に示します。 | で分けた左16列 [A-P] はマス目、中3列 [a-c] はピースの種類、右1列 [z] は設問であることを表します。（設問を「置き方が1通りのみのピース」と捉えることで、問題サイズが大きくなる代わりに変換を楽にしています）

exact_cover_problem

ABCDEFGHIJKLMNOP|abc|z
______________________
#.#.........#..#|...|# 00 // selected
#..#.##.........|#..|. 10
.#..#.##........|#..|. 11
..#..#.##.......|#..|. 12
...#..#.##......|#..|. 13
....#..#.##.....|#..|. 14
.....#..#.##....|#..|. 15
......#..#.##...|#..|. 16
.......#..#.##..|#..|. 17
........#..#.##.|#..|. 18 // selected
.........#..#.##|#..|. 19
#.#..##.........|.#.|. 20
.#.#..##........|.#.|. 21 // selected
..#.#..##.......|.#.|. 22
...#.#..##......|.#.|. 23
....#.#..##.....|.#.|. 24
.....#.#..##....|.#.|. 25
......#.#..##...|.#.|. 26
.......#.#..##..|.#.|. 27
........#.#..##.|.#.|. 28
.........#.#..##|.#.|. 29
##...##.........|..#|. 30
.##...##........|..#|. 31
..##...##.......|..#|. 32
...##...##......|..#|. 33
....##...##.....|..#|. 34 // selected
.....##...##....|..#|. 35
......##...##...|..#|. 36
.......##...##..|..#|. 37
........##...##.|..#|. 38
.........##...##|..#|. 39

selected と書かれた行のリスト [00, 18, 21, 34] は、全20列をぴったり埋めて互いに重ならないので厳密被覆であり、従って例題の解です。

解法

まずは適当に列を選び、 # を持つ行＝解の候補を抜き取ります。どの列を選んでも全ての解を見つけられますが、 # の個数が少ない列から考えると楽です。
列 z が # 1個なのでこの列にします。抜き出した行は以下の通りです。

x-depth1-step1

ABCDEFGHIJKLMNOP|abc|z
______________________
#.#.........#..#|...|# 00

行は 00 一択なので、これを解の候補に選びます。
候補を選んだら、 # が被っている他の行は解にならないので消します。すると以下のようになります。（選んだ列 z は行を抜き出した時点で役目が終わるので先に消しています。）

x-depth1-step2.1

ABCDEFGHIJKLMNOP|abc
____________________
#.#.........#..#|... 00
____________________
.#..#.##........|#.. 11
...#..#.##......|#.. 13
....#..#.##.....|#.. 14
.....#..#.##....|#.. 15
........#..#.##.|#.. 18
.#.#..##........|.#. 21
...#.#..##......|.#. 23
....#.#..##.....|.#. 24
.....#.#..##....|.#. 25
........#.#..##.|.#. 28
...##...##......|..# 33
....##...##.....|..# 34
.....##...##....|..# 35
........##...##.|..# 38

そして候補に # がある列 [ACMP] 自体も消します。するとより小さな問題の形になります。

x-depth1-step3.1

BDEFGHIJKLNO|abc
________________
#.#.##......|#.. 11
.#..#.##....|#.. 13
..#..#.##...|#.. 14
...#..#.##..|#.. 15
......#..###|#.. 18
##..##......|.#. 21
.#.#..##....|.#. 23
..#.#..##...|.#. 24
...#.#..##..|.#. 25
......#.#.##|.#. 28
.##...##....|..# 33
..##...##...|..# 34
...##...##..|..# 35
......##..##|..# 38

今度は列 B に注目すると解の候補が 11 と 21 の2つあるので、ひとつずつ試す必要があります。

x-depth2-step1

BDEFGHIJKLNO|abc
________________
#.#.##......|#.. 11
##..##......|.#. 21

まずは 11 を候補に選んでみて、同様に # の被る行を消し、 # の列も消します。

x-depth2-step2.1

DEFGHIJKLNO|abc
_______________
.#.##......|#.. 11
_______________
#.#..##....|.#. 23
.....#.#.##|.#. 28
.....##..##|..# 38

x-depth2-step3.1

DFIJKLNO|bc
___________
####....|#. 23
..#.#.##|#. 28
..##..##|.# 38

すると # の無い列が現れました。これはもうどの行を選んでも解にならないということで、探索失敗です。「その列に注目すると解の候補が0個見つかる」と考えてもいいです。

問題を遡り、今度は 21 を候補に選んでみます。

x-depth2-step2.2

DEFGHIJKLNO|abc
_______________
#..##......|.#. 21
_______________
..#..#.##..|#.. 15
.....#..###|#.. 18
.##...##...|..# 34
.....##..##|..# 38

x-depth2-step3.2

EFIJKLNO|ac
___________
.##.##..|#. 15
..#..###|#. 18
##.##...|.# 34
..##..##|.# 38

列 E が # 1個なので、これをもとに行 34 を選びます。

x-depth3-step1

EFIJKLNO|ac
___________
##.##...|.# 34

x-depth3-step2.1

FIJKLNO|ac
__________
#.##...|.# 34
__________
.#..###|#. 18

x-depth3-step3.1

ILNO|a
______
####|# 18

もう目視では答えが見えていますが、きちんと最後まで同じアルゴリズムを適用します。列 I をもとに行 18 を選びます。

x-depth4-step1

ILNO|a
______
####|# 18

x-depth4-step2.1

LNO|a
_____
###|# 18
_____

x-depth4-step3.1

列が無くなったため集合をぴったり埋められたことになり、選択した行 [00, 21, 34, 18] は解です（順不同）。他にも解があるか探すなら、探索を遡って他の候補を選び直せばいいです。今回は候補を選び尽くしたので、解はこの1個のみとわかります。

コード

実装は次節の「DLX」に回します。

効率

探索の順序を図にすると以下のようになります。候補の少ない列（ _ で表現）から攻めることで非常に短く済んでいます。（「単純な深さ優先探索」のときは、列をピースの a → b → c と順序固定で選んでいたことになります）

search tree

................|...|_
└── #_#.........#..#|...|#
    ├── #a#.a.aa..._#..#|a..|#
    └── #b#b_.bb....#..#|.b.|#
        └── #b#bccbb_cc.#..#|.bc|#
            └── #b#bccbbacca#aa#|abc|#
                └── // solution

表や図ではマス目とピースを区切っていますが、厳密被覆問題としては両者に区別はありません。これによって、「このマス目を埋められるピースはこれらだけ」と「このピースを置ける場所はここらだけ」という2通りの絞り込み方が自然とアルゴリズムに入っています。

DLX

見てきたAlgorithm Xは、表を作るのに 0/1 や true/false といった2値を記録できる2次元配列があれば済みます。ただ、深さ優先探索をする場合は探索を遡る方法が必要で、再帰呼び出しの度に現在の表を保存したり新しい表を作ったりすると、かなりメモリを消費してしまいます。

そこで別のデータ構造を使うことが多いです。要となるのはdancing linksと呼ばれる手法で、組み合わせてDLXと呼ばれます。Excelやスプレッドシートにある、行や列の「非表示／再表示」機能を思い浮かべるといいですが、表の一部を隠して小さくした後にまた元に戻すことができるため、新しい表を作る必要がありません。さらに表の2値のうち片方だけ記録すれば済み、今回のようにまばらな表なら効果的です。

dancing links

dancing linksは双方向連結リストの少し変わった使い方です。双方向連結リストからあるノード（要素）を取り除くときは両隣の参照先を変えるわけですが、取り除いたノードは両隣の参照を持っているため再び同じ位置に戻せます。ふつうは取り除いたノードは破棄するはずで、安全のため参照をnullなどにすることもあり、dancing linksの使い方は単純ながら意外です。

DLXでは表を再現するように縦横2次元の双方向連結リストになっていて、さらにリスト終端が無いほうが何かと便利なので循環リストにもなっています。連結リストは配列と異なり間をスキップしてもいいため、Algorithm Xで作った表の # 部分だけをノード化して互いに接続することで、メモリ効率も走査効率も良くなります。表のセル部だけだと扱いにくいので、列を管理するヘッダーノードとそれらを管理するマスターヘッダーノードもあります（行を管理するノードはありません）。図で見ると理解が速いので、参考リストにある元論文か日本語での解説を参照してください。

ノードを取り除いた連結リストはもちろん正常ですので、何段階でもノードの削除・復元ができます。注意事項として、基本的にノードの復元は削除と完全に逆順に行わなければなりません。これを間違えると連結リストの整合性が崩れてしまいます。当たり前のことを言っているようですが、DLXでは「縦横2次元の連結リストで」「ループによる走査を頻繁に行う」ため、1ヶ所でも間違えると原因の特定に苦労します。

コード

DLX::Client クラスから厳密被覆問題の表を操作することにします。単純な深さ優先探索のときの Solver クラスと似た構造です。

表の列は 0 〜 N-1 の番号で区別し、 add_row メソッドの引数に # のある列番号のリストを与えて行を追加することにします
each_solution メソッドが再帰になっています
- 基本ケースは表に列が無いときです
- 選んだ列にある候補行毎に、その候補を抜いた小問題を作って解きます

処理速度よりも安全性・可読性を優先させるため、 Node クラスでは以下の工夫をしています。

データの削除と復元が逆順になることを保証するために、それぞれを別のメソッドとして定義するのではなく、同じメソッドにフラグを与えます
併せて双方向連結リストのリンクも、各方向毎にメンバー変数を用意するのではなく配列に纏めることで、簡単に方向を切り替えられるようにします
- わかりやすく横/縦と順/逆の2次元配列にします → @links = [[right, left], [down, up]]
各ノードは役割毎にクラスを分け、アルゴリズムの実装ミスに気付きやすくします

dlx.rb

module DLX
	class Client
		def initialize(column_size)
			@root = RootNode.new
			@columns = Array.new(column_size) { ColumnNode.new(@root) }
			@selected_cells = []
		end

		def add_row(column_indices, data = nil)
			first_cell = nil
			column_indices.each do |i|
				cell = CellNode.new(first_cell, @columns[i], data)
				first_cell ||= cell
			end
			self
		end

		def each_solution(&block)
			return to_enum(__method__) unless block

			# find a column with the fewest cells
			column = @root.each_column.min_by do |column|
				column.size.nonzero? or break column
			end

			# no columns --> a solution is found
			unless column
				block.call(@selected_cells.map(&:data))
				return self
			end

			# depth-first search (recursive) when column.size > 0
			column.cover_rows(true)
			column.each_cell do |cell|
				@selected_cells.push(cell)
				cell.cover_other_columns_and_rows(true)
				each_solution(&block)
				cell.cover_other_columns_and_rows(false)
				@selected_cells.pop
			end
			column.cover_rows(false)

			self
		end
	end

	module Direction
		HORIZONTAL, VERTICAL = 0, 1
		FORWARD, BACKWARD = 0, 1

		def direction(forward)
			forward ? FORWARD : BACKWARD
		end
	end

	class Node
		include Direction

		attr_reader :links, :column  # links :: [[right, left], [down, up]]
		protected   :links, :column  # column != nil iff self is a cell node

		def initialize(row = nil, column = nil)
			@links = Array.new(2) { Array.new(2, self) }
			@column = column

			Array.new(2).tap do |headers|
				headers[HORIZONTAL] = row
				headers[VERTICAL] = column
			end.each_with_index do |header, dir_hv|
				next unless header
				@links[dir_hv][FORWARD] = header
				@links[dir_hv][BACKWARD] = header.links[dir_hv][BACKWARD]
				cover(false, dir_hv)
			end
		end

		def each(dir_hv, dir_fb, &block)
			return to_enum(__method__, dir_hv, dir_fb) unless block

			node = self
			block.call(node) until (node = node.links[dir_hv][dir_fb]).equal?(self)
			self
		end

		def cover(bool, dir_hv)
			column.update_size(bool) if dir_hv == VERTICAL

			node0, node1 = @links[dir_hv]
			node0.links[dir_hv][1] = bool ? node1 : self
			node1.links[dir_hv][0] = bool ? node0 : self
			self
		end
	end

	class CellNode < Node
		attr_reader :data

		def initialize(row, column, data = nil)
			super(row, column)
			@data = data
		end

		def cover_this_row(bool)
			each(HORIZONTAL, direction(bool)) { |cell| cell.cover(bool, VERTICAL) }
		end

		def cover_other_columns_and_rows(bool)
			each(HORIZONTAL, direction(bool)) { |cell| cell.column.cover_rows(bool) }
		end
	end

	class ColumnNode < Node
		attr_reader :size

		def initialize(root)
			super(root)
			@size = 0
		end

		def each_cell(&block)
			each(VERTICAL, FORWARD, &block)
		end

		def cover_rows(bool)
			cover(bool, HORIZONTAL)
			each(VERTICAL, direction(bool)) { |cell| cell.cover_this_row(bool) }
		end

		def update_size(bool)
			bool ? @size -= 1 : @size += 1
		end
	end

	class RootNode < Node
		def each_column(&block)
			each(HORIZONTAL, FORWARD, &block)
		end
	end

	private_constant :Direction, :Node, :CellNode, :ColumnNode, :RootNode
end

2次元の敷き詰めパズルに適用

2次元でも解き方は同じです。全てのマス目とピース種別（＋設問）を要素とする集合を表の列として用意し、各ピースが可能な配置を表の行としてひたすら列挙します。配置はフィールドの左上から右下まで、加えて回転した場合も必要です。

冒頭の形式の入力をパースして解を列挙するプログラムを示します。（1次元にも回転ありで対応しています）

puzzle_box.rb

require './dlx.rb'

class MapData
	attr_reader :width, :height, :size

	def initialize(lines, char = "#")
		@cells = lines.map { |str| str.chomp.each_char.map { |c| c == "#" } }
		@char = char

		trim_cells
		@width = @cells[0].size
		@height = @cells.size
		@size = @width * @height
	end

	def each_position(field, &block)
		return to_enum(__method__) unless block

		cells, width, height = @cells, @width, @height
		4.times do |rot|
			ary = []
			cells.each_with_index do |row, j|
				row.each_with_index do |cell, i|
					ary.push(i + j * field.width) if cell
				end
			end

			(0..(field.height - height)).each do |j|
				(0..(field.width - width)).each do |i|
					offset = i + j * field.width
					block.call(ary.map { |idx| idx + offset }, [i, j, rot])
				end
			end

			cells, width, height = rotate(cells), height, width
			break if cells == @cells
		end

		self
	end

	def write(*)
		raise NotImplementedError
	end

	private

	def rotate(cells)
		raise NotImplementedError
	end

	def trim_cells
		raise NotImplementedError
	end
end

class FieldData < MapData
	def write
		@cells.map do |row|
			row.map { |cell| cell ? @char : "." }.join
		end
	end

	private

	def rotate(cells)
		cells
	end

	def trim_cells
	end
end

class PieceData < MapData
	def write(base, left, top, rot)
		cells = rot.times.inject(@cells) { |c, _| rotate(c) }
		cells.each.with_index(top) do |row, j|
			row.each.with_index(left) do |cell, i|
				base[j][i] = @char if cell
			end
		end

		base
	end

	private

	def rotate(cells)
		cells.transpose.reverse!
	end

	def trim_cells
		4.times { @cells = rotate(@cells).drop_while(&:none?) }
	end
end


if $0 == __FILE__
	stream = $stdin.each_line
	field = FieldData.new(stream.take_while { |line| !line.start_with?("\n", "\r") })

	chunk_key = field.height > 1 || :_alone  # 2-D mode / 1-D mode
	pieces = stream.chunk { |line| line.include?("#") ? chunk_key : :_separator }
			.zip("a".."z")
			.map { |(_, sub_lines), char| PieceData.new(sub_lines, char) }
	pieces.push(field)

	dlx = DLX::Client.new(field.size + pieces.size)
	pieces.each.with_index(field.size) do |piece, idx|
		piece.each_position(field) do |cell_indices, pos|
			dlx.add_row(cell_indices.push(idx), [piece, pos])
		end
	end

	cnt = 0
	dlx.each_solution do |ary_data|
		cnt += 1
		basemap = field.write
		ary_data.each do |piece, pos|
			piece.write(basemap, *pos) if piece.is_a?(PieceData)
		end
		puts basemap
		puts
	end
	puts "#{cnt} solution#{"s" if cnt != 1} found."
end

参考

元論文
- Knuth, Donald E. (2000), "Dancing links", Millenial Perspectives in Computer Science, pp. 187-214. （arXiv:cs/0011047 [cs.DS]）
Wikipedia英語版
日本語での解説
- Knuth's Algorithm XとDancing Linksの解説 - TopCoderとJ言語と時々F#
- ポリオミノの敷き詰め問題をDancing LinksとKnuth's Algorithm Xを使って解く - matsu7874のブログ
「厳密被覆」という日本語訳を使っているページ
- Knuth先生の『TAOCP 7.2.2.2 Satisfiability』を読む
- 厳密被覆問題の高速な全解列挙法 - NTTグループ（PDF）
ゲーム情報
- すれちがいMii広場（すれちがい迷宮） | ニンテンドー3DS｜任天堂
- すれちがい迷宮/パズルボックス - すれちがいMii広場攻略まとめwiki - アットウィキ

要素の重複が無いことを保証したリストです。とはいえ今回は普通の配列でも事足ります。 ↩
"I will call algorithm X for lack of a better name" ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up