数理解析研究所講究録 1426 巻 2005 年 147-152

147
一般化ぷよぷよの NP 完全性
松金輝久 (Teruhisa MATSUKANE)
武永 康彦 (Yasuhiko TAKENAGA)

電気通信大学 (The University of Electro-Communications)

1

AO

はじめに

$\downarrow$

計算理論において、 ある問題を解くためにかかる時聞量や領域量$\mathrm{O}$

口口$\mathrm{O}\mathrm{O}\triangle \mathrm{O}\text{口}$$\mathrm{x}$o ロ ooO口$\triangle\triangle$$\triangle\triangle$$5\mathrm{J}$OAO$0\text{口}\mathrm{o}\mathrm{o}\mathrm{o}\text{口}\ovalbox{\tt\small REJECT}$$\cross \mathrm{O}\triangle \mathrm{O}$を計算し、その複雑さを調べるのは重要なことである。 扱われる問題は数多くあるが、パズルやゲームもその中の一つである。 本論文
ではぶよぶよ [4,というゲームを取り上げて、 その複雑さを調べ$0\text{口^{}\triangle}\ovalbox{\tt\small REJECT}^{\ovalbox{\tt\small REJECT}_{\mathrm{r}}}\mathrm{O}\text{口^{}\triangle})\zeta 0^{\text{口}}$$\mathrm{X}\mathrm{Q}\text{口}\triangle\triangle$(a)$\mathrm{x}\mathrm{O}\square \triangle\triangle$(b)$(\Phi\rangle$

た。 ぶよぶよとは、 日本では広く知られるアクションパズルゲーム
である。

$\text{口}\triangle$$\mathrm{o}$本論文では、 一般化ぶよぶよにおいて 「入力の初期盤面とピー$\mathrm{o}$ス列から連鎖可能であるか」 を判定する連鎖数判定問題を扱う。

$k$

一般化ぶよぶよに適切な問題を与えると、 それが$\mathrm{N}\mathrm{P}$$\mathrm{x}\mathrm{O}$

に属するこ

ロ
口

を行う。 これは、 同じくコンピュータゲームとして広く知られる、$\mathrm{N}\mathrm{P}$$\triangle$$\mathrm{x}$.

$\mathrm{O}$$\ovalbox{\tt\small REJECT}_{\mathrm{A}}^{\mathrm{A}}$$\triangle\triangle$$\mathrm{x}\mathrm{O}$(d)とが明らかに成り立つことを利用して、 3NPAR 丁 ITIoN からの帰着
テトリスの

O口
O臼

口

$\cross \mathrm{O}\triangle$

口口$\triangle$$\triangle\triangle$(e)$\text{図}1$

完全性を示す手法 [1] を取り入れている。

一般化ぶ \ddagger ぶ $x$ の操作の例

2 一般化ぶよぶよ
21 一般化ぶよぶよの定義
まず、ぶよぶよを以下のルールにしたがって、 1 人で行う組合せ
パズルとして定義する。
ルール

1. 盤面は格子状の正芳形のマスに区切られ、各マスに右方向をこのようなぶよぶよを、一般化ぶよぶよと呼ぶ。 その操作の仕方
を図 1 の例に示す。 以下、 ぶよを記号$\mathrm{O}$,$\triangle$$\mathrm{x},$, 口で表すことにする。
ルール 7. の性質を利用して、 他のぶよが消えて下に空白ができたときに、また同色のぶよが 4 姻以上隣接し消えることがある。 こっ座標平面である。 $y=0$ を地面としてサイズの制限は考えの現象を違鎧という。 連鎖はゲームとしてのぶよぶよにおいて非常に重要な性質である。 本論文ではこの連鎖について詳しく扱っない。 盤面の一番左下を座標 $(1, 1)$ とする。

ている。

$x_{\backslash }$

上方向を

$y$

座標として $(x, y)(y>0)$ に整数の座標を持

2. 盤面には「ぶよ』 と呼ばれるブロックを盤面のマスに置くことができる。 ぶよには 「色ぶよ」 と「おじやまぶよ の 2 種$\sim$

ぶよぶよでは、通常のぶよとは性質の異なるおじやまぶよが現れる。 以下、 おじやまぶよを記号$\bullet$で表すことにする。

これは、 ルール 2. のように縦、横に 4 個以上連結しても消える類がある。

3. 色ぶよ (以下、 単に 「ぶよ」 と呼ぶ) には 種類の色があり、ことはない。 その代わり、 あるぶよが消えたときにおじゃまぶよが同色のぶよが縦、 横に 4 個以上連結すると消える。
4. あるぶよが消えたときにおじゃまぶよが隣接していれば、そ隣接していれば、 そのおじやまぶよは消える。

$a$

22 蓮鎖敬判定問題
一般化ぶよぶよにおける連鎖数判定問題を以下のように定嚢のおじやまぶよは消える。

5. ピースは 2 個のぶよがつながったものであり、 入力としてピース列が与えられる、

6. ピースは 1 つずつ順に盤面の十分高いところがら表れ、 プ

..
.

する。
入力

初期盤面: $B$ , ピースの列: $P$ , 正整数:

出力

$B,$ $P$

に対して

$k$

$k$

連鎖することが可能か ?

レイヤーはそれを次の順に操作する。
ビースに対して回転
ビースに対して$x$$(0^{\mathrm{o}}, 90^{\text{。}}, 180^{o}, 270^{\text{。}})$

を行う

軸方向の移動を行う

ピースを落下させる

7. 下に空白ができたぶよは、他のぶよか地面に接触するまで落下する。

定理 1 連鎖数判定問題

3$\epsilon \mathrm{N}\mathrm{P}$

帰着とインスタンス
連鎖数判定問題のの帰着により行う。
入力

正整数$a_{1},$

完全性の証明は、 3-PARTITION [31 から-PARTITION の定義は以下の通りであ$\mathrm{N}\mathrm{P}$$3$$\ldots,$ $a_{3s},$$\text{る_{}\circ}^{\backslash }$

$T$

148
$\bullet\bullet\bullet$$\bullet\bullet\bullet\bullet\bullet\bullet$

ム口$\epsilon_{\bullet}^{\bullet}\bullet\bullet$$\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet$$\bullet\bullet\bullet\bullet\ldots\bullet\bullet\bullet\bullet$$\bullet\bullet\bullet\bullet$$\bullet\bullet$:$\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet f24T*156$$\bullet\bullet\bullet\bullet\bullet\bullet$$\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet$$\mathrm{F}\mathrm{E}$$\epsilon_{\bullet\bullet\bullet}^{\bullet\bullet\bullet}$$\bullet\bullet$$\bullet\bullet$$\square$ロ口$\mathrm{O}$

xo

xoxo

$\triangle \mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{O}\mathrm{X}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{X}$$\mathrm{X}$$\bullet\bullet\bullet\bullet \mathrm{o}\mathrm{x}\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\triangle \mathrm{O}\mathrm{x}\mathrm{O}\triangle\square \bullet\bullet\square \cross 0\cross\square \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{x}0\mathrm{x}$$\bullet\bullet \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{O}$xoxo
xoxo oxox$\square \mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}O\mathrm{x}\mathrm{O}$$\mathrm{x}\mathrm{O}$...

$\mathrm{O}\mathrm{x}$$\bullet\bullet\bullet\bullet \mathrm{O}\mathrm{x}\mathrm{o}\square \mathrm{o}\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{o}\square \mathrm{x}\mathrm{o}\mathrm{x}\triangle \mathrm{x}\mathrm{O}\mathrm{x}\square \mathrm{x}\mathrm{O}\mathrm{x}\square$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\bullet\bullet \mathrm{x}\mathrm{o}\mathrm{x}\mathrm{O}$$\mathrm{I}$$\mathrm{o}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{x}\mathrm{O}\ldots \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{o}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{o}\mathrm{x}\circ \mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\circ \mathrm{x}\mathrm{O}$$\square \mathrm{O}\mathrm{x}\mathrm{O}\square \mathrm{o}\mathrm{o}\mathrm{x}\triangle \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{x}0\mathrm{x}$$\bullet\bullet\bullet\bullet$$\bullet\bullet$$\mathrm{O}\mathrm{x}\mathrm{O}\square$$\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{x}$ox$\cross \mathrm{O}$$\cross0$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$口$\mathrm{x}\mathrm{O}$$\mathrm{O}\mathrm{x}$$0_{\mathrm{X}}$$\square \mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{O}\cross$$\mathrm{o}\mathrm{x}\mathrm{o}\square \mathrm{o}\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}\square \mathrm{x}\mathrm{O}\mathrm{x}\square |$$\mathrm{x}\mathrm{O}\triangle\triangle \mathfrak{g}\mathrm{T}+52$$\mathrm{Q}\mathrm{x}\mathrm{o}\triangle$$\mathrm{O}\mathrm{x}$$\mathrm{o}\mathrm{o}\mathrm{x}\mathrm{o}\mathrm{o}\mathrm{o}\cross \mathrm{o}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{o}\cross 0\triangle \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}_{\mathrm{O}\mathrm{x}\mathrm{O}\ldots \mathrm{x}\mathrm{O}}\mathrm{o}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{o}\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{o}\triangle \mathrm{O}\mathrm{x}\mathrm{o}\mathrm{x}..0)\zeta\circ \mathrm{x}\bullet \mathrm{o}\mathrm{x}\mathrm{o}\mathrm{x}\bullet \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\bullet\triangle \mathrm{o}\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{i}$

