ビットマスク初期化プロセス
row_mask: List[int] = [0] * 9 # 各行の使用済み数字ビットマスク
col_mask: List[int] = [0] * 9 # 各列の使用済み数字ビットマスク
box_mask: List[int] = [0] * 9 # 各ボックスの使用済み数字ビットマスク
# 数字 n は (1 << n) ビットで表現 # 例: 数字 5 → 0b100000 (32) for cell in
board: if cell !='.' : num=int(cell) bit=1 << num # ビット位置計算 row_mask[i]
|=bit # OR演算で設定 col_mask[j] |=bit box_mask[box_idx] |=bit
ビットマスクの動作原理
数字1-9のビット表現:
使用例: 行に1,3,7が配置済みの場合
MRV実装の核心部分
# 候補数最小のセルを動的選択
min_candidates = 10 min_idx = -1 min_list = [] for idx, (i, j) in
enumerate(empty_cells): candidates = get_candidates(i, j) if len(candidates) <
min_candidates: min_candidates=len(candidates) min_idx=idx min_list=candidates
if min_candidates == 1: break # 枝刈り: 候補1個なら即決定
if min_candidates == 0: return False # 矛盾検出: 即座にバックトラック
🎯 ビットマスク操作
# 候補計算: O(1) used = row_mask[i] | col_mask[j] | box_mask[b_idx]
candidates = [] for num in range(1, 10): if not (used & (1 << num)):
candidates.append(num)
改善効果: 制約チェック時間 27倍高速化
🧠 MRV戦略
# 候補数最小のセルを優先 # → 探索空間の劇的削減 if len(candidates) <
min_candidates: min_candidates=len(candidates) min_idx=idx
min_list=candidates
改善効果: 平均ケース探索回数を指数的削減
⚡ 動的リスト管理
# 効率的な空セル管理 i, j = empty_cells.pop(min_idx) # ... 探索処理 ...
empty_cells.insert(min_idx, (i, j)) # 復元
改善効果: メモリアクセス効率向上
🌿 枝刈り最適化
# 早期終了条件 if min_candidates == 1: break # 即座に確定 if min_candidates
== 0: return False # 矛盾検出
改善効果: 無駄な計算の完全排除
完全なアルゴリズム処理ステップ
Phase 1: 初期化 O(81)
# ビットマスク配列初期化 row_mask = [0] * 9 # 各行の制約 col_mask = [0] * 9 #
各列の制約 box_mask = [0] * 9 # 各ボックスの制約 empty_cells = [] # 空セルリスト
# 全セル走査して初期状態設定 for i in range(9): for j in range(9): if
board[i][j] == '.': empty_cells.append((i, j)) else: num = int(board[i][j]) bit
= 1 << num row_mask[i] |=bit col_mask[j] |=bit box_mask[get_box_index(i, j)]
|=bit
Phase 2: DFS探索 O(9^k)
# MRV戦略による最適セル選択 min_candidates = 10 min_idx = -1 for idx, (i, j) in
enumerate(empty_cells):
candidates = get_candidates(i, j) # O(9) ビット演算
if len(candidates) < min_candidates: min_candidates=len(candidates) min_idx=idx
min_list=candidates
if min_candidates == 1: break # 即座に確定可能
# 選択されたセルで各候補を試行 i, j = empty_cells.pop(min_idx) for num in
min_list: bit = 1 << num # 配置 board[i][j]=str(num) row_mask[i] |=bit
col_mask[j] |=bit box_mask[b_idx] |=bit if dfs(): # 再帰探索 return True #
バックトラック board[i][j]='.' row_mask[i] ^=bit # XOR演算で元に戻す col_mask[j]
^=bit box_mask[b_idx] ^=bit
Phase 3: 候補計算詳細 O(1)
def get_candidates(i: int, j: int) -> list[int]: b_idx = get_box_index(i, j)
used = row_mask[i] | col_mask[j] | box_mask[b_idx]
candidates = [] for num in range(1, 10):
if not (used & (1 << num)): # ビット演算チェック
candidates.append(num) return candidates
🎯 このアルゴリズムが強力な理由
1️⃣ ビットマスク技術
• 32bit整数1個で9個の数字状態を管理
• OR, AND, XOR演算でO(1)制約チェック
• メモリ効率とCPUキャッシュ効率の両立
2️⃣ MRV戦略
• 候補数最小のセルを優先して分岐因子削減
• 候補1個なら即決定で制約伝播
• 候補0個なら矛盾検出で即座にバックトラック
3️⃣ 動的最適化
• 空セルリストの効率的管理
• 実行時の状態に応じた適応的枝刈り
• XOR演算による高速バックトラック
4️⃣ 総合効果
• Time Limit Exceeded → 高速実行達成
• 平均ケース性能の劇的改善
• LeetCodeの厳しい制限をクリア
# 🎉 最終的な性能達成
時間複雑度: O(9^k) → 実際は大幅削減 (MRV効果)
空間複雑度: O(1) - 27個のint配列のみ
制約チェック: O(27) → O(1) - ビット演算
探索効率: 順次 → 候補最小優先 - MRV戦略
実行結果: Time Limit Exceeded → Accept ✅