バックトラックとは（全体像）
バックトラックは、いろいろな候補を順に試していき、うまくいかなくなったら少し戻って、別の候補を試す探索のやり方。最終的に、ありえる組み合わせをもれなく調べられる。
いちばんわかりやすいのが迷路。分かれ道で1つの道を選んで進み、行き止まりに来たら、分かれ道まで戻って別の道を試す。これをくり返せば、いつか出口が見つかる。この「進む→ダメなら戻る」の動きがバックトラックだ。
代表的な使いどころは、8クイーン問題（チェス盤にコマを互いにぶつからないように置く）や数独（空きマスに数字を入れて条件を満たす）。どれも「置いてみて、ダメなら戻して置き直す」で解ける。
詳しく：仕組みと枝刈りだけ覚えれば戦える
ここが記事の心臓部。バックトラックは、次の3つの部品でできている。
バックトラックの仕組み
| 部品 | はたらき |
|---|---|
| 奥まで進む探索（DFS） | 候補を選んでとことん先まで進む |
| 戻る（バックトラック） | 行き詰まったら一歩戻って別の候補を試す |
| 枝刈り（プルーニング） | ダメだと分かった道は早めに切り捨てる |
このうち、効率を大きく左右するのが枝刈り。条件に違反すると分かった時点で、その先を調べずに打ち切る。これでむだな探索が減り、調べる量を大きく減らせる。
代表的な使いどころ
| 問題 | やること |
|---|---|
| 8クイーン問題 | コマを置く→ぶつかったら戻して置き直す |
| 数独 | 数字を入れる→条件違反なら戻してやり直す |
| 迷路探索 | 道を進む→行き止まりなら分かれ道へ戻る |
つまり、バックトラックは「進んで、ダメなら戻って、むだな道は早めに切る」探索。枝刈りがないと、ありえる組み合わせが多い問題では時間が爆発的に増えてしまう（最悪で指数的に増える）。だから枝刈りが効率のカギ、というわけだね。
わかりやすく言い換えると
要するに、バックトラックは「試して、ダメなら戻る」をくり返すやり方だ。
①進む … 候補を1つ選んで先へ進む（迷路で道を選ぶ）
②戻る … 行き止まりなら分かれ道まで戻る（別の道を試す）
③枝刈り … ダメと分かった道は早めに切り捨てる（時間の節約）
ただ全部試すだけでなく、枝刈りでむだを減らすのがコツ。ここが効率の差になる。
試験のツボ
🔴 一番出る：進んで・ダメなら戻る探索
①候補を試し、行き詰まったら戻って別の候補へ
②ありえる組み合わせをもれなく調べる
🔴 次に出る：枝刈りで効率化
①ダメと分かった道は早めに打ち切る
②枝刈りがないと時間が爆発的に増える
🟡 押さえると安定：代表問題と分枝限定法
①代表は8クイーン・数独・迷路探索
②最適解を求める発展形が分枝限定法
よくある間違い
①「バックトラックはふつうの探索（DFS）と同じもの」→ ✗ DFSに「戻る＋枝刈り」を加えて強化したのがバックトラック。
②「枝刈りはしてもしなくても速さは変わらない」→ ✗ 枝刈りがあると探索量が大きく減る。効率のカギになる。
③「バックトラックは必ず一瞬で解ける」→ ✗ 最悪では時間が指数的に増える。だから枝刈りが要る。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（バックトラックの考え方）
バックトラックの考え方に関する次の記述のうち、正しいものはどれか。
- 一度選んだ候補は決して変えず、行き詰まっても最後まで進み続けるやり方とされる
- 候補をいっさい試さず、最初から答えだけを直接書き出すことができる手法だ
- 候補を試し、行き詰まったら一歩戻って別の候補を試すことをくり返すやり方だ
- すべての候補を同時に並べて、戻ることなく一度の操作で答えを決めるものだ
解答は 3 だよ。
バックトラックは候補を試し、行き詰まったら戻って別の候補を試すくり返しなんだ。迷路で行き止まりに来たら引き返すイメージだよ。
選択肢1の「変えず進み続ける」、選択肢2の「試さず直接」、選択肢4の「戻らず一度で」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 行き詰まったら戻る |
| 2 | ✗ | 候補を順に試す |
| 3 | ✓ | 試して、ダメなら戻る |
| 4 | ✗ | 戻りながら順に試す |
オリジナル問題2（枝刈りの役割）
バックトラックの枝刈りに関する次の記述のうち、正しいものはどれか。
- 枝刈りはダメと分かった道を早めに打ち切り、調べる量を大きく減らす工夫のことだ
- 枝刈りは正しい道をわざと打ち切り、答えにたどり着けなくするための操作だ
- 枝刈りをしてもしなくても、調べる量も探索にかかる速さもまったく変わらないとされる
- 枝刈りはすべての道を最後まで調べてから、最後にまとめて消すだけの操作だ
解答は 1 だよ。
枝刈りはダメと分かった道を早めに打ち切って、調べる量を減らす工夫なんだ。これがないと、組み合わせの多い問題では時間が爆発的に増えるよ。
選択肢2の「正しい道を打ち切る」、選択肢3の「変わらない」、選択肢4の「最後にまとめて消す」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | ダメな道を早めに打ち切る |
| 2 | ✗ | 切るのはダメな道 |
| 3 | ✗ | 探索量が大きく減る |
| 4 | ✗ | 途中で早めに切る |
オリジナル問題3（分枝限定法との関係）
バックトラックと分枝限定法の関係に関する次の記述のうち、正しいものはどれか。
- 分枝限定法はバックトラックとまったく無関係で、共通する考え方は一つもない手法だ
- 分枝限定法はバックトラックを発展させ、最適解を求められるようにした手法のことだ
- 分枝限定法はバックトラックより単純で、戻ることも枝刈りもしない探索のことだ
- 分枝限定法は答えがあるか調べるだけで、最適解を求めることはできない手法とされる
解答は 2 だよ。
分枝限定法はバックトラックを発展させて、最適解を求められるようにした手法なんだ。バックトラックは「解の有無や全部の解」、分枝限定法は「いちばんよい解」を探すよ。
選択肢1の「無関係」、選択肢3の「戻らず枝刈りなし」、選択肢4の「最適解を求められない」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | バックトラックの発展形 |
| 2 | ✓ | 最適解を求める発展形 |
| 3 | ✗ | 枝刈りを使う |
| 4 | ✗ | 最適解を求める手法 |
まとめ
押さえどころ
- 🔴 考え方 ＝ 候補を試し、行き詰まったら戻って別の候補へ。進む→ダメなら戻るのくり返し。
- 🔴 枝刈り ＝ ダメな道を早めに打ち切る工夫。これがないと時間が指数的に増える。
- 🟡 代表問題と分枝限定法 ＝ 8クイーン・数独・迷路探索。最適解を求める発展形が分枝限定法。
次に学ぶ
執筆: SikakuQuest編集部