図2

.

鐵力

$\frac{T}{4}$

く $a:< \frac{\tau}{2}(1\leq t\leq d3s)$を$s$らの全てについて$3$-PARTITION は,の両方をみたす。

$\sum_{i=1}^{3s}a_{i}=sT$$\{a_{1}, \ldots, a_{3s}\}$

定理 2

初期盤面

個の部分集合となるか$\sum_{\emptyset:^{\epsilon A_{\mathrm{j}}}}a:=T$$\mathrm{N}\mathrm{P}$

完全に分割し、それ$\ldots,A_{s}$$A_{1},$$\varphi$$[2]_{\text{。}}$

31 運鎖数判定図題のインスタンス

図33-PARTITION から次のように連鎖数判定問題のインスタンスに

初期盤面の繰り返し部分帰着する。
初期盤面の構成

初期盤面を図 2 に示す。

$\mathrm{i}$

初期盤面の大半は繰り返し部分で構成されており、それを図 3 に.

示す。 見方は以下の通りである。

行 $8T+67\sim 32T+208$ : 列 1 にパーツ

..

at or
$\mathrm{O}$$\triangle$$\triangle$$\mathrm{O}$$\mathrm{x}$$\mathrm{O}$$\mathrm{O}$$\mathrm{x}$$\mathrm{O}$$\mathrm{O}$$\triangle$$\triangle$$\mathrm{O}$$\triangle$$\mathrm{O}$$\mathrm{O}$$\mathrm{x}$$\mathrm{O}$$\triangle$$\mathrm{x}$$\mathrm{O}$$\mathrm{x}$$\mathrm{O}$$\mathrm{O}$$\mathrm{x}$$\mathrm{O}$$\mathrm{x}$$\mathrm{x}$$\mathrm{x}$$\mathrm{O}$$\mathrm{O}$$\mathrm{x}$$\mathrm{O}$$\mathrm{x}$が繰り返さ$\mathrm{F}$

笛 rm

れる

.
.

$\mathrm{t}\mathrm{i}$$\triangle$

filler

列 1,2:-$\mathrm{B},$ni$\mathrm{x}$-行 $8T+49\sim 8T+56$ : パーツ A-

行 $\sim 8T+48$ : パーツ$\mathrm{B},$$\mathrm{B}$$\mathrm{x}$$\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}$0rr$\mathrm{x}$$\mathrm{O}$$\triangle$$\mathrm{O}$$\mathrm{O}$$\mathrm{x}$$\mathrm{O}$$\mathrm{x}$$\mathrm{O}$$\mathrm{O}$’ が交互に繰り返される

列 $3\sim 6s+2$-

行 $8T+63\sim 32T+2\mathrm{O}\mathrm{S}$: パーツ-

行 $5\sim \mathrm{S}T+52$ : パーツ-

行 1\sim 4: パーツ C’ の繰り返し$\mathrm{C}$

図4$\mathrm{G}$の繰り返し

夕 」 $6s+3,6s+4$$1$$\mathrm{B}$-

行 $8T+53\sim 32T+208$ : パーツ-

行 $5\sim 8T+52$ : パーツ-

行 1\sim 4: パーツ’ および$\mathrm{D},$$\mathrm{D}$$\mathrm{D},$$\mathrm{D}$

が奇数:

$T$

が偶数:

$\mathrm{B},$の繰り返し’ が交互に繰り返されるピースの構成$\mathrm{B}$$\ldots,$$\mathrm{B},$$\mathrm{B}’$.

および, . . , ’ および$\mathrm{B}$$\mathrm{D},$$\mathrm{D}$$\mathrm{D}’,$$\ldots,$$\mathrm{D},$$\mathrm{D}$$\mathrm{D}’,$’$\ldots,$となる。 ただし、 いずれにしても隣接する他のパーツに影響は.
..

