倉庫番をPythonで解かせると何通り調べる？幅優先探索と枝刈りで状態の数を数えてみる

「倉庫番、自分で解くと意外と頭を使うんだよな…」

「これ、プログラムに解かせたらどうなるんだろう？」

箱を押してゴールまで運ぶパズル、倉庫番。ルールは単純なのに、箱が2つ、3つと増えると急に難しくなりますよね。この記事では、倉庫番をPythonの標準機能だけでコンピュータに解かせて、最短手数の答えが出るまでに「何通りの場面」を調べたのかを数えてみます。

使うのは幅優先探索（BFS）と、無駄な探索を減らす枝刈りです。リスト・辞書・集合・関数をひととおり読んだ方が対象です。幅優先探索が初めての方は、先に迷路の最短経路を求める記事を読むと、すっと入れると思います。一緒に見ていきましょう！

Contents

盤面を「集合」で表す
迷路との違いは「状態」の中身
本当に解けているか、再生して確かめる
あり得る場面は何通り？
「もう詰んでいる場面」を調べない（枝刈り）
AIに解かせるときにも効いてくる
よくあるつまずき ⚠️
まとめ

盤面を「集合」で表す

cardboard boxes warehouse / Photo by Ihsan Adityawarman via Pexels

まずは面をデータにします。今回は、壁・ゴール・箱の位置を、それぞれ (行, 列) の集合（set）で持ちます。

from collections import deque

# 倉庫番の面（# 壁、@ 人、$ 箱、. ゴール）
level_text = """
#########
#   #   #
# $   $ #
#  ## @ #
# .  . ##
#########
"""
level = [line for line in level_text.splitlines() if line]

walls, goals, boxes = set(), set(), set()
for r, row in enumerate(level):
    for c, ch in enumerate(row):
        if ch == "#":
            walls.add((r, c))
        elif ch == ".":
            goals.add((r, c))
        elif ch == "$":
            boxes.add((r, c))
        elif ch == "@":
            player = (r, c)

print("箱:", sorted(boxes), "ゴール:", sorted(goals), "人:", player)

実行結果：

箱: [(2, 2), (2, 6)] ゴール: [(4, 2), (4, 5)] 人: (3, 6)

ポイントをまとめるとこんな感じです👇

壁・ゴール・箱は集合で持つ。「このマスは壁？」が in walls の1回で分かる
箱は2つ、ゴールも2つ。人は箱を押せるだけで、引っぱることはできない

迷路との違いは「状態」の中身

迷路なら、調べる単位は「人がどのマスにいるか」だけでした。倉庫番はそうはいきません。同じマスに人が立っていても、箱の位置が違えば、まったく別の場面だからです。

そこで、「人の位置」と「すべての箱の位置」をひとまとめにしたものを状態と呼び、状態を1マスのように扱って幅優先探索をします。やっていることは迷路と同じで、近い（手数の少ない）状態から順に調べていくだけです。

MOVES = {"上": (-1, 0), "下": (1, 0), "左": (0, -1), "右": (0, 1)}


def solve(walls, goals, player, boxes, is_dead=None):
    """幅優先探索で最短手数の解を探す。返り値は (手順, 調べた状態の数)"""
    start = (player, frozenset(boxes))      # 状態 ＝ 人の位置 ＋ 箱の位置の組
    seen = {start}
    queue = deque([(start, "")])
    while queue:
        (pos, bxs), path = queue.popleft()
        if bxs == goals:                    # 全部の箱がゴールに乗った
            return path, len(seen)
        for name, (dr, dc) in MOVES.items():
            nxt = (pos[0] + dr, pos[1] + dc)
            if nxt in walls:
                continue
            new_boxes = bxs
            if nxt in bxs:                  # 箱がある → その先へ押す
                ahead = (nxt[0] + dr, nxt[1] + dc)
                if ahead in walls or ahead in bxs:
                    continue                # 押せない
                if is_dead and is_dead(ahead):
                    continue                # 押したら二度と動かせないマス（あとで使う）
                new_boxes = (bxs - {nxt}) | {ahead}
            state = (nxt, frozenset(new_boxes))
            if state not in seen:
                seen.add(state)
                queue.append((state, path + name))
    return None, len(seen)


path, count = solve(walls, goals, player, boxes)
print("最短手数:", len(path))
print("手順:", path)
print("調べた状態の数:", count)

14手で解けました。そして、答えが出るまでに調べた状態は 1,490 通りです。

ここが重要です👇

状態は (人の位置, frozenset(箱の位置))。集合 seen に入れるので、変更できない frozenset にしている
人が動く先に箱があれば、その先が空いているときだけ押せる
幅優先なので、最初に見つかった答えが最短手数になる

本当に解けているか、再生して確かめる

手順の文字列だけだと、合っているのか分かりにくいですよね。見つけた手順を最初から動かして、最後の盤面を表示してみます。前のコードの続きに書きます。

