DSA Interview Prep · レッスン

N-Queensと制約伝播

Q: 「N-Queensと制約伝播」レッスンは無料ですか？

はい。「N-Queensと制約伝播」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。

Q: DSA Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

Q: 「N-Queensと制約伝播」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このDSA Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

列と対角線の集合を使って制約をO(1)で確認しながら、N×Nの盤面にN個のクイーンを配置し、解の個数を数える場合と列挙する場合について学びます。

「N-Queensと制約伝播」はCoddyKit上の無料DSA Interview Prepレッスンです。これはレッスン4/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。

N-Queens 問題

N-Queens 問題（LeetCode 51/52）では、どの2つのクイーンも互いに攻撃できないように、N×N のチェス盤に N 個のクイーンを配置します。クイーンは行、列、および両方の対角線に沿って攻撃できます。N=4 の場合、解はちょうど 2 つあります。古典的な N=8 の場合は 92 個です。これは、制約チェックによって探索空間を大幅に枝刈りする、バックトラッキングの代表的な問題です。

# N-Queens constraints:
# 1. Exactly one queen per row
# 2. No two queens in the same column
# 3. No two queens on the same diagonal (top-left to bottom-right)
# 4. No two queens on the same anti-diagonal (top-right to bottom-left)

# For N=4, the 2 solutions:
sol1 = ['.Q..', '...Q', 'Q...', '..Q.']
sol2 = ['..Q.', 'Q...', '...Q', '.Q..']
print('N=4 solutions:')
for row in sol1: print(row)
print()
for row in sol2: print(row)

各行に1つのクイーンを配置

2つのクイーンが同じ行を共有することはできないため、各行にちょうど1つのクイーンを配置します。バックトラッキングでは、行ごとに再帰し、各行の列を選択します。これにより、クイーンごとに N² 個の選択肢を調べる代わりに、各行で N 個の列だけを調べればよくなります。最初の分岐数は N^N ですが、制約によって大幅に削減されます。再帰の深さは N（行ごとに1レベル）で、分岐係数は最大 N です。

def solve_n_queens(n):
    results = []
    queens = []  # queens[row] = column of queen in that row
    
    def backtrack(row):
        if row == n:
            # Build the board representation
            board = []
            for r in range(n):
                board.append('.' * queens[r] + 'Q' + '.' * (n - queens[r] - 1))
            results.append(board)
            return
        for col in range(n):
            if is_valid(row, col):
                queens.append(col)   # CHOOSE
                backtrack(row + 1)   # EXPLORE
                queens.pop()         # UNCHOOSE
    
    def is_valid(row, col):
        for r, c in enumerate(queens):
            if c == col: return False             # same column
            if abs(row - r) == abs(col - c): return False  # diagonal
        return True
    
    backtrack(0)
    return results

print(len(solve_n_queens(4)), 'solutions for N=4')  # 2
print(len(solve_n_queens(8)), 'solutions for N=8')  # 92

集合による O(1) の制約チェック

配置済みのすべてのクイーンを走査して有効性を確認すると、候補ごとに O(N) かかるため、アルゴリズム全体は最悪の場合 O(N² × N!) になります。3つの集合を管理することで、各チェックを O(1) に削減できます。cols は使用中の列、diag は左上から右下へ向かう対角線の row-col の値、anti_diag は右上から左下へ向かう対角線の row+col の値を保持します。同じ対角線上にあるクイーンは同じ row-col を共有し、同じ反対角線上にあるクイーンは同じ row+col を共有します。

def solve_n_queens_fast(n):
    results = []
    cols = set()       # occupied columns
    diag = set()       # row - col (positive diagonal)
    anti = set()       # row + col (negative diagonal)
    queens = []
    
    def backtrack(row):
        if row == n:
            board = ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
            results.append(board)
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue  # PRUNE: constraint violated
            # CHOOSE
            cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
            backtrack(row + 1)  # EXPLORE
            # UNCHOOSE
            cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
    
    backtrack(0)
    return results

print(len(solve_n_queens_fast(8)))  # 92

対角線の不変条件を理解する

対角線に関する重要な点は、左上から右下へ向かう同じ対角線上のすべてのセルが、同じ row - col の値を持つことです。たとえば、(0,0)、(1,1)、(2,2) はすべて row-col=0 になります。同じ反対角線上のすべてのセルは、同じ row + col を持ちます。(0,2)、(1,1)、(2,0) はすべて row+col=2 です。これらの値が一定であるという不変条件により、O(N) の線形走査ではなく、O(1) の集合検索で対角線の衝突を確認できます。