行 $4j+1\sim 4j+4$ の集まりをそれぞれ belt と呼び、 後にぶよが連鎖で消える単位を表す。
$6\mathrm{F}+6$

以下に入力のピースの列を示す。 まず、 initiator,

以下が $3s$ 組、 この順で表れる

initiator, filier) $(S,$
Key:
Tsum : 口$\dot{\Delta}$スの$a_{\dot{\mathrm{t}}}$$\mathrm{x}a_{\dot{\mathrm{t}}}$, term inator$\trianglerightarrow \mathrm{x}s$$0$$a_{\dot{\tau}}$

回繰り返されるのは、 3-PARTITION のインスタンに対応しており、$\sum_{a:\epsilon A_{j}}a_{\dot{\mathrm{t}}}=T$となるとき、 buciet がちょうど満たされる。

の空の座標の集まりをそれぞれ$A_{s}$$\ldots,$

ffller, terminator を図 4 のように定義する.

Filler がない。

また、 列 $6i+5$ および$A_{1},$$\mathrm{E}$’ の繰り返しにおいて、 $T$ の偶奇によってそ$\mathrm{B}’,$

bucket と呼び、 後にぶよを置く際の議論で用いる。 この bucketには個あり、 3-PARTITION のインスタンスの分割
対応している。 さらに、 bucket にある行 $52+8T$ 以下の空の座標の総和のことを、 bucket の容積と呼ぶ。
$s$$\mathrm{H}$の終端が異なる。 すなわち、
$T$

ビースの列

の繰り返し

また、 $k=20sT+58s+8T+53$ とする。

149
補題 3 連鎖数判定問題のサイズは、 8, $T$ の多項式で表される。

$\circ[mathring]_{\mathrm{K}}$$\circ\circ \mathrm{x}$$8\mathrm{x}$$\circ\circ \mathrm{x}$$8\mathrm{x}\mathrm{x}$$\circ\circ \mathrm{x}\mathrm{x}$$8\mathrm{K}\mathrm{K}$$8\mathrm{K}$$8\mathrm{x}$$\circ \mathrm{x}\mathrm{x}$$\circ \mathrm{x}\mathrm{x}$$\circ \mathrm{x}\mathrm{x}$$\circ \mathrm{x}\mathrm{x}$$\circ \mathrm{K}\mathrm{X}$$\circ \mathrm{Q}\mathrm{x}\mathrm{x}$$\circ\circ \mathrm{X}\mathrm{K}$$8\mathrm{x}\not\in_{0}^{\mathrm{x}}\mathrm{x}$$\circ \mathrm{x}\mathrm{x}$$\mathrm{o}\mathrm{x}\circ \mathrm{x}O\mathrm{x}\mathrm{x}\mathrm{x}8^{[mathring]_{\mathrm{X}}}\mathrm{x}8$$[mathring]_{\circ \mathrm{x}\mathrm{x}}$$8\mathrm{x}\mathrm{x}$$[mathring]_{\circ \mathrm{x}\mathrm{x}}$$8\mathrm{x}\mathrm{x}$$[mathring]_{\circ \mathrm{x}\mathrm{x}}$$\circ\circ \mathrm{x}\mathrm{x}$$8\mathrm{x}\mathrm{x}$$[mathring]_{\circ \mathrm{x}\mathrm{x}}$$8\mathrm{x}\mathrm{x}8_{\mathrm{x}}^{\mathrm{O}}\mathrm{x}\mathrm{O}\mathrm{K}$$\circ \mathrm{x}[mathring]_{\mathrm{x}}$$[mathring]_{\circ \mathrm{x}\mathrm{x}}$$8\mathrm{x}\mathrm{x}$$8\mathrm{x}\mathrm{x}$$8\mathrm{K}\mathrm{x}$4 完全性$[mathring]_{\circ \mathrm{x}\mathrm{x}}$$8\mathrm{K}\mathrm{x}$本章で示した連鎖数判定問題のインスタンスが、 3-PARTITION
からの帰着として正しいことを、 本章、 次章にわたって示す。

$[mathring]_{\circ \mathrm{x}\mathrm{x}}$$\mathrm{o}_{\mathrm{X}}\mathrm{o}\mathrm{x}$$\circ[mathring]_{\mathrm{X}}\mathrm{K}$

1 8$8\mathrm{K}\mathrm{x}$$\circ \mathrm{x}\mathrm{x}$$\circ \mathrm{X}\mathrm{K}$$8\mathrm{x}$$[mathring]_{\circ}\mathrm{x}$連鎖の性質上、 入力のぶよの総数を 4 で割った商が得られる最大連鎖数の上界となる。 したがって、連鎖数判定問題では次のよう$\mathrm{o}\mathrm{o}$$\mathrm{x}$

$($

..

$0$

$\mathrm{K}$$\mathrm{x}\mathrm{x}$$\circ \mathrm{o}$$\circ$$\mathrm{x}$$\circ \mathrm{x}\mathrm{x}$$[mathring]_{\mathrm{x}\mathrm{x}}$$8\mathrm{x}$$8\mathrm{x}$$\circ$$\mathrm{x}$$\circ$$\circ\circ \mathrm{X}\mathrm{K}$$8\mathrm{K}\mathrm{x}$$\mathrm{x}$な性質がただちに導かれる。

8$0$$\mathrm{x}$$\circ\circ \mathrm{X}\mathrm{x}$$\circ\circ \mathrm{x}\kappa$$\mathrm{x}$$[mathring]_{\circ \mathrm{x}\mathrm{x}}\circ \mathrm{x}8\mathrm{x}$$8\mathrm{K}\lambda$$\circ$$\mathrm{x}$$\mathrm{K}\mathrm{O}$$\mathrm{x}$$8\circ \mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{X}\mathrm{K}$$\mathrm{x}\mathrm{O}$$\mathrm{o}\mathrm{x}8_{\mathrm{X}}^{\mathrm{K}}\mathrm{o}\mathrm{x}$xOxO$\mathrm{x}\circ \mathrm{x}\mathrm{O}$$\circ$$\circ$$[mathring]_{\circ \mathrm{x}\mathrm{x}}\circ \mathrm{x}-\mathrm{x}^{\mathrm{X}}8$..

$\mathrm{s}[mathring]_{\mathrm{x}}^{\mathrm{X}}\mathrm{s}_{\mathrm{O}}^{[mathring]_{\mathrm{X}}}\mathrm{x}^{\mathrm{K}}\mathrm{x}_{\mathrm{O}\mathrm{x}^{\mathrm{X}}}$$\circ\circ \mathrm{x}\mathrm{x}[mathring]_{\circ}\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}_{[mathring]_{\mathrm{K}}}$$0[mathring]_{-}\circ \mathrm{x}\mathrm{O}\mathrm{O}\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}$$\circ \mathrm{x}[mathring]_{\mathrm{x}}\mathrm{O}^{0\mathrm{O}\mathrm{x}}\mathrm{K}\mathrm{O}$$\circ \mathrm{x}\mathrm{x}\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{K}\mathrm{K}@8$$8:\mathrm{x}\mathrm{O}[mathring]_{\mathrm{x}\mathrm{x}}$$8\cdot.\mathrm{x}\mathrm{x}\mathrm{x}0\mathrm{O}$$\mathrm{x}$$0$$\circ\cdot.\circ \mathrm{x}\circ.\mathrm{x}\mathrm{X}\mathrm{K}\mathrm{X}\mathrm{X}8$$\mathrm{x}$xo$[mathring]_{\circ}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{o}\mathrm{x}\circ$$\mathrm{x}$$\circ$$0^{\cdot}\circ \mathrm{x}\circ.\mathrm{K}\mathrm{X}\mathrm{K}\mathrm{K}.-8$$\mathrm{K}$$\mathrm{x}\mathrm{O}$..

