Ball-sort transposition

組合せパズル · プレプリント草稿

\(N\) 本のスタックを空き 1 本で転置する:色そろえパズルは 6 色で 55 手、一般には \((3N^2-N-4)/2\) 手以上

要旨. 色は \(N\) 色、玉は各色 \(N\) 個、スタックは \(N+1\) 本で容量は \(N\) とする。最初は 1 本が空で、残りのスタックはどれも下から色 \(1,\dots,N\) の順に積まれている。1 手で、あるスタックの一番上の玉を、満杯でない別のスタックへ移す。どのスタックも空か同じ色 \(N\) 個になるまでの最少手数を \(T(N)\) とする。本稿では、すべての \(N\) について \(T(N)\ge(3N^2-N-4)/2\) を証明し、計算機による探索で \(T(6)=55\) を決定する。\(T(2),\dots,T(5)=3,10,21,36\) は既知である。7 色では \(75\le T(7)\le78\) を得た。探索は、完成までの距離の下界 \(J\) で枝刈りした幅優先探索である。\(J\) を定義し、正しさを証明する。\(J\) を使うと、\(T(6)\ge55\) の証明でたどる状態は 471 万で済む。また、\(N\le24\) のすべてについて、機械的に検証した具体的な手順を与える。確定した値は \(N=6\) まで \((2N-1)(N-1)\) と一致する。それより大きい \(N\) でも一致するかは未解決で、\(N\ge8\) について私たちが知る最良の手順はこの式より長い。

1. 問題と結果

扱うのは、「ボールソート」「色そろえ」と呼ばれるゲームのうち、玉をどの玉の上にも置ける版である。色は \(N\) 色、玉は各色 \(N\) 個、スタックは \(N+1\) 本で、これをレーンと呼ぶ。容量はどれも \(N\)。レーンには \(0,\dots,N\) の番号を付ける。初期配置では、レーン 0 が空で、レーン \(1,\dots,N\) はどれも下から色 \(1,2,\dots,N\) の順である。1 手は、空でないレーンの一番上の玉を、玉が \(N\) 個未満の別のレーンの一番上に置く操作である。どのレーンも空か同じ色 \(N\) 個である配置を完成形と呼ぶ。\(T(N)\) は、初期配置から完成形までの最少手数である。

初期配置では横の段がどれも 1 色で、完成形では縦の列がどれも 1 色になる。つまり、スタックでできた \(N\times N\) の配列を、空きスタック 1 本で転置する問題である。

定理 1.

すべての \(N\ge2\) について \(T(N)\ge(3N^2-N-4)/2\)。

結果 2(計算機による).

\(T(6)=55\)。

結果 3(計算機による).

\(75\le T(7)\le78\)。また \(8\le N\le24\) について表 1 の上界が成り立つ。

定理 1 は 4 節で証明する。結果 2 は、55 手の具体的な手順と、54 手以内の手順がないことを示す探索(6 節)を合わせたものである。結果 3 の上界は具体的な手順で、短いスクリプトで再生して確かめられる(7 節)。

\(N\)下界上界下界の根拠上界の根拠\((2N-1)(N-1)\)
233確定全探索最短の手順3
31010確定全探索最短の手順10
42121確定全探索最短の手順21
53636確定全探索最短の手順36
65555確定下界 J を使った枝刈り全探索2 つの規則で制限した探索55
77578未確定下界 J を使った枝刈り全探索ビーム探索78
895106未確定下界 J を使った枝刈り全探索以前から記録されていた手順105
9117140未確定下界 J を使った枝刈り全探索ビーム探索136
10145179未確定下界 J を使った枝刈り全探索ビーム探索171
11175224未確定下界 J を使った枝刈り全探索ビーム探索210
12208272未確定一般式 (3N²−N−4)/2以前から記録されていた手順253
13245329未確定一般式 (3N²−N−4)/2ビーム探索300
14285387未確定一般式 (3N²−N−4)/2ビーム探索351
15328457未確定一般式 (3N²−N−4)/2ビーム探索406
16374525未確定一般式 (3N²−N−4)/2ビーム探索465
17423625未確定一般式 (3N²−N−4)/2ビーム探索528
18475719未確定一般式 (3N²−N−4)/2ビーム探索595
19530853未確定一般式 (3N²−N−4)/2ビーム探索666
20588992未確定一般式 (3N²−N−4)/2ビーム探索741
216491,114未確定一般式 (3N²−N−4)/2ビーム探索820
227131,355未確定一般式 (3N²−N−4)/2ビーム探索903
237801,568未確定一般式 (3N²−N−4)/2ビーム探索990
248501,672未確定一般式 (3N²−N−4)/2ビーム探索1,081
表 1. \(T(N)\) の上界と下界。右端の列は、確定した値を通る 2 次式(9 節)。

