n クイーン問題をバックトラッキングで解く：Hello Algo の行ごと配置戦略・対角線枝刈り・計算量解析

2026-09-07 16:07:26作者：董灵辛Dennis

本稿は『Hello Algo（ja 版）』のバックトラッキング章に収録される n クイーン問題 を題材に、問題の定式化、行ごとの配置戦略、列・対角線の枝刈り技法、実装の詳細と計算量解析を体系的に解説する技術ガイドです。読み終えると、n × n 盤上でクイーン同士が互いに攻撃し合わない全配置を求めるバックトラッキング解法を理解し、Python 実装や Java 実装などのリポジトリコードを読んで自分で実行・拡張できるようになります。

問題の定義と解法の見通し

n クイーン問題は次のように定義されます（n_queens_problem.md に基づく）。

チェスのルール上、クイーンは同じ行・同じ列・同じ斜線上にある駒を攻撃できます。
$n$ 個のクイーンと $n \times n$ サイズの盤面が与えられたとき、すべてのクイーンが互いに攻撃し合わない配置を求めます。

下図のように、 $n = 4$ のときは 2 つの解が見つかります。バックトラッキングの観点では、 $n \times n$ 盤には合計 $n^{2}$ 個のマスがあり、これがすべての選択肢 choices を与えます。クイーンを 1 つずつ配置していく過程で盤面の状態は絶えず変化し、その各時点の盤面が状態 state です。

3 つの制約条件：行・列・2 種類の対角線

本問題の制約は以下の 3 つに整理できます。

行制約：複数のクイーンを同じ行に置けない
列制約：複数のクイーンを同じ列に置けない
対角線制約：複数のクイーンを同じ対角線上に置けない

対角線には 主対角線 \（左上→右下） と 副対角線 /（右上→左下） の 2 種類があり、それぞれ独立に制約として扱う必要があります。

行ごとの配置戦略

クイーンの数と盤面の行数はいずれも $n$ です。すると次の推論が簡単に得られます。

盤面の各行にはクイーンを 1 つだけ配置できる

つまり、最初の行から始めて各行に 1 つのクイーンを配置し、最後の行まで進む「行ごとの配置戦略」を採用できます。

下図は 4 クイーン問題における行ごとの配置過程です。図の大きさの都合上、1 行目の検索分岐のうち 1 つだけを展開し、列制約と対角線制約を満たさない案をすべて枝刈り（Omitted）しています。

本質的に、行ごとの配置戦略はそれ自体が枝刈りとして機能します。同じ行に複数のクイーンが現れる探索分岐をすべて回避できるため、探索空間を先に 1 次元ぶん削減できます。ここまでで行制約は構造的に解決済みとなるため、残るは列制約と対角線制約の扱いです。

列制約と対角線制約の枝刈り

列の記録：配列 `cols`

列制約を満たすために、長さ $n$ のブール配列 cols を用いて各列にクイーンがあるかどうかを記録します。配置を決めるたびに cols[col] を検査して、既にクイーンが存在する列を枝刈りし、バックトラッキングの過程で cols の状態を動的に更新（True 化・復元）します。

!!! tip "インデックスの向きに注意" 盤面の原点は左上にあり、行インデックスは上から下へ、列インデックスは左から右へ増加します。以降の式はすべてこの座標系を前提としています。

対角線の数学的性質：主対角線は `row - col` 一定、副対角線は `row + col` 一定

列制約は配列 1 本で簡単に扱えましたが、対角線制約はどう扱えばよいでしょうか。盤面上のあるマスの行・列インデックスを $(r o w, c o l)$ とします。

ある主対角線（\） を選ぶと、その上のすべてのマスで 行インデックスから列インデックスを引いた値 row - col が一定 になります。
すなわち、2 つのマスが $r o w_{1} - c o l_{1} = r o w_{2} - c o l_{2}$ を満たすなら、それらは必ず同じ主対角線上にあります。
同様に、副対角線（/） 上のすべてのマスでは row + col が一定 になります。

この性質を利用し、主対角線用の配列 diags1（インデックスを $r o w - c o l$ に対応付け）と、副対角線用の配列 diags2（インデックスを $r o w + c o l$ に対応付け）によって、各対角線にクイーンがあるかどうかを $O (1)$ で記録・検査できます。