$8\mathrm{x}\mathrm{o}.\cdot[mathring]_{\mathrm{X}\mathrm{x}}$$\mathrm{x}$$0$$\mathrm{o}\mathrm{O}\mathrm{K}[mathring]_{\mathrm{x}}.\mathrm{x}^{\mathrm{X}}\mathrm{x}\mathrm{x}8$$\mathrm{x}$$\mathrm{K}\circ$$8^{\mathrm{K}}\mathrm{x}\mathrm{g}\mathrm{x}-$$8_{\mathrm{K}}^{\mathrm{x}}\S_{\mathrm{K}}^{\mathrm{x}}$$\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{O}$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{x}\mathrm{x}8_{\Delta}^{\Delta}8$

定理 4 この連鎖数判定問題のインスタンスにおいて、 5 飼以上の國時消しはできな$\nu\backslash _{8}$$[mathring]_{\circ \mathrm{K}\mathrm{K}}$$8\mathrm{x}\mathrm{x}$$[mathring]_{\circ \mathrm{x}\mathrm{x}}$$\mathit{0}\Lambda\epsilon_{\mathrm{X}}^{\mathrm{x}}\mathrm{O}-\mathrm{x}\mathrm{x}8^{[mathring]_{\Delta}}8$$0\Delta \mathrm{o}\mathrm{x}0\mathrm{X}\mathrm{O}\mathrm{x}\mathrm{x}\mathrm{x}8_{\mathrm{A}}^{\mathrm{A}}8$$0\Delta \mathrm{O}\kappa\circ \mathrm{x}\mathrm{x}\mathrm{x}\mathrm{x}8_{\Delta}^{[mathring]_{\Delta}}8$$0\Delta \mathrm{O}\mathrm{x}[mathring]_{\mathrm{x}^{\mathrm{K}\circ \mathrm{X}}\lambda}8_{\Delta}^{\Delta}8$$\S \mathrm{X}\mathrm{K}$$[mathring]_{\mathrm{X}}82_{0}^{\mathrm{x}}$88$\mathrm{x}$

また、最後のピース以外では連鎖として消え$\mathrm{K}\mathrm{A}\mathrm{O}$$\circ$$\wedge\circ \mathrm{A}\mathrm{O}$$\mathrm{x}\mathrm{O}\Delta \mathrm{O}$$\mathrm{X}\mathrm{O}\Delta \mathrm{O}$

xOAO

$($
$8\mathrm{x}8_{0}^{\mathrm{x}}\Delta \mathrm{x}$$8_{\mathrm{A}}^{\Delta}8_{\mathrm{X}}^{\mathrm{x}}\mathrm{X}\mathrm{O}\Delta 0$$8_{\Delta}^{\mathrm{A}}8^{\mathrm{x}}\mathrm{x}\mathrm{O}\Delta\circ \mathrm{x}$$8^{\Delta}8\mathrm{x}\mathrm{x}6_{\Delta \mathrm{O}}\mathrm{x}$$8_{4}^{\Delta}8\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{A}\mathrm{O}\mathrm{K}$$8_{\Delta}^{\Delta}8^{\mathrm{x}}\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}$$\circ \mathrm{x}\circ \mathrm{x}\Delta \mathrm{O}$る以外ぶよを消すような操作はできな$0\Delta \mathrm{O}\mathrm{x}$$0\Delta \mathrm{O}\mathrm{x}$$0\Delta \mathrm{O}\mathrm{x}$$0\Delta \mathrm{O}\mathrm{X}$$0\Delta \mathrm{O}\mathrm{X}$$\circ\Delta\circ \mathrm{X}$$\mathrm{V}_{\mathrm{O}}^{\backslash }$$\mathrm{i}$定理 4 より、 次のような操作を行って得られる連鎖を正当でな

ni$\mathrm{t}\mathrm{i}$filler, . . . , termi mat or

at or$\mathrm{f}\mathrm{i}$

.

ller

い連鎖と呼ぶことにする。
図5

ピース列が終了していないにもかかわらず、 ぶよを消す
・連鎖の過程で 5 個以上の同時消しが起こる$\mathrm{B}\mathrm{u}\mathrm{d}\sigma \mathrm{e}\mathrm{t}$へのピースの正当な配置

・連鎖の過程で絶対に消されないぶよが現れる口
逆に、 そのような操作をしないで得られる連鎖を正当な連鎖と呼ぶことにする。

口

定理 5 任意の 3-PARTITION のインスタンスに対して、 連鎖数籾定問題のインスタンスで 連鎖可能となる初期盤面 $B$ に対する

ロ$\triangle$$k$

ピース $P$ の操作が必ず存在する。

各 bucket に目皿するピースは initiator,

隆明の概略$\mathrm{f}\mathrm{i}11\mathrm{e}\mathrm{r}\mathrm{x}a_{i}$$A_{\mathrm{j}}$口,$\bullet\bullet$$\bullet\bullet\bullet$$\bullet\bullet\bullet$$\bullet\bullet$$\bullet\bullet\bullet$$\bullet\bullet\bullet$