定理 1 から \(T(N)\ge1.5N^2-O(N)\) が出る。\(T(N)=O(N^2)\) は知られている [1] ので、\(T(N)=\Theta(N^2)\) である。係数は分かっていない。

3. 不動の玉と家

配置 \(s\) と、\(s\) から完成形までの手順を 1 つ固定する。以下これを「この手順」と呼ぶ。この節と続く 2 節の主張は、初期配置に限らず、任意の配置 \(s\) についてのものである。

完成形では、色 \(c\) の玉は 1 本のレーンを埋める。これを \(c\) の家と呼ぶ。色が違えば家も違う。この手順で一度も動かない玉を不動と呼ぶ。動く玉の集合を \(M\)、2 回以上動く玉の集合を \(M_2\) とする。手順の長さは \(|M|+|M_2|\) 以上である。

空でないレーンについて、底から同じ色が続く部分を底の連続と呼び、その長さを \(r\)、色を \(c_0\) とする。底の連続がレーン全体であるとき単色、底の連続の上に玉があるとき汚れていると言う。

補題 1.

あるレーンの不動の玉は、底から続けて並ぶ。それらは同じ色なので底の連続の一部であり、そのレーンは \(c_0\) の家である。底の色が \(c\) のレーンのうち、不動の玉を持つものは 1 本以下である。

証明. 玉は、上にある玉より先には動けない。したがって不動の玉は、そのレーンの動く玉すべてより下にある。不動の玉は、いまの位置のまま完成形に残り、完成形のレーンは 1 色である。最後の主張は、\(c\) の家が 1 本であることによる。∎

補題 2.

ちょうど 1 回だけ動く色 \(c\) の玉は、\(c\) の家へ入る。その時点で、そのレーンでそれより下にある玉はすべて、以後動かない色 \(c\) の玉である。

証明. ただ 1 回の移動のあと、その玉は完成形での位置にある。下の玉があとで動くなら、その前にこの玉をどける必要がある。∎

補題 3.

\(L\) を、動く玉を含む \(s\) のレーンとする。\(s\) で \(L\) にある動く玉のうち一番下のものを \(b\)、\(b\) が初めて動く時刻を \(\tau\) とする。\(\tau\) より前に、ちょうど 1 回だけ動く玉が \(L\) に入ることはない。\(\tau\) の直後、\(L\) には不動の玉しかない。不動の玉があれば \(L\) は \(c_0\) の家で、他の色の家ではない。なければ \(L\) は空である。

証明. \(\tau\) より前に \(L\) に入った玉は \(b\) より上にあり、\(b\) が動く前に出ていく必要がある。時刻 \(\tau\) には \(b\) より上の玉はすべて出ていて、\(b\) より下には不動の玉しかない。∎

補題 3 のレーンについて、\(s\) で \(L\) にある動く玉の集合を \(X(L)\) と書く。これは \(b\) とその上の玉すべてである。異なるレーンの \(\tau\) は異なる手の時刻なので、互いに異なる。

4. 下界 \(h+D\) と一般の下界