なお、配列のインデックスは 0 以上でなければならないため、 $r o w - c o l$ が負になるケースに注意が必要です。実装では「 $r o w - c o l$ 」をそのまま使わず、オフセットとして $n - 1$ を加算し、diag1 = row - col + n - 1 としてから diags1 を引いています（後述のコード実装を参照）。

コード実装：状態と 3 つの制約配列の初期化

配列サイズの設計

$n$ 次正方行列では、次の範囲・本数になります。

$r o w - c o l$ の範囲は $[- n + 1, n - 1]$ （全部で $2 n - 1$ 通り）
$r o w + c o l$ の範囲は $[0, 2 n - 2]$ （全部で $2 n - 1$ 通り）

したがって主対角線・副対角線の本数はいずれも $2 n - 1$ 本であり、配列 diags1・diags2 の長さもともに $2 n - 1$ とします。一方、列の本数は $n$ なので cols の長さは $n$ です。これは Python 実装の n_queens() 内でも確認できます。

Python による完全な実装例

リポジトリの n_queens.py を要約した実装は次のとおりです。盤面上で "Q" はクイーン、"#" は空きマスを表します。

def backtrack(
    row: int,
    n: int,
    state: list[list[str]],
    res: list[list[list[str]]],
    cols: list[bool],
    diags1: list[bool],
    diags2: list[bool],
):
    """回溯算法：n 皇后（バックトラッキングで n クイーンを解く）"""
    # 全行の配置が完了したら解を記録する
    if row == n:
        res.append([list(row) for row in state])
        return
    # すべての列を走査する
    for col in range(n):
        # このマスに対応する主対角線と副対角線を計算する
        diag1 = row - col + n - 1  # 主対角線（row - col 一定、負値対策に n-1 を加算）
        diag2 = row + col          # 副対角線（row + col 一定）
        # 枝刈り：このマスの列・主対角線・副対角線にクイーンが存在してはならない
        if not cols[col] and not diags1[diag1] and not diags2[diag2]:
            # 試行：このマスにクイーンを置く
            state[row][col] = "Q"
            cols[col] = diags1[diag1] = diags2[diag2] = True
            # 次の行に配置を進める
            backtrack(row + 1, n, state, res, cols, diags1, diags2)
            # 回退：このマスを空きマスに戻す
            state[row][col] = "#"
            cols[col] = diags1[diag1] = diags2[diag2] = False


def n_queens(n: int) -> list[list[list[str]]]:
    """n クイーンを解く"""
    # n*n の盤面を初期化する
    state = [["#" for _ in range(n)] for _ in range(n)]
    cols = [False] * n                    # 列にクイーンがあるかを記録
    diags1 = [False] * (2 * n - 1)        # 主対角線にクイーンがあるかを記録
    diags2 = [False] * (2 * n - 1)        # 副対角線にクイーンがあるかを記録
    res = []
    backtrack(0, n, state, res, cols, diags1, diags2)
    return res

実装の要点

この実装は、バックトラッキングの定石である「試行 → 再帰 → 回退」の 3 段階をそのままなぞっています。

終了条件（解の記録）：row == n に達したとき、すべての行にクイーンが 1 つずつ置かれたことを意味します。state を行ごとにコピーして res へ追加します。参照をそのまま追加すると、後続の回退操作で記録済みの解まで書き換わってしまうため、必ず複製を取ります（Python では [list(row) for row in state]、Java では二重 ArrayList の再生成、Go では copy による複製として表現されています）。
ループで全列を試行：for col in range(n) により、現在の行の全マスを選択肢とします。
3 条件の同時検査と枝刈り：not cols[col] and not diags1[diag1] and not diags2[diag2] が成り立つマスだけにクイーンを置きます。
状態の更新と再帰：盤面マスを "Q" に変え、3 つの制約配列の該当要素をすべて True にしてから row + 1 で再帰します。
回退（バックトラッキングの中核）：再帰から戻ったらマスを "#" に戻し、制約配列をすべて False に復元してから次の列の試行へ進みます。

言語別の実装