セットのピースが置かれたときに bucket が満たされることと、となることは対応している。 3-PARTITION のインスタンスカ ‘yes” となるならば、 すべての bucket についてこれが$\mathrm{x}\mathrm{O}\cross$$\mathrm{x}\mathrm{O}\mathrm{X}$$\triangle \mathrm{O}\cross \mathrm{O}$$\cross \mathrm{O}\cross$$\mathrm{x}\mathrm{O}\cross$$\mathrm{O}\cross \mathrm{O}$$\mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{O}\cross$$\triangle\cross \mathrm{O}\cross$$\mathrm{O}\mathrm{x}\mathrm{O}$$\square \cross \mathrm{O}\cross$$\mathrm{o}\mathrm{x}\mathrm{O}$$\cross \mathrm{O}\cross \mathrm{O}$$\mathrm{x}\mathrm{O}\cross$口$\mathrm{x}\mathrm{O}\cross$$\mathrm{x}\mathrm{O}\cross$$\mathrm{O}\cross \mathrm{O}$に対応した bucket だとすると、 3$\bullet\bullet.\bullet\bullet\dot{\bullet}\bullet$$\bullet\bullet.\cdot\bullet\bullet\bullet\bullet$$\triangle \mathrm{O}\cross \mathrm{O}$ロ口ロterminator である。 これらはすべて図?? のように置いていく。
これを 1 セットとする。

$\square \downarrow\bullet.\cdot\bullet\bullet\bullet$$\mathrm{O})\sigma \mathrm{O}$$\mathrm{O}\cross \mathrm{O}$$\mathrm{x}\mathrm{O}\cross$$\mathrm{O}\cross \mathrm{O}$$\mathrm{O}\cross \mathrm{O}$$\cross \mathrm{O}\cross$$\sum_{a;\in A_{\mathrm{j}}}a_{i}=T$成り立つ。 その後に$\mathrm{k}\mathrm{e}\mathrm{y}_{\mathrm{I}}\mathrm{t}\mathrm{s}\mathrm{u}\mathrm{m}\mathrm{o}$

(b)

(a)

$\mathrm{t}$$\mathrm{e}$を図 6 のように配置して発火させると、 連鎖が正しく動作し、 $20sT+58s+8T+53$ 運鎖となる。

園 7

盤面左上部における連鎖の発火

口

5 帰着の正当性
以下では、 3-PARTITION で “no” となるならば、 連鎖数判定問
題でも

$k$

連鎖が不可能であることを示す。

51 蓮鎖の流れ
511 Bucket の側面
まず、連鎖を発火用後の連鎖の様子を見てみよう。 補題 6 から連ピースを bucket に積み上げていく過程において、 連鎖の進行方向が明らかでないとその形を想定するのが困難である。 そのため鎖の発火は図に、初期盤面に置かれているぶよの組合せから、 どのような流れで

図連鎖が進行するのかが一意に定まることを示す。
本論に入る前に、 連鎖の発火について確認しておく。

のいずれかに$7(\mathrm{b})$) のように行われる。 途中までその連鎖を追って) の状態まで進行する。 この連鎖を続けるために、の色で示した、 列 $(5, 8T+51)$ , $(5,8T+50\rangle,$ $(5,8T+49)$$\mathrm{O}$

のぶよを置くことになる。

この時点で、 次の連鎖は bucket 内のぶよを用いて進む。 何が、座標 (1, $8T+54$ }, $(2,8T+53)$
補題 6 連鎖の発火は、tsumoの口のぶよと迷結することで行われる。
$\prod_{\square }$連鎖を発火する箇所は決まっているので、はじめの数連鎖 @ まで
そは明らかである。 しかし、 bucket 内の構成は定まっていなの外にたどり着いたとき、
bucketこで、 連鎖がはじめの bucket$4\backslash \text{。}$へどう連鎖が進行していくかを考え、 全体の連鎖の進行方向を明らかにする。

いくと、 図$7\langle \mathrm{a}$$7\langle \mathrm{b}$

回かの bucket 内の連鎖の後、 初期盤面にあったぶよが消える。
Bucket 内の連鎖の構成を想定するのは現段階では困難なので、 列), $(7, y)(y=5, \ldots,8T+52)$ のうちどのぶよが消えるかに注目する。 各 bucket について、 これらのぶよを
bucket の側面と呼ぶことにする。 また、 そのうち色ぶよがある{4, ), $(6, y)\{y=1,$
$y$

$4$

$\ldots,$$y$

座標のうち最も値の大きいものを側面の高さと呼ぶことにする。
補題 7 ある bucket に連鎖が及んだとき、 その側面の高さを $3t$ とすると、 そのうち正当に消すことができるのは高さ $3t-2$ のぶよ

150

(b)

(a)

$\mathrm{O}\Delta \mathrm{O}\cross \mathrm{O}\mathrm{x}\Delta$

060
O60
060 OxOO$\mathrm{x}\circ \mathrm{x}\mathrm{O}$$\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}$$\mathrm{x}\mathrm{x}O\mathrm{x}\ovalbox{\tt\small REJECT}_{\chi}’ \mathrm{x}[mathring]_{\mathrm{x}}\mathrm{X}\circ \mathrm{X}\circ \mathrm{x}_{\mathrm{X}}\mathrm{x}\mathrm{O}\Delta \mathrm{x}\circ[mathring]_{\mathrm{x}}\mathrm{O}\Delta \mathrm{O}\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}0\circ \mathrm{x}\mathrm{O}\Delta[mathring]_{\mathrm{O}}\mathrm{x}\circ \mathrm{X}\Delta\circ \mathrm{x}\mathrm{O}\mathrm{O}\Delta\circ[mathring]_{\mathrm{X}}\circ \mathrm{x}\mathrm{O}\Delta O\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{x}\circ \mathrm{x}\mathrm{O}\Delta 0\mathrm{x}$$\mathrm{O}$$\mathrm{x}$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$[3$\mathrm{x}$Ox$\mathrm{x}\circ \mathrm{x}\circ \mathrm{x}\mathrm{O}\mathrm{O}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}O\mathrm{x}\mathrm{O}\vee \mathrm{O}\mathrm{x}$CI$\mathrm{x}\mathrm{O}\aleph \mathrm{O}\mathrm{X}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\circ \mathrm{x}\mathrm{O}$0$\mathrm{x}\circ \mathrm{x}\mathrm{O}\Delta\Delta$$\mathrm{x}\mathrm{O}\mathrm{x}\circ \mathrm{x}\mathrm{O}\Delta$$0-8_{\mathrm{x}}^{\mathrm{X}}\mathrm{o}\mathrm{x}8_{\mathrm{X}\Delta}^{\mathrm{X}\mathrm{X}}$$\mathrm{o}\circ \mathrm{x}\mathrm{o}^{\mathrm{X}}8_{\chi}^{\mathrm{X}}\mathrm{o}\mathrm{o}\cross 0_{\mathrm{X}}8_{\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\kappa 0_{\mathrm{X}}8_{\mathrm{X}}^{\mathrm{X}}}^{\mathrm{X}\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}}$$\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}O\mathrm{x}\circ \mathrm{x}O\mathrm{x}\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}O$

