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。
| N | lower | upper | lower bound from | upper bound from | (2N−1)(N−1) | |
|---|---|---|---|---|---|---|
| 2 | 3 | 3 | exact | exhaustive search | optimal solution | 3 |
| 3 | 10 | 10 | exact | exhaustive search | optimal solution | 10 |
| 4 | 21 | 21 | exact | exhaustive search | optimal solution | 21 |
| 5 | 36 | 36 | exact | exhaustive search | optimal solution | 36 |
| 6 | 55 | 55 | exact | pruned search with the bound J | search restricted by two rules | 55 |
| 7 | 75 | 78 | open | pruned search with the bound J | beam search | 78 |
| 8 | 95 | 106 | open | pruned search with the bound J | earlier recorded solution | 105 |
| 9 | 117 | 140 | open | pruned search with the bound J | beam search | 136 |
| 10 | 145 | 179 | open | pruned search with the bound J | beam search | 171 |
| 11 | 175 | 224 | open | pruned search with the bound J | beam search | 210 |
| 12 | 208 | 272 | open | general bound (3N²−N−4)/2 | earlier recorded solution | 253 |
| 13 | 245 | 329 | open | general bound (3N²−N−4)/2 | beam search | 300 |
| 14 | 285 | 387 | open | general bound (3N²−N−4)/2 | beam search | 351 |
| 15 | 328 | 457 | open | general bound (3N²−N−4)/2 | beam search | 406 |
| 16 | 374 | 525 | open | general bound (3N²−N−4)/2 | beam search | 465 |
| 17 | 423 | 625 | open | general bound (3N²−N−4)/2 | beam search | 528 |
| 18 | 475 | 719 | open | general bound (3N²−N−4)/2 | beam search | 595 |
| 19 | 530 | 853 | open | general bound (3N²−N−4)/2 | beam search | 666 |
| 20 | 588 | 992 | open | general bound (3N²−N−4)/2 | beam search | 741 |
| 21 | 649 | 1,114 | open | general bound (3N²−N−4)/2 | beam search | 820 |
| 22 | 713 | 1,355 | open | general bound (3N²−N−4)/2 | beam search | 903 |
| 23 | 780 | 1,568 | open | general bound (3N²−N−4)/2 | beam search | 990 |
| 24 | 850 | 1,672 | open | general bound (3N²−N−4)/2 | beam search | 1,081 |
| N | 下界 | 上界 | 下界の根拠 | 上界の根拠 | (2N−1)(N−1) | |
| 2 | 3 | 3 | 確定 | 全探索 | 最短の手順 | 3 |
| 3 | 10 | 10 | 確定 | 全探索 | 最短の手順 | 10 |
| 4 | 21 | 21 | 確定 | 全探索 | 最短の手順 | 21 |
| 5 | 36 | 36 | 確定 | 全探索 | 最短の手順 | 36 |
| 6 | 55 | 55 | 確定 | 下界 J を使った枝刈り全探索 | 2 つの規則で制限した探索 | 55 |
| 7 | 75 | 78 | 未確定 | 下界 J を使った枝刈り全探索 | ビーム探索 | 78 |
| 8 | 95 | 106 | 未確定 | 下界 J を使った枝刈り全探索 | 以前から記録されていた手順 | 105 |
| 9 | 117 | 140 | 未確定 | 下界 J を使った枝刈り全探索 | ビーム探索 | 136 |
| 10 | 145 | 179 | 未確定 | 下界 J を使った枝刈り全探索 | ビーム探索 | 171 |
| 11 | 175 | 224 | 未確定 | 下界 J を使った枝刈り全探索 | ビーム探索 | 210 |
| 12 | 208 | 272 | 未確定 | 一般式 (3N²−N−4)/2 | 以前から記録されていた手順 | 253 |
| 13 | 245 | 329 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 300 |
| 14 | 285 | 387 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 351 |
| 15 | 328 | 457 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 406 |
| 16 | 374 | 525 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 465 |
| 17 | 423 | 625 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 528 |
| 18 | 475 | 719 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 595 |
| 19 | 530 | 853 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 666 |
| 20 | 588 | 992 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 741 |
| 21 | 649 | 1,114 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 820 |
| 22 | 713 | 1,355 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 903 |
| 23 | 780 | 1,568 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 990 |
| 24 | 850 | 1,672 | 未確定 | 一般式 (3N²−N−4)/2 | ビーム探索 | 1,081 |
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 の番号の付け方だけが違う手順や、使うレーンが重ならない手の順番だけが違う手順は、同じ書き方になる。完成時に色が左から番号順に並ぶようにレーンの番号を付け替え、互いに関係のない手は辞書順に並べている。
Loading…
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
| Statement示したこと | States visitedたどった状態 | Logログ |
|---|---|---|
| T(6) ≥ 54 | 833,372 | prove6J_54_final.log |
| T(6) ≥ 55 | 4,710,164 | prove6J_55_final.log |
| T(7) ≥ 72 | 800,114 | prove7J_72_final.log |
| T(7) ≥ 73 | 6,755,298 | prove7J_73_final.log |
| T(7) ≥ 74 | 49,759,109 | prove7J_74.log |
| T(7) ≥ 75 | 329,474,202 | prove7J_75.log |
| T(8) ≥ 91 | 3,925 | prove8J_91.log |
| T(8) ≥ 92 | 33,108 | prove8J_92.log |
| T(8) ≥ 93 | 401,839 | prove8J_93.log |
| T(8) ≥ 94 | 4,849,953 | prove8J_94.log |
| T(8) ≥ 95 | 53,114,526 | prove8J_95.log |
| T(9) ≥ 116 | 18,272 | prove9J_116.log |
| T(9) ≥ 117 | 179,334 | prove9J_117.log |
| T(10) ≥ 144 | 95,064 | prove10J_144.log |
| T(10) ≥ 145 | 1,115,978 | prove10J_145.log |
| T(11) ≥ 175 | 546,790 | prove11J_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/)。