次のように置く。 \[ h(s)=\sum_{\text{レーン}}(\text{高さ}-r)\;+\;\sum_{c}\Bigl(\sum_{L:\,c_0(L)=c}r(L)-\max_{L:\,c_0(L)=c}r(L)\Bigr). \] 補題 1 より、色 \(c\) の不動の玉の数は、底の色が \(c\) のレーンの \(r\) の最大値以下である。よって \(|M|\ge h(s)\)。

\(s\) で空か単色であるレーンの数を base とする。汚れたレーンを \(\tau\) の順に \(L_1,L_2,\dots\) と並べる。\(X(L_k)\) の玉が初めて動く時刻は \(\tau_k\) 以下である。補題 2・3 より、それがただ 1 回の移動であるなら、行き先は、\(s\) で空か単色のレーンか、\(L_1,\dots,L_{k-1}\) のどれかである。1 本のレーンが家になれる色は 1 色以下である。したがって、\(X(L_k)\) のうちちょうど 1 回だけ動く玉の色は \(\text{base}+k-1\) 種類以下で、 \[ |M_2\cap X(L_k)|\;\ge\;|X(L_k)|-\sigma_{\text{base}+k-1}\bigl(X(L_k)\bigr). \qquad (1) \] ここで \(\sigma_j(X)\) は、\(X\) の色ごとの個数のうち大きい方から \(j\) 色の合計である。 \(X(L_k)\) は底の連続より上の玉をすべて含み、不動の玉がないレーンではレーン全体である。ある色の玉を増やしても、(1) の右辺は減らない。そこで (1) は、底の連続を残すレーンでは「底の連続より上の部分」、それ以外では「レーン全体」を \(X\) として評価できる。補題 1 より、残すレーンは底の色ごとに 1 本以下である。

\(D(s)\) を、汚れたレーンの順番と、残すレーンの許される選び方のすべてについて、(1) の右辺の和を最小にした値と定める。計算は、汚れたレーンの部分集合についての動的計画法による。\(X(L_k)\) は互いに交わらないので \(|M_2|\ge D(s)\) であり、\(s\) からの手順はどれも \(h(s)+D(s)\) 手以上である。

定理 1 の証明. 初期配置では、\(N\) 本のレーン \([1,\dots,N]\) はどれも汚れていて \(r=1\)、\(c_0=1\)、base \(=1\) である。よって \(h=N(N-1)+(N-1)=N^2-1\)。どのレーンも各色の玉を 1 個ずつ含むので、\(k\) 番目のレーンの寄与は、残さないなら \(N-k\)、ただ 1 本の残すレーンで \(k\le N-1\) なら \((N-1)-k\) である。最小値は \(\sum_{k=1}^{N}(N-k)-1=N(N-1)/2-1\) で、\(h+D=(3N^2-N-4)/2\)。∎