XO$\Delta \mathrm{x}O\mathrm{x}\mathrm{O}$$\mathrm{x}\mathrm{O}\mathrm{x}$OX$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{O}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}O$$O\mathrm{x}\mathrm{O}\mathrm{x}\circ$$\mathrm{O}$$\mathrm{x}\circ \mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{O}\mathrm{x}O\mathrm{x}$$\mathrm{x}$ooox$\mathrm{x}$Ox$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\circ$$\mathrm{x}O\mathrm{x}$$\mathrm{x}\mathrm{x}\circ \mathrm{x}\cdot \mathrm{x}\circ \mathrm{x}O\mathrm{x}$$\mathrm{x}\mathrm{O}\cross \mathrm{O}$$\mathrm{O}\mathrm{x}O\mathrm{x}$Ox$0$$\mathrm{x}$$\mathrm{x}\mathrm{O}$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$$\circ \mathrm{x}$Ox.

$\mathrm{x}\mathrm{x}$$\circ \mathrm{x}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{Q}$$\mathrm{x}$Ox.

$\circ$$\kappa \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\cdot \mathrm{K}\circ$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\kappa$$\mathrm{O}$$\mathrm{O}\mathrm{x}\mathrm{o}\mathrm{x}$$\mathrm{o}_{\mathrm{X}}o\mathrm{x}$$\mathrm{O}\mathrm{O}\mathrm{x}\mathrm{O}$Ox$\mathrm{x}[mathring]_{\mathrm{O}}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{x}0$$\mathrm{x}\mathrm{O}\mathrm{x}0\mathrm{X}\circ \mathrm{X}\circ$$\Delta\chi\circ\Delta[mathring]_{\mathrm{O}}\mathrm{x}\mathrm{O}$$\circ \mathrm{x}\mathrm{O}\mathrm{x}$$\circ \mathrm{x}$$\mathrm{O}\mathrm{x}\circ \mathrm{X}\mathrm{O}$$\Delta \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{x}\mathrm{O}$$\circ \mathrm{x}\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{x}\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\circ \mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\kappa \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$a OX060

Ox$\mathrm{x}\mathrm{O}$$\mathrm{O}\mathrm{x}O\Delta$$\mathrm{x}\mathrm{O}$$\mathrm{O}\mathrm{x}$Ox$\mathrm{x}\mathrm{O}$oxQx$\mathrm{x}$$\mathrm{x}\mathrm{O}\mathrm{x}0$$\circ$$\mathrm{x}$$\mathrm{x}$$\mathrm{x}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\circ \mathrm{x}$$\circ \mathrm{X}$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\kappa \mathrm{O}\kappa\Delta$$\mathrm{o}\mathrm{o}$$\circ$OA$\mathrm{x}0\mathrm{x}\mathrm{x}$$\mathrm{Q}\mathrm{x}$)$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{Q}\mathrm{c}$$\mathrm{x}\mathrm{O}\mathrm{x}$OO
O6$\circ \mathrm{x}\mathrm{O}\Delta\Delta$$\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\circ \mathrm{x}\mathrm{x}$$\circ \mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{O}\mathrm{x}O\mathrm{x}\circ \mathrm{r}\mathrm{O}\mathrm{x}\circ \mathrm{X}\circ \mathrm{x}\circ \mathrm{x}\mathrm{O}\cross 0\mathrm{x}$$\mathrm{x}O\mathrm{x}\mathrm{O}^{\chi}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{O}\mathrm{x}\circ \mathrm{x}\mathrm{O}^{\chi}$$\circ \mathrm{x}\mathrm{O}\mathrm{x}O\mathrm{x}\Delta$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}O\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\kappa O\mathrm{x}$$\circ \mathrm{x}\mathrm{O}$Ox$\mathrm{x}$$\mathrm{x}\mathrm{O}\mathrm{x}$OAO$\mathrm{x}O\mathrm{x}\mathrm{O}\Delta \mathrm{O}\cross \mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{O}\mathrm{x}$O60)(OOAO$\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}$$\mathrm{a}\mathrm{x}0\mathrm{x}0\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}$OQO$\mathrm{O}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}60$x060$\mathrm{x}$.

$\mathrm{x}\mathrm{O}\mathrm{X}\mathrm{X}$$\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}^{\chi}$$\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}$

(d)

(c)
園6

$8\mathrm{u}\mathrm{c}\mathrm{k}\mathrm{e}\mathrm{t}$へのピースの正当な配置と連鎖の発火が同様に適用することができ、 それが成り立つ。

のみである。

証明の概略$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}$$\mathrm{x}\mathrm{O}$OAO$0\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$$\Delta \mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{Q}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta O\mathrm{x}$$\mathrm{O}\mathrm{O}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{X}\mathrm{X}8_{\Delta \mathrm{O}\mathrm{x}O\Delta}^{\Delta \mathrm{O}\mathrm{x}0\Delta}$$0\Delta 0$$\Delta \mathrm{O}\mathrm{x}\mathrm{C}\Delta \mathrm{O}\mathrm{x}O\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}$$\Delta$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}0\mathrm{x}$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\Delta$$\mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}\Delta \mathrm{O}$

まず、 ある高さ $3t$ の bucket の左側面について考える。 同色のぶよのつながりを上部から$\mathrm{F}_{1},l_{2,)}\ldots\mathrm{F}_{t}$正当に消すことのできるぶよを探す。 すると、$\mathrm{F}_{2}$とし、 その中で以外を消すと正当でないことがわかる。

この場合に消えるぶよのかたまりに注目すると、 その belt 上の

16 偶のぶよが 1 つの単位となって消えることがわかる。 すなわち、
bucket の側面のぶよが消えるときは、 4 行分ずつ消されるという右働面についても同様の理由から成り立つ。 したがって、 bucketの側面は、 上から 2 番員のつながりのみを正当に消すことがで口きる。

5.1.2 Bucket 内の遠鎖の進行方向
bucket 内での連鎖の構成について明らかにする。 補題 7 により、
bucket に連鎖が及んだときに初期盤面のどのぶよが消されるかが

2 通りに絞られた。 1 つは連鎖方向が一定のままになるのと、 もう
1 つは連鎖が 「折り返し」 を趨こすものである。
各 bucket と belt が交差する、座標 $\{6i+5,4j+1),$ $(6i+6,4j+4)$$\backslash$

