始めに

今回はValid Sudokuに挑戦してみた
難易度はMediumですが、私はタイムアップ(30分)だったので復習して理解を深めていきたい。
間違ったことを言う可能性は大いにあるのでご指摘お願いします🙇‍♂️

問題

この問題は9×9のマス内に同じ数字があるかどうかを判定するプログラムを組むこと。
具体的には以下の条件

各行には1-9の数字が繰り返しなしで含まれていなければならない
各列には1-9の数字が繰り返しなしで含まれていなければならない
3x3の9つのサブボックスには1-9の数字が重複なく含まれていること。

LeetCodeのサンプルの引用

ここから先は上記の例を参考に進めていく

考察

あまり難しく考えず縦列、横列、3×3サブボックスボックスを一つ一つ処理していく。
最初からシンプルかつ効率性を求めると詰みます。私のように...

行、列、サブボックスの配列を用意していき、配列を走査して一意の値を入れていきます。
途中で重複した値があればその時点でFalseにすればいけそうですね

ポイントはこんな感じ

行と列の値はどのようにして取得できるか
行、列、サブボックスを使い一意な値を入れていく
行、列、サブボックスに入れる条件文はどうするか

解法

では一つ一つ見ていこう

行、列、ボックスを格納する配列の作成

縦9マス、横9マス、ボックス9個なので以下のようにする

rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]

set()を使うのは余計なコードが不要になるので使ってます。
通常の配列でも解けますが、今回はこれでやっていく

二重ループで全てのマスを走査

考察で行と列の値はどのようにして取得できるか
という部分があったが単純に二重ループで全てのマスを辿れば良い
さらにコードのiは行、jは列なのでこの方法でそれぞれの値を取れそうですね

for i in range(9):
    for j in range(9):
        # 現在のマスの値を取得
        val = board[i][j]

ちなみに二重ループだと計算量が増えるのでは？と思いがちだが今回の場合は9×9=81回の計算量になるので問題ない

空マスの場合は飛ばす

「.」は空なのでループをスキップする

if val == ".":
    continue

行チェック

現在の値がrowsに存在すればその時点でFalseを返す
存在しなければrowsに追加していく。

if val in rows[i]:
    return False
rows[i].add(val)

列チェック

現在の値がcolsに存在すればその時点でFalseを返す
存在しなければcolsに追加していく。

if val in cols[j]:
    return False
cols[j].add(val)

ボックスチェック

box_indexは現在の値(val)がどのボックスに所属してるかを計算で導いてる。

# valがどこのボックスに所属してるか確認
box_index = (i // 3) * 3 + j // 3
if val in boxes[box_index]:
    return False
boxes[box_index].add(val)

でもここで (i // 3) * 3 + j // 3という計算はなんとなくわかるようでわからない
なんでこれで所属ボックスがわかるのか？
↓の例で考える

0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8

i//3 は、「今、どの段にいるのか？」を計算してる
1段目なら0、2段目なら1、3段目なら2 という答えを返す

ここで、段ごとに3つのボックスがあるので、段の番号（0、1、2）に3を掛けることで、その段の最初のボックスのインデックスを取得できます。

1段目(i//3=0) の最初のボックスのインデックスは0×3=0
2段目(i//3=1) の最初のボックスのインデックスは1×3=3
3段目(i//3=2) の最初のボックスのインデックスは2×3=6

この計算で、探してるボックスのある段の最初(一番左端)の位置が特定できる。
そして、 j//3を足すことで、その段の中で左から何番目のボックスにいるのかを知ることができる

(i // 3) * 3 + j // 3

最後まで重複がなければTrueが返されて完了

以下コード全文

def isValidSudoku(self, board: List[List[str]]) -> bool:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for i in range(9):
        for j in range(9):
            val = board[i][j]

            if val == ".":
                continue

            # 行チェック
            if val in rows[i]:
                return False
            rows[i].add(val)

            # 列チェック
            if val in cols[j]:
                return False
            cols[j].add(val)

            # ボックスチェック
            # valがどこのボックスに所属してるか確認
            box_index = (i // 3) * 3 + j // 3
            if val in boxes[box_index]:
                return False
            boxes[box_index].add(val)

    return True

感想

数独系の問題はある程度慣れが必要な気がした
特にボックスチェック周りのアルゴリズムはちょっとしたコツがありそう
Atcoderにありそうな問題だな〜と
Mediumの壁はまだまだ厚い

LeetCodeのValid Sudoku解いてみた

始めに

問題

考察

解法