このアルゴリズムはリポジトリ内の主要言語すべてに移植されており、ロジックは共通です。主な実装は次のとおりです。

言語	ファイルパス
Python	codes/python/chapter_backtracking/n_queens.py
Java	codes/java/chapter_backtracking/n_queens.java
C++	codes/cpp/chapter_backtracking/n_queens.cpp
C	codes/c/chapter_backtracking/n_queens.c
Go	codes/go/chapter_backtracking/n_queens.go
日本語版一式	ja/codes/（各言語の `chapter_backtracking/n_queens.*`）

たとえば Java 実装では boolean[] cols、boolean[] diags1、boolean[] diags2 をフィールド渡しし、state.get(row).set(col, "Q") と state.get(row).set(col, "#") で試行と回退を行っています。また C 実装は char state[MAX_SIZE][MAX_SIZE] のような固定サイズ配列で盤面を表現し、解を動的確保した char*** にコピーするなど、言語ごとのメモリ管理スタイルの違いも比較して学べます。さらに Python Tutor 版では、このコードをステップ実行して各再帰時点の盤面と制約配列の変化を可視化できます。

実行例と検証

各実装のドライバコード（main 関数）は共通して $n = 4$ を解き、解の個数と各盤面を出力します。たとえば Python 版の実行結果は次のとおりです。

输入棋盘长宽为 4（入力された盤面サイズは 4）
皇后放置方案共有 2 种（クイーンの配置パターンは全部で 2 通り）
--------------------
['#', 'Q', '#', '#']
['#', '#', '#', 'Q']
['Q', '#', '#', '#']
['#', '#', 'Q', '#']
--------------------
['#', '#', 'Q', '#']
['Q', '#', '#', '#']
['#', '#', '#', 'Q']
['#', 'Q', '#', '#']

出力された 2 つの盤面は、冒頭の図に示した 4 クイーン問題の 2 解と一致します。 $n = 4$ のような小さな盤面では出力が少なく手計算で検証できますが、 $n = 8$ では解が 92 通りになることでも知られており、ドライバコードの n を書き換えることで挙動を確認できます。

計算量解析

最後に、この解法の時間計算量と空間計算量を整理します。

時間計算量： $O(n! \cdot n^2)$

行ごとに $n$ 回配置を試行し、列制約を考慮すると、1 行目から最終行までの選択肢はそれぞれ $n,\ n-1,\ \dots,\ 2,\ 1$ 個となります（同じ列には二度クイーンを置けないため、次の行では使える列が 1 つずつ減ります）。したがって探索の枝数は $O (n!)$ です。さらに解を記録する際には行列 state をコピーして res に追加する必要があり、このコピー操作に $O (n^{2})$ 時間を要します。よって全体の時間計算量は $O(n! \cdot n^2)$ です。

なお実際には、対角線制約による枝刈りが探索空間を大きく縮小するため、探索効率はしばしば上記の漸近上界よりも良くなります。 $O (n!)$ は列制約だけを考慮した上界であり、対角線制約によって多くの分岐が早期に打ち切られる点に注意してください。

空間計算量： $O (n^{2})$

盤面 state は $O (n^{2})$ の空間を使用します。
制約配列 cols、diags1、diags2 はそれぞれ $O (n)$ 、 $O (2 n - 1) = O (n)$ 、 $O (n)$ の空間を使用します。
最大再帰深さは $n$ であり、再帰呼び出しのスタックフレーム空間として $O (n)$ を使用します。

全体では最大オーダーの項が盤面の $O (n^{2})$ であるため、空間計算量は $O (n^{2})$ となります。

まとめと関連トピック

n クイーン問題は、「行ごとの配置戦略」で行制約を構造的に解決し、「配列 cols・diags1・diags2」と対角線の不変量（ $r o w - c o l$ 、 $r o w + c o l$ ）で列・対角線制約を $O (1)$ 検査に落とし込み、バックトラッキングの試行と回退で全解を列挙する、という 3 層の設計から成る代表的な探索問題です。状態 state・選択肢 choices・制約・枝刈りというバックトラッキングの基本要素がすべて含まれており、次に挙げる章の内容と合わせて学ぶと理解が深まります。