def show(walls, goals, player, boxes, rows, cols):
    for r in range(rows):
        line = ""
        for c in range(cols):
            p = (r, c)
            if p in walls:
                line += "#"
            elif p in boxes:
                line += "*" if p in goals else "$"   # ゴールに乗った箱は *
            elif p == player:
                line += "@"
            else:
                line += "." if p in goals else " "
        print(line)


# 見つけた手順を最初から再生して、最後の盤面を表示する
pos, bxs = player, set(boxes)
for step in path:
    dr, dc = MOVES[step]
    nxt = (pos[0] + dr, pos[1] + dc)
    if nxt in bxs:
        bxs = (bxs - {nxt}) | {(nxt[0] + dr, nxt[1] + dc)}
    pos = nxt
show(walls, goals, pos, bxs, len(level), len(level[0]))

実行結果（* はゴールに乗った箱）：

#########
#   #   #
#       #
# @##   #
# *  * ##
#########

2つの箱が、どちらもゴールに乗っています。プログラムの答えは、こうして自分で確かめるのが大切です。

あり得る場面は何通り？

1,490 通りは多いのでしょうか、少ないのでしょうか。この面の床は 24 マスです。人がどこにいて、箱がどこにあるか、ざっくりの上限を数えてみます。

from math import comb
floor = sum(ch != "#" for row in level for ch in row)
for n in range(1, 5):
    print(f"箱{n}個: 人の位置 × 箱の置き方 = {floor} × {comb(floor - 1, n)} = {floor * comb(floor - 1, n):,} 通り")

実行結果：

箱1個: 人の位置 × 箱の置き方 = 24 × 23 = 552 通り
箱2個: 人の位置 × 箱の置き方 = 24 × 253 = 6,072 通り
箱3個: 人の位置 × 箱の置き方 = 24 × 1771 = 42,504 通り
箱4個: 人の位置 × 箱の置き方 = 24 × 8855 = 212,520 通り

箱が1つ増えるたびに、場面の数は何倍にもふくらみます。これが、倉庫番が箱の数で急に難しくなる理由です。人が頭の中で全部を試せないのはもちろん、コンピュータでも、大きな面を何も工夫せずに調べ尽くすのは大変です。

「もう詰んでいる場面」を調べない（枝刈り）

倉庫番をやったことがある方なら、「箱を角に押し込んだら終わり」というのを知っていますよね。ゴールではない角に入った箱は、二度と動かせません。その先の場面をいくら調べても、答えにはたどり着かないんです。

そこで、箱を「ゴールではない角」に押す手は、最初から調べないようにします。このように、答えにつながらない枝を切り落とすことを枝刈りと呼びます。

def make_dead_check(walls, goals):
    """ゴールではない「角」のマスか判定する関数を作る"""
    def is_dead(cell):
        if cell in goals:
            return False
        r, c = cell
        up, down = (r - 1, c) in walls, (r + 1, c) in walls
        left, right = (r, c - 1) in walls, (r, c + 1) in walls
        # 上か下が壁で、しかも左か右も壁なら「角」。箱はもう動かせない
        return (up or down) and (left or right)
    return is_dead


dead = make_dead_check(walls, goals)
path2, count2 = solve(walls, goals, player, boxes, is_dead=dead)
print("枝刈りなし:", len(path), "手 /", count, "状態")
print("枝刈りあり:", len(path2), "手 /", count2, "状態")

手数は同じ 14 手のまま、調べた状態は 1,490 から 907 に減りました。答えは変えずに、無駄だけを省けています。

これ、実行せずに答えられますか？「角」の判定に cell in goals の確認がなかったら、どうなるでしょう。ゴールが角にある面では、正解の手まで切り落としてしまい、解けなくなります。枝刈りは、切ってよい理由をきちんと説明できるものだけにするのがコツです。

AIに解かせるときにも効いてくる

いまは「倉庫番を解くPythonのコードを書いて」とAIに頼めば、それらしいコードがすぐに返ってきます。小さな面なら、それで解けることも多いでしょう。

でも面が大きくなって「終わらない」となったとき、原因が状態の数にあると気づけるか、どんな枝刈りなら答えを壊さずに減らせるかを考えられるかは、手順の考え方を知っているかどうかで変わります。動くコードを受け取るだけでなく、「何通り調べているのか」を見積もれるようになっておくと心強いですよ。

よくあるつまずき ⚠️

箱の位置をリストや set のまま状態に入れる：TypeError: unhashable type になります。集合の中に入れるものは、frozenset やタプルのような変更できない型にしましょう
状態に人の位置を入れ忘れる：箱の位置だけで「調べ済み」にすると、人が回り込めば押せた手を見落とし、解ける面を「解けない」と判定してしまいます
枝刈りでゴールの角まで切る：上で見たとおり、正解が消えます。枝刈りを足したら、足す前と同じ手数で解けるかを必ず確かめましょう