Pythonで数独の盤面が有効かどうかを判定する方法

問題の概要

9×9の数独（Sudoku）盤面が与えられ、その盤面が有効（valid）であるかどうかを判定します。検証対象はすでに数字が埋められているセルのみであり、以下の3つのルールを満たす必要があります。

• 行のルール：各行には数字1〜9が重複なく含まれていること
• 列のルール：各列には数字1〜9が重複なく含まれていること
• ブロックのルール：盤面を区切った9つの3×3サブボックスそれぞれに、数字1〜9が重複なく含まれていること

注意したいのは、盤面が完成していなくてもよいという点です。空欄は無視し、埋まっている数字だけがルールに違反していないかを確認します。

例として、次の数独盤面を考えてみましょう。

この盤面は上記の3つのルールをすべて満たしているため、有効です。

解法のアプローチ

各行・各列・各3×3ブロックについて「すでに出現した数字」を辞書（ハッシュマップ）で管理し、重複が見つかった時点でFalseを返すのが基本的な考え方です。具体的な手順は以下の通りです。

• i を 0〜8 の範囲でループする
  • 空の辞書 row・column・block を作成し、row_cube = 3 × (i // 3)、column_cube = 3 × (i % 3) を計算する
  • j を 0〜8 の範囲でループする
    • board[i][j] が空欄（"."）でなく、かつ row に存在する場合は False を返す
    • row[board[i][j]] = 1 として記録する
    • board[j][i] が空欄でなく、かつ column に存在する場合は False を返す
    • column[board[j][i]] = 1 として記録する
    • rc = row_cube + j // 3、cc = column_cube + j % 3 を計算する
    • board[rc][cc] が空欄でなく、かつ block に存在する場合は False を返す
    • block[board[rc][cc]] = 1 として記録する
• 最後まで重複が見つからなければ True を返す

このアルゴリズムのポイントは、外側のループ変数 i を1つ回すだけで「i 行目」「i 列目」「i 番目の3×3ブロック」を同時に走査できることです。これにより、盤面全体をたった1回の二重ループで効率的に検証できます。

Pythonでの実装例

理解を深めるために、実際の実装を見ていきましょう。

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        for i in range(9):
            row = {}
            column = {}
            block = {}
            row_cube = 3 * (i // 3)
            column_cube = 3 * (i % 3)
            for j in range(9):
                if board[i][j] != '.' and board[i][j] in row:
                    return False
                row[board[i][j]] = 1
                if board[j][i] != '.' and board[j][i] in column:
                    return False
                column[board[j][i]] = 1
                rc = row_cube + j // 3
                cc = column_cube + j % 3
                if board[rc][cc] in block and board[rc][cc] != '.':
                    return False
                block[board[rc][cc]] = 1
        return True

ob1 = Solution()
print(ob1.isValidSudoku([
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]]))

入力

[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

出力

true

計算量の目安

盤面のサイズは固定の9×9（81マス）なので、実行時間は常に一定、つまり O(1) とみなせます。n×n の盤面に一般化した場合には、時間計算量・空間計算量ともに O(n²) となります。