ビット操作による高速化アルゴリズムの詳細解説
N-Queens問題は、n×nのチェスボード上にn個のクイーンを配置し、どのクイーンも他のクイーンを攻撃できない状態にする問題です。クイーンは縦・横・斜めに移動できるため、同じ行、列、対角線上に複数のクイーンを配置することはできません。
class Solution:
def totalNQueens(self, n: int) -> int:
"""
N-Queens問題の解の数を求めるメソッド
Args:
n: チェスボードのサイズ (n x n)
Returns:
N-Queens問題の解の総数
"""
def backtrack(row: int, cols: int, diag1: int, diag2: int) -> int:
"""
バックトラッキングを用いてN-Queens問題を解く再帰関数
Args:
row: 現在処理中の行
cols: 列の使用状況をビットマスクで表現
diag1: 左上から右下への対角線の使用状況をビットマスクで表現
diag2: 右上から左下への対角線の使用状況をビットマスクで表現
Returns:
現在の状態から可能な解の数
"""
# 全ての行にクイーンを配置できた場合、解を1つカウント
if row == n:
return 1
count: int = 0
# 現在の行で使用可能な位置を計算（ビット演算で高速化）
available_positions: int = ((1 << n) - 1) & ~(cols | diag1 | diag2)
# 使用可能な各位置にクイーンを配置して再帰的に探索
while available_positions:
# 最下位の1ビットを取得（次に配置可能な位置）
position: int = available_positions & -available_positions
# その位置のビットをクリア
available_positions ^= position
# 次の行で再帰的に探索し、解の数を加算
# diag1とdiag2は対角線の制約を表現（ビットシフトで位置調整）
count += backtrack(
row + 1,
cols | position, # 列の制約を更新
(diag1 | position) << 1, # 左上-右下対角線の制約を更新
(diag2 | position) >> 1 # 右上-左下対角線の制約を更新
)
return count
# 最初の行から探索開始
return backtrack(0, 0, 0, 0)このアルゴリズムの核心は、クイーンの配置制約をビットマスクで効率的に表現することです。
# 1. 利用可能な位置の計算
available_positions = ((1 << n) - 1) & ~(cols | diag1 | diag2)
# ((1 << n) - 1): n個の1からなるマスク (例: n=4 → 1111)
# ~(cols | diag1 | diag2): 制約のある位置を反転
# &: 有効範囲内での利用可能位置
# 2. 最下位ビットの取得
position = available_positions & -available_positions
# -available_positions: 2の補数（ビット反転+1）
# &演算で最下位の1ビットのみを抽出
# 3. ビットのクリア
available_positions ^= position
# XOR演算で該当ビットを0にセット
# 4. 対角線制約の更新
(diag1 | position) << 1 # 左上-右下: 左シフトで次行の制約
(diag2 | position) >> 1 # 右上-左下: 右シフトで次行の制約バックトラッキングの本質的な複雑さ。ただし、ビット演算により定数倍が大幅に改善される。
再帰スタックの深さがNに比例。ビットマスクにより追加のデータ構造が不要。
従来の配列ベースの実装と比較して、10倍から50倍の速度向上が期待できる。