バックトラッキング（backtracking）とは？仕組み・コード・例題をわかりやすく解説

バックトラッキングが解く問題

ルールを満たすすべての配置、またはそのうちの1つを求める問題があります。たとえば、互いに攻撃し合わないように8つのクイーンを置く、数独の盤面を埋める、合計が目標値になる集合の部分集合をすべて列挙する、文字列を辞書の単語に分割するすべての方法を見つける、といったものです。うまい公式はなく、探索するしかありません。完成した組み合わせをやみくもにすべて試すのは遅すぎますが、ほとんどの部分的な組み合わせは、いくつかの選択をした時点ですでに無効です。

バックトラッキングは、選択のたびにルールを確認します。部分解がルールに反すると、探索木のその枝全体を一度に放棄し、戻って次の選択肢を試します。

考え方を言葉で説明すると

1. 現在の部分解が完成していれば、記録します。
2. そうでなければ、次に取りうる各選択について、その選択が許されるなら、それを実行します（選ぶ）。
3. 再帰して、解をさらに延ばします（探索する）。
4. 選択を取り消して、次の選択肢が同じ状態から始まるようにします（選択を戻す）。

探索空間は木になります。根が空の解で、各レベルが選択を1つ加え、葉が完成した候補です。バックトラッキングはこの木に対する深さ優先探索で、枝刈りとは、解を含みえない部分木を切り落とすことです。

例題：4-Queens

4 × 4 の盤面に4つのクイーンを、1行に1つずつ、どの2つも同じ列や斜めに並ばないように置きます。列には 0 から 3 までの番号を付けます。

探索を続けると、もう1つの解 2, 0, 3, 1 が見つかります。これは最初の解の鏡像です。

Pythonでの実装

使用済みの列と斜めを集合で保持すると、安全確認が 1 回あたり O(1) になります。一方の斜めでは row - col が一定で、もう一方の斜めでは row + col が一定です。

def solve_n_queens(n):
    solutions, cols = [], []
    used_cols, diag1, diag2 = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(cols.copy())   # copy, not the live list
            return
        for col in range(n):
            if col in used_cols or row - col in diag1 or row + col in diag2:
                continue                    # prune: square is attacked
            cols.append(col)                # choose
            used_cols.add(col); diag1.add(row - col); diag2.add(row + col)
            place(row + 1)                  # explore
            cols.pop()                      # unchoose
            used_cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    place(0)
    return solutions

print(solve_n_queens(4))       # [[1, 3, 0, 2], [2, 0, 3, 1]]
print(len(solve_n_queens(8)))  # 92

同じテンプレートで、すべての部分集合とすべての順列を生成できます。

def subsets(items):
    result, current = [], []

    def go(i):
        if i == len(items):
            result.append(current.copy())
            return
        current.append(items[i]); go(i + 1); current.pop()   # take items[i]
        go(i + 1)                                            # skip items[i]

    go(0)
    return result

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def go():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; current.append(x)
                go()
                used[i] = False; current.pop()

    go()
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

単純な部分集合や順列なら、実際のコードでは itertools.combinations と itertools.permutations のほうが高速です。問題固有のルールで枝刈りしたいときに、自分でバックトラッキングを書きます。

時間計算量と空間計算量

バックトラッキングは、出力の大きさを下回ることはできません。n! 通りの順列を列挙しなければならないなら、少なくとも n! ステップが必要です。枝刈りが役立つのは、何も生み出さない枝を飛ばすことだけです。

バリエーションとよくある間違い

• 戻し忘れ：再帰呼び出しの後に状態を元に戻さないと、後の枝に古い選択が残ったままになります。
• 変更される側のリストを追加してしまう：result.append(current) は、後で変更される参照を保存します。current.copy() を追加してください。
• 入力に重複がある場合：項目をソートし、同じ深さで直前の項目と等しい項目を読み飛ばすと、重複した部分集合や順列を避けられます。
• 最初の解で止める：解が1つで足りる場合（数独ソルバーなど）は、再帰から True を返し、ループも止めます。
• 順序の工夫：最も制約が厳しい選択から試します（数独なら、候補が最も少ない空きマス）。木が劇的に小さくなることがよくあります。

使う場面と実世界での用途

• 制約充足問題：数独、クロスワード、地図の彩色、時間割や試験日程の作成。
• SATソルバーやPrologのような論理エンジンは、強力な枝刈りを備えたバックトラッキング探索を土台にしています。
• Pythonの re を含む多くの言語の正規表現エンジンはバックトラッキングを使っており、悪いパターンは指数的に戻り続けることがあります（「壊滅的バックトラッキング」）。
• コーディング面接の問題：部分集合、順列、組み合わせの和、N-Queens、グリッドでの単語探索、回文分割、括弧の生成、電話番号の文字の組み合わせ。