# Visualise the diagonal invariants for a 4x4 board
n = 4
print('row-col values (same diagonal):')
for r in range(n):
    print([r-c for c in range(n)])

print('row+col values (same anti-diagonal):')
for r in range(n):
    print([r+c for c in range(n)])

# Verify: (0,0) and (2,2) share diag value 0
print('(0,0) diag:', 0-0, '| (2,2) diag:', 2-2)  # both 0
# Verify: (0,2) and (2,0) share anti-diag value 2
print('(0,2) anti:', 0+2, '| (2,0) anti:', 2+0)  # both 2

解の数え上げ：N-Queens II

N-Queens II（LeetCode 52）では、盤面そのものではなく、解の数だけを求めます。そのため、盤面を構築する処理を省略し、カウンターを増やすだけで少し最適化できます。集合の代わりにビットマスクを使えば、数え上げ処理を1回あたりほぼ O(1) までさらに高速化できます。解の数は単調には増加しません。1(N=1)、0(N=2)、0(N=3)、2(N=4)、10(N=5)、4(N=6)、40(N=7)、92(N=8) となります。

def total_n_queens(n):
    count = [0]
    cols = set(); diag = set(); anti = set()
    def backtrack(row):
        if row == n:
            count[0] += 1
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti:
                continue
            cols.add(col); diag.add(row-col); anti.add(row+col)
            backtrack(row + 1)
            cols.remove(col); diag.remove(row-col); anti.remove(row+col)
    backtrack(0)
    return count[0]

for n in range(1, 11):
    print(f'N={n}: {total_n_queens(n)} solutions')

高速化のためのビットマスク N-Queens

非常に大きな N に対しては、ビットマスクによる実装のほうが大幅に高速に動作します。3つの整数をビットマスクとして使います。cols、各行で左シフトする left_diag、各行で右シフトする right_diag です。配置可能な列は ((1<<n)-1) & ~(cols|left_diag|right_diag) で求められます。各配置可能な列を bit = available & -available（最下位のセットビット）で取り出し、再帰します。これにより、ビット演算を使って制約チェック1回あたり O(1) を実現できます。

def total_n_queens_bitmask(n):
    full = (1 << n) - 1  # all n columns set
    count = [0]
    def bt(cols, left_diag, right_diag):
        if cols == full:
            count[0] += 1
            return
        available = full & ~(cols | left_diag | right_diag)
        while available:
            bit = available & -available  # lowest set bit
            available &= available - 1   # remove lowest bit
            bt(cols | bit,
               (left_diag | bit) << 1,
               (right_diag | bit) >> 1)
    bt(0, 0, 0)
    return count[0]

for n in range(1, 13):
    print(f'N={n}: {total_n_queens_bitmask(n)}')

制約伝播の概念

制約伝播は、単純な枝刈りにとどまりません。クイーンを1つ配置したら、後続の行にある不正な位置をすべて直ちに推論して排除します。これは候補ごとに妥当性を確認するよりも積極的な方法で、分岐する前に探索空間をあらかじめ狭めます。最も有名な例は、SATソルバーやSudokuソルバーで使われるアーク整合性です。1つの数字を配置すると、同じ行、列、3×3ボックスにおける選択肢が排除されます。

# Constraint propagation in Sudoku:
# After placing 5 in cell (0,0):
# - Row 0: no other cell can have 5
# - Column 0: no other cell can have 5
# - Box (0,0)-(2,2): no other cell can have 5
# This is propagated BEFORE branching further

# Simple demo: remaining valid columns after placing queens
def remaining_columns(n, queens):
    cols = set(q for q in queens)
    diags = set(r - q for r, q in enumerate(queens))
    anti_diags = set(r + q for r, q in enumerate(queens))
    row = len(queens)
    return [c for c in range(n)
            if c not in cols
            and (row-c) not in diags
            and (row+c) not in anti_diags]

print(remaining_columns(8, [0]))  # valid cols for row 1 after placing col 0 in row 0

Sudokuソルバー

Sudokuは、制約伝播の典型的な問題です。各空きセルで選べる有効な数字は、同じ行、列、3×3ボックスにまだ存在しないものです。バックトラッキングソルバーでは、最初の空きセルを見つけ、有効な数字を1つずつ試して再帰します。矛盾（有効な数字がない空きセル）に達したら、バックトラックします。優れたSudokuソルバーは、バックトラッキングの前に制約伝播（候補メモ）も適用します。

