Ball-sort transposition

Data

データ

Everything on this page is generated from two sources in the repository: bounds.tsv and the move sequences in solutions/. Machine-readable copies: bounds.json, solutions.json.

このページの内容は、リポジトリの bounds.tsv と solutions/ の手順から作っている。機械で読める形: bounds.json、solutions.json。

Bounds and their sources

上界・下界と根拠

Nlowerupperlower bound fromupper bound from(2N−1)(N−1)
233exactexhaustive searchoptimal solution3
31010exactexhaustive searchoptimal solution10
42121exactexhaustive searchoptimal solution21
53636exactexhaustive searchoptimal solution36
65555exactpruned search with the bound Jsearch restricted by two rules55
77578openpruned search with the bound Jbeam search78
895106openpruned search with the bound Jearlier recorded solution105
9117140openpruned search with the bound Jbeam search136
10145179openpruned search with the bound Jbeam search171
11175224openpruned search with the bound Jbeam search210
12208272opengeneral bound (3N²−N−4)/2earlier recorded solution253
13245329opengeneral bound (3N²−N−4)/2beam search300
14285387opengeneral bound (3N²−N−4)/2beam search351
15328457opengeneral bound (3N²−N−4)/2beam search406
16374525opengeneral bound (3N²−N−4)/2beam search465
17423625opengeneral bound (3N²−N−4)/2beam search528
18475719opengeneral bound (3N²−N−4)/2beam search595
19530853opengeneral bound (3N²−N−4)/2beam search666
20588992opengeneral bound (3N²−N−4)/2beam search741
216491,114opengeneral bound (3N²−N−4)/2beam search820
227131,355opengeneral bound (3N²−N−4)/2beam search903
237801,568opengeneral bound (3N²−N−4)/2beam search990
248501,672opengeneral bound (3N²−N−4)/2beam search1,081
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

Format of a move sequence

手順の書式

Lanes are numbered 0 to N; lane 0 is the one that starts empty. A move is two characters in base 36 (0–9, then a–z): the lane the ball leaves and the lane it enters. A sequence is the moves written one after another. The four-colour solution starts with 10: the top ball of lane 1 goes to lane 0.

レーンには 0 から N の番号を付ける。レーン 0 が最初に空のレーン。1 手は 36 進(0–9、a–z)の 2 文字で、玉が出るレーンと入るレーンを表す。手順はそれを並べた文字列。4 色の手順 の最初の 10 は、レーン 1 の一番上の玉をレーン 0 へ移す手。

The sequences below are in a normal form, so that solutions which differ only by renaming lanes 1 to N, or by swapping moves that use disjoint lanes, are written the same way: the lanes are renamed so that the finished colours appear in increasing order from left to right, and independent moves are put in lexicographic order.

下の手順は正規形で書いてある。レーン 1〜N の番号の付け方だけが違う手順や、使うレーンが重ならない手の順番だけが違う手順は、同じ書き方になる。完成時に色が左から番号順に並ぶようにレーンの番号を付け替え、互いに関係のない手は辞書順に並べている。

Best known move sequences

最良の手順

Loading…

Check it yourself

自分で確かめる

Replaying a sequence needs no special tool. This is the whole check, in Python:

手順の再生に特別な道具は要らない。確認は、Python で書くと次のとおり。

D = "0123456789abcdefghijklmnopqrstuvwxyz"
def check(n, s):
    lanes = [[]] + [list(range(1, n + 1)) for _ in range(n)]
    for i in range(0, len(s), 2):
        a, b = D.index(s[i]), D.index(s[i + 1])
        assert a != b and lanes[a] and len(lanes[b]) < n
        lanes[b].append(lanes[a].pop())
    return all(not l or (len(l) == n and len(set(l)) == 1) for l in lanes)

In the repository, python3 tools/verify_all.py replays every stored sequence and compares the move counts with bounds.tsv. The lower-bound searches are in lowerbound/ (Rust):

リポジトリでは、python3 tools/verify_all.py が保存した手順をすべて再生し、手数を bounds.tsv と突き合わせる。下界の探索は lowerbound/(Rust)にある。

cd lowerbound && cargo build --release
COLORLB_JOINT=1 ./target/release/colorlb check 4      # bound J vs exact distance, all states, N = 4
COLORLB_JOINT=1 ./target/release/colorlb prove 6 55   # no solution with at most 54 moves

Proof logs

証明のログ

Statement示したことStates visitedたどった状態Logログ
T(6) ≥ 54833,372prove6J_54_final.log
T(6) ≥ 554,710,164prove6J_55_final.log
T(7) ≥ 72800,114prove7J_72_final.log
T(7) ≥ 736,755,298prove7J_73_final.log
T(7) ≥ 7449,759,109prove7J_74.log
T(7) ≥ 75329,474,202prove7J_75.log
T(8) ≥ 913,925prove8J_91.log
T(8) ≥ 9233,108prove8J_92.log
T(8) ≥ 93401,839prove8J_93.log
T(8) ≥ 944,849,953prove8J_94.log
T(8) ≥ 9553,114,526prove8J_95.log
T(9) ≥ 11618,272prove9J_116.log
T(9) ≥ 117179,334prove9J_117.log
T(10) ≥ 14495,064prove10J_144.log
T(10) ≥ 1451,115,978prove10J_145.log
T(11) ≥ 175546,790prove11J_175.log

Other files: bounds.tsv, solutions/, the proofs in Japanese, and exact distances for all states with four colours and for a band of states with five (learn/).

そのほかのファイル: bounds.tsv、solutions/、下界の証明(日本語)、4 色の全状態と 5 色の一部の状態の正確な距離(learn/)。