ことになる。

4 行分消された bucket の側面についても、 先に示した場合分け

151$\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet\bullet$$\mathrm{r}\downarrow \mathrm{I}\mathrm{x}\mathrm{x}\mathrm{O}\cross\bullet\bullet\bullet \mathrm{O}\mathrm{x}$rz$O O$\bullet\bullet\bullet$$\cross$r3$$\bullet\bullet\bullet$$\mathrm{O}\cross \mathrm{o}\mathrm{O}\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{I}_{\iota_{2}^{11}}\mathrm{x}\mathrm{o}\mathrm{x}$$\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{x}\mathrm{O}\cross$$\mathrm{r}5mathrm{x}\mathrm{o}_{\mathrm{X}}\mathrm{r}\prime \mathrm{J}_{\mathrm{O}\mathrm{x}\mathrm{o}}^{\mathrm{O}\cross \mathrm{O}}$$13$\mathrm{r}\epsilonmathrm{O}\mathrm{x}\mathrm{O}$:$i$$\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{I}\mathrm{x}\mathrm{o}\mathrm{x}\mathrm{l}\mathrm{t}\cdot 5$$\mathrm{o}\mathrm{x}\mathrm{o}$$\cross \mathrm{O}\cross 1t\cdot 3$$\mathrm{O}\cross 0\mathfrak{g}_{1\mathrm{t}-\mathrm{z}}\mathrm{o}\mathrm{x}\mathrm{O}$$\mathrm{x}$$\mathrm{r}\mathrm{t}\cdot s\mathfrak{g}\mathrm{o}_{\mathrm{X}}\mathrm{o}^{\mathrm{X}}\mathrm{o}\mathrm{o}$

$1,-4

Ox$

$1\iota\sim 1$

rt-,

:

$\mathrm{r}\mathrm{t}\cdot \mathrm{z}\mathfrak{g}_{\mathrm{o}^{\mathrm{X}}\mathrm{o}^{\mathrm{X}}}^{\mathrm{o}_{\mathrm{X}}\mathrm{o}_{\mathrm{X}}}$$\mathrm{r}_{2}.\iotatriangle \mathrm{O}\mathrm{x}\mathrm{O}$$\mathrm{o}\cross 0iota_{\mathrm{t}}$$\mathrm{f}\iotamathrm{O}\mathrm{x}\mathrm{O}\mathrm{x}$(b)$(\mathrm{a})$

園8

:

:

$x\mathrm{x}\mathrm{O}\mathrm{x}$$\mathrm{r}‘\cdot 3mathrm{O}\mathrm{x}\mathrm{O}$

図9

盤面全体における連鎖の流れ

Bucket の側面で消すことかできるぶよを探す

を対角線とするような長方形の領域を、 box と呼ぶ。

$\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{x}$$\mathrm{O}\mathrm{x}\mathrm{x}\mathrm{O}\mathrm{x}\mathrm{O}^{\cdot}\ovalbox{\tt\small REJECT}_{\mathrm{x}^{\mathrm{X}}}^{\cross \mathrm{O}}’.\cdot 0$

補題 8 各 box において、 0 のぶよはちょうど 4 飼ずつ置かれる。

$\mathrm{x}\mathrm{O}\mathrm{O}\mathrm{x}\mathrm{O}$.
$\mathrm{o}\mathrm{x}^{\mathrm{X}.\Delta \mathrm{O}^{\chi}}\ovalbox{\tt\small REJECT}_{{}^{t}\mathrm{x}\mathrm{o}}^{\iota^{\mathrm{t}}}$次に、 これから全体の連鎖方向を決定付ける補題を示す。

補題 9Bucket の中での折り返しは正当でない。

図 10

始めの 2 手の配置証明の概略 左から右に向かって進行する速鎖を例として考える。
Bucket の左側面に到達した連鎖が、 下の belt の同じく左側百に連鎖が及ぼうとすると、 そこで消える のぶよの連結するパターン
は 4 通り考えられる。 一方、 その box に配置できる 0 のぶよのパだが、 bucket の中ではどのような連鎖が起こるだろうか。 あるのように O 以
bucket ですべての belt において、 例えば

ターンは補題 8 より 7 通りとなる。 そのいずれにおいても、 鳳中
のぶよをよりも下の行には連鎖を進めることがで

外のぶよが 1 組だけ消えると、 Bucket の容積とぶよの個数の関係$\mathrm{O}$の色で示した$\mathrm{O}$きない。 なぜならば、$\mathrm{O}$

のぶよを消すときは必ず bucket の側面を巻き込 $b$ 形でなければならないからである。 したがって、 bucket
口
内での折り返しは正当でない。

.

補題 7 と補題 9 により、盤面全体における連鎖方向が明らかになった。 それを次の定理として示す。 また、 それを図 9 に表す。
定理 10 連鎖は盤面両端でのみ折り返され、 奇数番目の belt は左$\mathrm{O}arrow\trianglearrow \mathrm{O}$からちょうど bucket が満たされるように連鎖を構成することがで
口 $arrow 0$ のように O 以外のぶよが 2 園
きるだろう。 しかし、$\mathrm{O}arrow\trianglearrow$

続けて消えると、 その bucket では別に
そこで、$\mathrm{O}arrow \mathrm{O}$と消える速鎖は bucket 中で構成することができないことを示し、 より詳細な連鎖の構成を明らかにする。

補題 13 Bucket 中で $0arrow 0$ と消える連鎖の形は一通りに定まる。
定理 14 Bucket 中で

5L3 Bucket の容類
本節では、 各 bucket に置くことができるぶよの総数を求める。

証明の概略

るぶよの悩数とその容積の箆は 4 の倍数でなければならない。

$\mathrm{O}arrow \mathrm{O}$$\mathrm{O}arrow \mathrm{O}$と消える連鎖は正当でない。

捕題 13 より、 bucket の最も下でないある box で、と消える連鎖を 1 っ構成し、 その下の box の連鎖の形を考の速鎖がある box の下の box もまたの連鎖でなければならないことが分かる。 ところが、最も下の box
える。 すると、はそのような構成ができないことが、 初期盤面からただちに判断できる。 したがって、 どの box にもしい個数のぶよが置かれなければならない。

はできない。

5.1.4Bucket 内で消える色の顛番

52

いく。

定理 7 によって bucket 間の連鎖の流れが明らかになったわけ$\mathrm{O}arrow \mathrm{O}$$\mathrm{O}arrow \mathrm{O}$

補題 12 正当な連鎖のために, 各 bucket において、 その容積と等