def solve_sudoku(board):
    def is_valid(r, c, num):
        for i in range(9):
            if board[r][i] == num: return False  # row
            if board[i][c] == num: return False  # col
        br, bc = (r//3)*3, (c//3)*3
        for i in range(3):
            for j in range(3):
                if board[br+i][bc+j] == num: return False  # box
        return True
    
    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for d in '123456789':
                        if is_valid(r, c, d):
                            board[r][c] = d
                            if backtrack(): return True
                            board[r][c] = '.'
                    return False  # no valid digit found
        return True  # no empty cells: solved
    
    backtrack()
    return board

# Mini test with a solvable board (simplified)
print('Sudoku solver implemented')

最制約変数ヒューリスティック

制約充足問題における重要な最適化は、次に必ず最も制約の多い変数（有効な選択肢が最も少ないセル）を選ぶことです。Sudokuで、あるセルに有効な数字が1つしかない場合、それをすぐに埋めることは強制される選択であり、バックトラッキングは必要ありません。このようなセルを優先して選ぶと、探索木の深さを大幅に減らせます。これは、AIの制約プログラミングで使われる最小残余値（Minimum Remaining Values; MRV）ヒューリスティックです。

def solve_sudoku_mrv(board):
    '''Find cell with fewest valid choices (MRV heuristic).'''
    def valid_choices(r, c):
        nums = set('123456789')
        for i in range(9):
            nums.discard(board[r][i])
            nums.discard(board[i][c])
        br, bc = (r//3)*3, (c//3)*3
        for i in range(3):
            for j in range(3):
                nums.discard(board[br+i][bc+j])
        return nums
    
    def find_mrv():
        best = (10, -1, -1, set())  # (choices_count, r, c, choices)
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    choices = valid_choices(r, c)
                    if len(choices) < best[0]:
                        best = (len(choices), r, c, choices)
        return best[1], best[2], best[3]
    
    def backtrack():
        r, c, choices = find_mrv()
        if r == -1: return True  # no empty cells
        for d in choices:
            board[r][c] = d
            if backtrack(): return True
            board[r][c] = '.'
        return False
    
    backtrack()
    return board

N-Queensの解の個数表

N-Queensの解の個数は、次のよく知られた数列になります。N=1: 1、N=2: 0、N=3: 0、N=4: 2、N=5: 10、N=6: 4、N=7: 40、N=8: 92、N=9: 352、N=10: 724。既知の閉形式の公式はなく、個数は計算する必要があります。N=27では、約 2.34 × 10^17 個の解が存在します。面接では通常、N ≤ 9 の問題が出されます。指数的な増加を理解すると、より大きなNでビットマスクによる最適化が重要になる理由が分かります。

def count_queens(n):
    '''O(1) per constraint check using sets.'''
    count = [0]
    cols = set(); diag = set(); anti = set()
    def bt(row):
        if row == n: count[0] += 1; return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti: continue
            cols.add(col); diag.add(row-col); anti.add(row+col)
            bt(row+1)
            cols.discard(col); diag.discard(row-col); anti.discard(row+col)
    bt(0)
    return count[0]

sequence = [count_queens(n) for n in range(1, 12)]
print('N-Queens counts:', sequence)
# [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680]

N-Queensの盤面構築

面接官から実際の盤面を返すよう求められた場合（LeetCode 51）、queens リストから各盤面を構築します。queens[r] は行 r にあるクイーンの列を表します。文字列は、各行について '.' * col + 'Q' + '.' * (n - col - 1) のように構築します。この O(n²) の構築は、再帰木の葉（N個すべてのクイーンを配置し終えた時点）でのみ呼び出されるため、全体の計算量には影響しません。

def n_queens_boards(n):
    results = []
    queens = []
    cols = set(); diag = set(); anti = set()
    def build_board():
        return ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
    def bt(row):
        if row == n:
            results.append(build_board())
            return
        for col in range(n):
            if col in cols or (row-col) in diag or (row+col) in anti: continue
            cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
            bt(row+1)
            cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
    bt(0)
    return results

for board in n_queens_boards(4):
    for row in board: print(row)
    print()

理解度チェック

このレッスンで学んだData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、N-Queensでは1行に1つのクイーンを配置し、列、対角線（row-col）、反対角線（row+col）の集合を使って制約をO(1)で確認すること、ビットマスクによって制約チェックをさらに高速化し、ほぼO(1)の操作単位であらゆる配置を探索できること、そして制約伝播（MRVヒューリスティック）によって、最も制約の多い変数を常に次に選び、探索を減らせることを学びました。次は、貪欲法とDPのアプローチを比較し、それぞれをいつ適用するかを学びます。

よくある質問