世の中には、管に入ったボールを移動させるゲームがある。

今回は、以下のルールのゲームを扱う。

4個の管が並んでいる
初期状態では、そのうち左の3個の管に、ボールが4個ずつ入っている
ボールは3色が4個ずつある
1回の移動では、それぞれの管に入っているボールのうち、一番上にある1個のみを動かせる
ボールの移動先の管は、入っているボールが3個以下かつ一番上のボールは移動するボールと同じ色である管に限る (空の管も、入っているボールが0個、かつ一番上のボールは存在しないので、この条件を満たす)
ボールが3個の管にのみ入っており、それぞれの管には同じ色のボールしか入っていない状態にできればクリア (ボールが入っている管、および入っているボールの色はどれでもよい)

このゲームについて、以下の疑問に答える。

状態数はどのくらいあるか？
任意の初期状態からクリアできるか？

状態数はどのくらいあるか？

初期状態

初期状態は、「ボールを左の3個の管に4個ずつ入れる」ということは共通であり、色をどうするかのみを考えればよい。
この状態数は、同じものが4個ずつ3組ある重複順列なので、

\frac{12!}{4! 4! 4!} = 34,650

通りである。

全状態

(初期状態を含む) 全状態の状態数は、

それぞれの管にボールを何個入れるか
ボールを入れる数を決めたときの、色の配置

を考えることで求めることが出来る。

「それぞれの管にボールを何個入れるか」は、4個の候補から12個を選ぶ重複組み合わせ…と考えると、1個の管に5個以上のボールが入る組み合わせも入ってしまい、失敗する。
今回は、それぞれの管にボールではなく「空きの空間」を何個入れるかを考えると、空きは4個しかないので、1個の管に5個以上入ることはなく、うまくいく。
これは4個の候補から4個を選ぶ重複組み合わせ、すなわち4個のモノと3個の仕切りの重複順列である。

「ボールを入れる数を決めたときの、色の配置」は、初期状態と同様の重複順列である。

よって、この状態数は

\frac{7!}{4! 3!} \times \frac{12!}{4! 4! 4!} = 1,212,750

通りである。
この程度の状態数であれば、現代のパソコン程度の計算機で数秒以内に探索しきれることが期待できる。

任意の初期状態からクリアできるか？

クリア状態同士の変換

まず、クリア状態 (3個の管にそれぞれ同じ色のボールが4個ずつ入っていて、残りの1個の管が空の状態) から任意の別のクリア状態にできることを確認する。

4個のボールを連続で動かせばいいので、ボールが入っている管を1個選び、その管に入っているボールを全て空の管に移すことはできる。
よって、4個のボールをひとかたまりとして考えることができる。

そして、この操作を繰り返すことで、ABC- → -BCA → B-CA → BAC- のようにして任意の管のペアに入っているボール (またはボール「なし」) を入れ替えることができる。
この入れ替えを繰り返すことで、任意のクリア状態から任意の別のクリア状態にできる。

クリア状態からの逆算

クリア状態から任意の別のクリア状態にはできることがわかったので、最終的にある1種類のクリア状態にする、と考えてよい。
このクリア状態から逆算することで、クリア状態にできる状態をすべて求めることができる。

逆算においてボールを移動できる条件は、

移動元の筒では、ボールが1個だけか、上2個のボールの色が同じである
移動先の筒では、ボールが3個以下である

である。
この条件を用いて、幅優先探索を行う Python プログラムを実装した。

start_puttern = "rrrr|gggg|bbbb|"

q_start = 0
q = [start_puttern]
visited = {start_puttern}

while q_start < len(q):
    cur = q[q_start]
    q_start += 1
    cur_status = cur.split("|")
    for move_from in range(len(cur_status)):
        from_status = cur_status[move_from]
        if len(from_status) > 0 and (len(from_status) == 1 or from_status[0] == from_status[1]):
            for move_to in range(len(cur_status)):
                if move_to != move_from and len(cur_status[move_to]) < 4:
                    new_status = [e for e in cur_status]
                    new_status[move_to] = new_status[move_from][0] + new_status[move_to]
                    new_status[move_from] = new_status[move_from][1:]
                    new_status_str = "|".join(new_status)
                    if new_status_str not in visited:
                        q.append(new_status_str)
                        visited.add(new_status_str)

init_putterns = [e for e in q if e[-1] == "|"]

print("all putterns: %d" % len(q))
print("initial putterns: %d" % len(init_putterns))

このプログラムを実行すると、約2秒で以下の結果が得られた。
これは、それぞれ全状態のうちクリア状態にできる状態の数と、初期状態のうちクリア状態にできる状態の数を表している。(それぞれクリア状態の数を含む)

all putterns: 801396
initial putterns: 26514

先ほど求めた状態数からこの数を引くと、全状態のうち 411,354 通り (34%) が、初期状態のうち 8,136 通り (23%) がクリア状態にできない (クリア不可能な) 状態であることがわかる。

結論

今回考えるゲームで考えられる全状態の数は約120万通りであり、現代の通常のパソコン程度の計算機で数秒以内に探索を行うことができる。
考えられる初期状態のうち、約4分の1がクリア不可能な配置である。

今回はクリアできる初期状態の特徴や条件については考察を行っていないが、クリアできる初期状態をクリアした状態から逆算して求め、その中から選ぶことで、クリアできる初期状態からゲームを開始することができるだろう。

とはいえ、IchigoJam などの性能が低い計算機で処理を行う場合、探索を行うのは処理時間的にもメモリ容量的にも難しい可能性がある。
初期状態からクリアできるかを効率よく判定する方法の確立は、今後の課題としたい。
※IchigoJamはjig.jpの登録商標です。