🧩 数独検証アルゴリズム解析

📋 アルゴリズム概要

目的: 9×9の数独ボードが有効かどうかを判定する

制約:

時間計算量: O(1) - 固定サイズ（9×9）のため定数時間

空間計算量: O(1) - 最大81個の要素を格納する定数空間

🎯 視覚的デモンストレーション

現在のセル
同じ行
同じ列
同じ3×3ボックス

🔍 ステップバイステップ解析

1
初期化: 各行、列、3×3ボックス用のSetを作成
rows[9], cols[9], boxes[9] - 各Setで重複チェックを効率化
2
ボードスキャン: 左上から右下へ順次処理
二重ループで全81セルを一度だけ訪問
3
空セルスキップ: '.'の場合は処理をスキップ
計算量を削減し、効率性を向上
4
ボックスインデックス計算: (i // 3) * 3 + (j // 3)
各セルがどの3×3ボックスに属するかを数学的に計算
5
重複チェック: 同じ数字が既に存在するかチェック
Set.has()でO(1)時間での高速検索
6
早期終了 or 継続: 重複があればfalse、なければSetに追加
無効な場合は即座に処理を終了して効率化

💻 コード解析

def isValidSudoku(self, board: List[List[str]]) -> bool:
    # Set初期化 - O(1)空間、各Setは最大9要素
    rows: List[set[str]] = [set() for _ in range(9)]
    cols: List[set[str]] = [set() for _ in range(9)]
    boxes: List[set[str]] = [set() for _ in range(9)]
    
    # 二重ループ - 固定81回の反復
    for i in range(9):
        for j in range(9):
            cell: str = board[i][j]
            
            # 空セルスキップ - 計算量削減
            if cell == '.':
                continue
            
            # 3×3ボックスインデックス - O(1)計算
            box_index: int = (i // 3) * 3 + (j // 3)
            
            # 重複チェック - 各Set.has()はO(1)
            if cell in rows[i] or cell in cols[j] or cell in boxes[box_index]:
                return False  # 早期終了
            
            # Set追加 - 各Set.add()はO(1)
            rows[i].add(cell)
            cols[j].add(cell)
            boxes[box_index].add(cell)
    
    return True

⚡ 性能分析

時間計算量: O(1)

空間計算量: O(1)

最適化ポイント