Ball-sort transposition

Turning rows into columns: shortest solutions of a ball-sort puzzle

ヨコをタテに:色そろえパズルの最短手数

There are N colours, N balls of each, and N+1 lanes that hold N balls. At the start one lane is empty and every other lane holds the colours 1, 2, …, N from bottom to top, so each row has one colour. A move takes the top ball of a lane to any lane with room. How many moves does it take to make every lane one colour?

色は N 色、玉は各色 N 個、レーンは N+1 本で、1 本に N 個入る。最初は 1 本が空で、残りのレーンはどれも下から色 1, 2, …, N の順。つまり横の段ごとに 1 色になっている。1 手で、あるレーンの一番上の玉を、空きのある別のレーンへ移す。どのレーンも 1 色にするには、最少で何手かかるか。

Starting position and a finished position for four colours start21 moves
Four colours: the start, and one of the positions the shortest solutions end in.
4 色の初期配置と、最短の手順が行き着く完成形の 1 つ。

Results

結果

Write T(N) for the minimum number of moves.

最少手数を T(N) と書く。

Exact values
確定した値
T(6) = 55

T(2), …, T(6) = 3, 10, 21, 36, 55. The values up to five colours were known from exhaustive search. Six colours is settled here: a 55-move solution exists, and a pruned search over 4.7 million states shows that 54 moves are not enough.

T(2), …, T(6) = 3, 10, 21, 36, 55。5 色までは全探索による既知の値。6 色はここで確定した。55 手の手順があり、54 手以内では解けないことを 471 万状態の枝刈り全探索で示した。

Every N
一般の N
T(N) ≥ (3N² − N − 4)/2

Every ball but one must move, and about half of the balls must move at least twice. The bound is proved by hand; three versions of it, each stronger than the last, are checked against exact distances on all 37 million states for four colours.

1 個を除くすべての玉は動かす必要があり、およそ半数の玉は 2 回以上動かす必要がある。証明は手で書いたもので、段階的に強くした 3 つの下界を、4 色の全 3,745 万状態で正確な距離と照合した。

Seven colours
7 色
75 ≤ T(7) ≤ 78

The upper bound is an explicit solution. The lower bound comes from the same pruned search; each further move multiplies the number of states by about eight.

上界は実際の手順。下界は同じ枝刈り全探索による。証明する手数を 1 上げるごとに、状態数はおよそ 8 倍になる。

Up to 24 colours
24 色まで
T(24) ≤ 1,873

Each upper bound is a stored move sequence that a short script replays from the start. For 13 colours and more the sequences come from a construction and are far from the lower bound.

上界はどれも保存した手順で、短いスクリプトが最初から再生して確かめる。13 色以上の手順は組み立てによるもので、下界とはまだ大きく離れている。

Bounds

上界と下界

Nlowerupper(2N−1)(N−1)
233exact3
31010exact10
42121exact21
53636exact36
65555exact55
77578open78
895106open105
9117140open136
10145179open171
11175224open210
12208272open253
13245329open300
14285387open351
15328457open406
16374525open465
17423625open528
18475719open595
19530853open666
20588992open741
216491,114open820
227131,355open903
237801,568open990
248501,672open1,081
N下界上界(2N−1)(N−1)
233確定3
31010確定10
42121確定21
53636確定36
65555確定55
77578未確定78
895106未確定105
9117140未確定136
10145179未確定171
11175224未確定210
12208272未確定253
13245329未確定300
14285387未確定351
15328457未確定406
16374525未確定465
17423625未確定528
18475719未確定595
19530853未確定666
20588992未確定741
216491,114未確定820
227131,355未確定903
237801,568未確定990
248501,672未確定1,081
The last column is the quadratic through the exact values. It is a guide, not a claim: for eight colours and more, the best known solutions are longer. 右端の列は、確定した値を通る 2 次式。目安であって主張ではない。8 色以上では、見つかっている最良の手順はこれより長い。

Sources, move sequences and logs are on the data page.

根拠・手順・ログはデータのページにある。

What the results depend on

結果の前提

The upper bounds depend only on a short replay script. The lower bounds for six and seven colours are computer-assisted: they rest on the written proof that the bound J never exceeds the true distance, on the check of J against exact distances for four colours, and on the correctness of one search program. That program has not been reimplemented independently.

上界は、短い再生スクリプトだけに拠る。6 色と 7 色の下界は計算機を使った証明で、下界 J が正確な距離を超えないことの証明(文章)、4 色での J と正確な距離の照合、そして 1 つの探索プログラムの正しさに拠る。このプログラムを独立に書き直しての確認は、まだしていない。

It is known that T(N) grows like N² (Szegedy and Yu). The constant is open: the lower bound gives 1.5.

T(N) が N² に比例して増えることは知られている(Szegedy と Yu)。係数は未解決で、下界からは 1.5 が出る。