ここからは bucket 内でどのような連鎖が構成可能かを調べてのような連鎖が起こらなければならなくなる。

から右、 偶数番目の belt は右から左に向かって進行する。

補題 11 正当な速鎖のために、 各 bucket において、 bucket }こ入$\mathrm{O}rightarrow \mathrm{O}$$\mathrm{O}arrow \mathrm{O}$の連鎖を構成すること
口

ピースの配置

前節までの議論によって、盤面全体の連鎖の流れと bucket 内の連鎖の構造について明らかになった。 ここからは、入力のピースをどのように配置できるかを考える。

152の繰り返し回数を、 3-PARTITION のインスタンス$\{a_{\mathrm{I}}, \ldots, \mathrm{a}_{3},\}$に対応づけると、補題 18 により、 $\sum_{a:\epsilon A_{j}}a_{i}=T$ が成り立つ。 すな
わち、 これは 3-PARTITION において$*\mathrm{s}$

”

となる

口

$\circ$6 結論と今後の課題
定理 21 連鎖数判定問題は$\circ$口以上より、 一般化ぶよぶよの連鎖数判定間題が補題 15 ある box に科以外のぶよが置かれると、 正当な連鎖のために、 その box には完全。

補題 3, 定理 1, 5, 20 より明らか。

証明
定理 10,14 により、 次のことが言える。

$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$完全である

ことが示された。

一般化ぶよぶよにおける他の問題として、 全消し判定問題がおとその色のぶよだけ置くことができる。

る。 これは、 入力 $P$ のピース列が終了した時点で盤面上のぶよをさらに、 初期盤面から次のことも雷える。
補題 16 初期盤面において、 bucket に$\mathrm{O}$

全て消すことができるかを判定する闇題である。 これものぶよを置くことは正当であることが知られている$\mathrm{N}\mathrm{P}$

完全$[6]_{0}$また、 初期盤面が空で、 かっ入力 $P$ には 2 色のぶよで限定したでない。

全消し判定問題は、 線形時間で計算可能であることが示されてい補題 17 このインスタンスにおいて、 おじやまぶよの上にピースを置くことは正当でなる$[7]_{9}$多くの場含、 初期盤面を空にするとピースの配置の仕方が無数$\triangleright\backslash _{\mathrm{O}}$に考えられるため、 その計算量がどう変化するかはわからないが、ここから入力のピースの配置を調べ、initiator, 韻 er, terminatorについてその配置の一意性を確認する。 初期盤面における bucket

それを調べることは困難であると思われる。

の状態はどれも同じなので、 どの bucket にピースを置くかは任

参考文献

意に選択するものとする。 以後、 その bucket をとする。
bucket を $B,$ $B’,$ $B”,$
補題 15 により、 1,2 手
は配置が確定する

それ以外の$A_{\backslash }$$\ldots$$\Delta’ \mathrm{O}\Delta \mathrm{O}$を$0^{\mathrm{o}}$回転して列$6\mathrm{i}+5$または列$6\mathrm{i}+6$$($

図$10)_{\text{。}}1$

手目に置くと、 2 手自を正当に置くことができなくなるからである。

3,4,6 手目は$A$

以外の bucket に鐙ける可能性がある。 3,4,6 手

目を $A,$ $B,$ $B’,$ $B”$ のどの bucket に置く力

$1\text{、}$またそれによって 5 手昌以降のピースはどの bucket に置かれるかを衰 1 に示した。
表 1 より、 初期盤面においてピース列 initiator は 1 つのbucket にのみ配置することができ、 その結果、 ffller を迎える。
$\mathrm{F}\mathrm{i}\mathrm{l}\mathrm{l}\epsilon \mathrm{r},\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{o}\mathrm{r}$についても同様の議論によリピースの配置は一意に定まり、 次の補題が導かれる。

[1] Erik D.Dem aine, Susan Hohenberger, David Liben-Nowell.
Tetris is Hard, Even to Approximate. Technical Report
MIT-LCS TR-865, Massachusetts Institute of $Technol\eta y$ .
$\cdot$2002.
[2] Michael R. Garey and David S. Johnson. Complexity Results for Multiprocessor Scheduling under Resource Constraints. SLAM J. Comput., 4:397-411, 1975.
[3]
R. Garey and David S. Johnson. ComPuters andIntroctabdity: A Guide to the Theory of $NP,Completeness$
W. H. Freeman and Company, New York, 1979.
[4] (c) SEGA. http:.co[5] COMPILE.
.
.compile.co .
$\mathrm{M}\mathrm{i}\mathrm{c}\mathrm{h}\mathrm{a}\epsilon \mathrm{I}$.

$//\mathrm{w}\mathrm{w}\mathrm{w}.\epsilon \mathrm{e}\mathrm{g}\mathrm{a}$$\mathrm{h}\mathrm{t}\mathrm{t}\mathrm{p}://\mathrm{w}\mathrm{w}\mathrm{w}$

補題 18 $f\geq 0$ について、 ピース列 initiator, flllerxr, terminator
は 1 つの bucket に続けて置かれなければならない。 また、 その配置は一意に定まる。

Key. tsumo$\mathrm{o}\mathrm{C}1$を捕題 6 にしたがって醗置することで、 連鎖が発火される。
補題 19 ピース列 key$\Delta \mathrm{O}\mathrm{x}s,$

っずつ三三されなけれぼならな$\triangle\Delta \mathrm{x}s$は全ての bucket にピース 1$\iota\backslash _{\mathrm{o}}$定理 20 連鎖数判定問題のあるインスタンスで$k$

とき、 対応する 3-PARTITIQN のインスタンスでも証明

連鎖数判定問題のインスタンスで$k$

連鎖可能である

unyes となる。

連鎖可能であるということは、 正当な連鎖を構成できるということである。

補題 6 より入力 $P$ の最後のピース tsurno で連鎖を発火し、捕題

18, 19 より舘の bucket はちょ以外のピースで入力の盤面
うど満たされる。 このとき、 各 bucket を 3-PARTITION に置ける集合の分割に対応づけ、 また、 入力 $P$ に現れる filter$B$$\mathrm{u}\mathrm{m}\mathrm{o}$$A_{1},$$A_{\epsilon}$$\ldots,$. .
$\mathrm{j}\mathrm{p}/$$\mathrm{j}\mathrm{p}/$完全. 東京大学卒業[6] 牟田秀俊. ぶよぶよ全消し判定問題は論文, 2005.
[7] 亀村真理. ぶよぶよの 2 色全消し判定問題. 電気通信大学卒業
論文, 2005.
$\mathrm{N}\mathrm{P}$