5. 下界 \(D'\) と \(J\)

\(D\) では、レーンごとに都合のよい色を選べる。実際の手順では、家は 1 つに決まっている。\(D'(s)\) は、同じ順番についての最小値だが、開いた色の集合 \(O\) を持ち運ぶ。残すレーンが開くのは底の色 \(c_0\) だけで、残せるのは \(c_0\notin O\) のときに限る。全部を出すレーンは、好きな色を 1 つ開く。最初の \(O\) は、\(\min(\text{base},N)\) 色の任意の集合とする。レーンの費用は、\(X\) の玉のうち色が \(O\) にないものの数である。\(D'(s)\le|M_2|\) の証明は手順をたどる。家が、\(s\) で空か単色のレーンか \(L_1,\dots,L_{k-1}\) のどれかである色の集合を \(R_k\) とすると、補題 2・3 より \(|M_2|\ge\sum_k|\{x\in X(L_k):x\text{ の色}\notin R_k\}|\) で、残りのレーン数についての帰納法により、\(R_k\) を含む任意の \(O\) から始めた動的計画法の値はこれ以下になる。\(D'\ge D\) である。

まだ 2 つの緩みが残る。\(h\) と \(D'\) は別々に最小化されていて、残すレーンの選び方が食い違ってよい。また、単色のレーンは、すでに完成したものも含めて、自由に使える家として数えられている。\(J\) はこの両方を除く。

定義.

\(J(s)\) を、次の手続きの費用の最小値とする。まず、単色のレーンのうち残すものを選ぶ(同じ色は 1 本まで)。その色は開いている。空のレーン \(e\) 本について、さらに \(e\) 色以下を開いた色として選ぶ。次に、汚れたレーンと、残さなかった単色のレーンを、任意の順番で 1 本ずつ片付ける。\(c_0\) が開いていない汚れたレーンは残すことができる。費用は \((\text{高さ}-r)\) と、底の連続より上の玉のうち色が開いていないものの数の和で、\(c_0\) が開く。どのレーンも全部出すことができる。費用は、高さと、そのレーンの玉のうち色が開いていないものの数の和で、そのあと開いていない色を 1 つ開くか、何も開かない。

命題 4.

\(s\) からの手順はどれも \(J(s)\) 手以上で、\(J\ge h+D'\ge h+D\) である。

証明. 手順を 1 つ取る。不動の玉を持つ単色のレーンを、残す単色レーンとする。その色と、家が \(s\) の空のレーンである色を合わせたものが、最初の開いた色の集合である。残りの空でないレーンを \(\tau\) の順に並べる(補題 3 はこれらにも成り立つ)。家が、\(s\) の空のレーンか、残す単色レーンか、\(L_1,\dots,L_{k-1}\) のどれかである色の集合を \(R_k\) とする。補題 2・3 より、手順の長さは \[ \sum_k\bigl(|X(L_k)|+|\{x\in X(L_k):x\text{ の色}\notin R_k\}|\bigr) \] 以上である。これは、手続きのある 1 通りの進め方の費用以上である。\(L_k\) に不動の玉があれば、\(L_k\) は \(c_0\) の家なので \(c_0\notin R_k\) で、手続きは残すことができる。\(X(L_k)\) は底の連続より上をすべて含むので、費用は手順のもの以下で、\(R_{k+1}=R_k\cup\{c_0\}\) となる。\(L_k\) に不動の玉がなければ、費用は一致し、手続きは \(L_k\) を家とする色があればそれを開く。∎

初期配置では \(J=h+D\) なので、\(J\) は定理 1 を改善しない。差が出るのは手順の途中である。4 色の全 37,449,732 状態で、\(J\) は正確な距離を一度も超えず、13,639,911 状態で距離と一致し、差の平均は 0.92 手である(\(h+D'\) では 1.58 手)。

7. 上界

表 1 の上界はどれも、リポジトリに保存した手順で、短いスクリプトが再生する(10 節)。\(N\le5\) の手順は最短である。\(N=6\) の 55 手の手順は、2 つの規則(1 本のレーンを最後まで動かさない。玉は、空のレーンか、同じか大きい色の玉の上にだけ置く)で制限した探索で見つけた。この制限の下では探索空間が小さい。\(N=7\) の 78 手の手順はビーム探索で見つけた。

\(9\le N\le11\) の手順は、1 層あたり最大 \(10^6\) 状態のビーム探索のあと、途中の配置から先を繰り返し解き直して得た。\(N=9\) と \(N=10\) では、後で述べる注ぎ単位のビーム探索(幅 \(3\cdot10^4\))がそれぞれ 1 手短い 140 手と 179 手を出した。\(N=11\) では、その並列版(幅 \(10^5\))が 5 手短い 224 手を出した。\(N=8\)(106 手)と \(N=12\)(272 手)の手順は、以前から記録されていたもので、本稿では改善できていない。後者は Claude(Fable)が、1 ステップを「注ぎ」(1 個、上に続く同じ色の塊、入るだけ全部のどれかを 1 回でまとめて動かす。費用は動かした個数)とし、同じ手数どうしで盤面を比べるビーム探索(幅 2,000)で見つけた。1 個ずつのビームでは注ぎの途中の盤面が悪く見えて切り捨てられるが、注ぎ終わった盤面だけを比べればそれが起きない。前者の出所は記録がない。どちらも再生して正しいことを確かめてある。\(N=13\)(329 手)と \(N=14\)(387 手)の手順は、12 色の解を見つけたのと同じ注ぎ単位のビーム探索(幅 \(10^4\) と \(3\cdot10^4\)、同点を崩す乱数の種を変えたもの)で得た。1 個ずつのビーム(1 層あたり \(10^6\) 状態)と解き直しで得ていた 364 手・443 手より、35 手・56 手短い。

\(15\le N\le24\) では組み立てを使う。\(m=\lfloor N/2\rfloor\) とする。色 \(N,N-1,\dots,\lceil N/2\rceil+1\) を 1 色ずつ完成させる。空のレーンが必要になるたびに、2 本のレーンを \([1,\dots,\lceil N/2\rceil]\) と \([1,\dots,m]\) まで掘り、一方を他方へ注ぐ。これでレーン \([1,\dots,\lceil N/2\rceil,m,\dots,1]\) と空のレーンができる。残るのは、この形のレーン \(m\) 本と空のレーン 1 本である。これらのレーンの上の層は、色の名前を付け替えると \(m\) 色の初期配置になるので、\(m\) 色の既知の手順をその上で再生できる。残りはビーム探索で解く。こうして得た上界は \(N=24\) でおよそ \(3.4N^2\) で、最短からは確実に遠い。\(N=16\) では、組み立てた手順の後半を 1 層あたり \(10^6\) 状態のビームで解き直し、646 手を 643 手に縮めた。手順の前の方の 12 手区間を SAT で解き直した改善(646 → 635)と、両者に共通する局面(レーンの付け替えは許す)のうち全体が最短になるところでつなげて、632 手を得た。さらに、この解の 32 手の区間ごとに、区間の終わりの局面(レーンの付け替えは許す)へ向かうビーム探索(残りの手数の下界はレーンの割り当てで計る)で解き直し、613 手を得た。注ぎ単位のビーム探索(幅 \(10^4\))も直接 613 手を出し、その 32 手の区間を同じように解き直して 611 手を得た。幅を \(3\cdot10^4\) に広げると、直接 562 手を出した。その 48 手の区間を解き直して 560 手になった。並列版(beam/src/bin/pour.rs)を幅 \(10^5\) で回すと 541 手を出し、その 48 手の区間を解き直して 538 手になった。評価の重みを調べ直すと、幅 \(10^5\) で 525 手を直接出した。\(N=17\) では、注ぎ単位のビーム探索が幅 2,000 で 715 手、幅 \(3\cdot10^4\) で 677 手を直接出した。並列版を幅 \(10^5\) で回すと 657 手、幅 \(2\cdot10^5\) で 650 手、評価の重みを調べ直すと幅 \(10^5\) で 625 手で、組み立て(743 手)より 118 手短い。\(N=18\) では、並列版(幅 \(10^5\))が 757 手を出し、評価の重みを調べ直すと 719 手で、組み立て(863 手)より 144 手短い。\(N=19\) でも 998 手(並列版の幅 \(10^5\) では 900 手、幅 \(2\cdot10^5\) では 883 手、評価の重みを調べ直すと幅 \(10^5\) で 853 手。組み立ては 1004 手)、\(N=20\) では並列版(幅 \(10^5\))が 1027 手(評価の重みを調べ直すと 992 手。同 1157 手)、\(N=21\) では 1302 手(並列版では 1129 手。同 1336 手)、\(N=22\) では並列版が 1355 手(同 1477 手)、\(N=23\) では 1568 手(同 1632 手)、\(N=24\) では 1672 手(同 1873 手)と、組み立てより短い。\(N=15\) では、組み立てた手順の連続する 12 手の区間ごとに、同じ配置(レーンの付け替えは許す)へより短く行けるかを SAT ソルバー(cadical)で調べ、547 手を 536 手に縮めた。別に、組み立てた手順の後半を 1 層あたり \(10^6\) 状態のビームで解き直すと 543 手になった。2 つの改善は手順の別の部分にあるので、つなげて 532 手を得た。その後半をさらに解き直して 531 手になった。その後、注ぎ単位のビーム探索(幅 \(3\cdot10^4\))が、乱数の種を変えた中で最短の 483 手を直接出し、途中の配置から先を解き直して 482 手になった。並列で省メモリに作り直した版(beam/src/bin/pour.rs)を幅 \(10^5\) で回すと 468 手を出し、評価の重みを調べ直す(色の変わり目と散らばりを重く、空きレーンを好み、同点崩しの乱数を広く)と 457 手になった。

8. 結果の前提

定理 1 は 4 節で証明してあり、計算には拠らない。

上界は、再生スクリプトだけに拠る。スクリプトは、初期配置に手を順に適用し、最後の配置を調べる。

6 色と 7 色の下界は、計算機を使った証明である。命題 4、\(J\) の実装の正しさ、探索プログラムの正しさに拠る。\(J\) の実装は、4 色の全状態で正確な距離と照合した。別に Python で書いた第 2 の実装は、4 色と 5 色の 160,834 状態で正確な距離と照合した。探索プログラムは 3 種類の下界で実行し、重なる範囲では同じ結論になった(表 2)。探索プログラムを独立に書き直しての確認はしておらず、4・5 節の証明の形式的な検証もしていない。

9. 未解決の問題

係数. \(1.5\le\liminf T(N)/N^2\) であり、明示的で小さい上からの定数は知られていない。確定した値は \(2\le N\le6\) で \(T(N)=(2N-1)(N-1)\) を満たす。\(N\ge8\) について私たちが知る最良の手順はこれより長い。106, 140, 179, 224, 272 に対して、式の値は 105, 136, 171, 210, 253 である。これらは上界なので、式を否定するものではない。

\(J\) が数えていないもの. 手順の長さは、動く玉の数と、玉を最終位置以外へ置く手の数の和である。後者を仮置きの手と呼ぶ。\(4\le N\le7\) の最短の手順を調べると、仮置きの手はちょうど \((N-1)(N-2)\)、つまり 6, 12, 20, 30 だった。\(J\) が保証するのは 5, 9, 14, 20 である。差は、2 回以上仮置きされる玉(これらの手順では 3 回動く玉が 1, 2, 3, 6 個ある)と、\(J\) が家へ直行できるとみなしている玉から来る。\(J\) は、少なくとも 1 回は仮置きされる玉を数えるが、仮置きの場所には制限がないとみなしている。実際の手順では、あるレーンを空けるとき、その玉は、直前に集めた色の玉が抜けた穴、つまり、あとで空けるレーンの上に仮置きされる。自分の色の家ができる前にそのレーンが空けられると、その玉はもう一度仮置きされる。仮置きの玉がどこで待てるかを数に入れた下界が自然な次の一歩だが、まだ得られていない。

7 色. \(75\le T(7)\le78\) の差を探索だけで埋めるには、これまでの増え方が続くとして、最後に実行した段階の数万倍の状態が要る。

10. コードとデータ

リポジトリ github.com/wand125/colorsort-transpose に、手順、上界・下界とその根拠、探索プログラム、結果を決めた実行のログ、3〜5 節の証明(日本語)がある。データのページに手順の一覧と確かめ方を、再生のページに手順のアニメーションを置いた。

参考文献

  1. M. Szegedy and J. Yu, Rubik Tables and object rearrangement, Int. J. Robotics Research (2022); arXiv:2002.04979.
  2. S. D. Han, N. M. Stiffler, K. E. Bekris and J. Yu, Efficient, high-quality stack rearrangement, IEEE Robotics and Automation Letters 3 (2018), 1608–1615.
  3. Anonymous, web page on matrix transposition with piles, https://piles-five.vercel.app/(2026 年 11 月閲覧).
  4. T. Ito et al., Sorting balls and water: equivalence and computational complexity, FUN 2022; arXiv:2202.09495.