Pythonで数独グリッドの有効性を検証するプログラムの実装方法

数独グリッドの有効性検証とは？

ここでは、9×9の数独（スドク）グリッドが有効（valid）であるかどうかを判定するプログラムを扱います。検証の対象となるのは、すでに埋められているセルだけであり、次のルールに従ってチェックを行います。

• 行のルール：各行には、1〜9の数字が重複することなく含まれていること。
• 列のルール：各列にも、1〜9の数字が重複することなく含まれていること。
• ブロックのルール：グリッド内の9つの3×3サブボックス（ブロック）のそれぞれにも、1〜9の数字が重複せずに含まれていること。

例として、次のような数独グリッドを考えてみます。

このグリッドは有効です。

解法のアプローチ

この問題は、行・列・ブロックごとに辞書（ハッシュテーブル）を使って出現済みの数字を記録しながら盤面を走査することで、効率的に解けます。具体的な手順は以下の通りです。

1. i を 0〜8 の範囲でループします。
   • row、column、block という空の辞書を作成し、row_cube = 3 × (i ÷ 3)、column_cube = 3 × (i mod 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 mod 3 を計算します。
     • board[rc][cc] が block に存在し、かつ「.」でない場合は False を返します。
     • block[board[rc][cc]] = 1 として記録します。
2. すべてのチェックを通過したら True を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例（Python）

class Solution(object):
    def isValidSudoku(self, board):
        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

まとめ

このアルゴリズムでは、外側のループで行・列・ブロックの基準位置を決め、内側のループで各マスを一度ずつ走査します。辞書による重複チェックにより、盤面全体をたった1回の走査で検証できるため、時間計算量は O(n²)（n=9 なら定数）に抑えられ、シンプルかつ高速に数独グリッドの妥当性を判定できます。