有効な数独 (LeetCode 36): Python 解答、ボックスインデックス、エッジケース

Valid Sudoku（LeetCode 36）では、一部が埋まった9×9の盤面が与えられ、埋まっているマスが数独のルールに違反していないかを判定します。パズルを解く必要はありません。各行、各列、各3×3ブロックで同じ数字が重複していないことだけを確認します。出現済みの数字を3つのセットで管理しながら1回走査するだけで、O(81)、つまり定数時間で済みます。

問題

盤面は9×9の文字グリッドで、各マスは1から9の数字か、空きマスを表す.です。埋まっているマスが次のルールに従っていればtrueを返します。

• 各行に重複した数字がない。
• 各列に重複した数字がない。
• 各3×3ブロックに重複した数字がない。

盤面は解が存在しなくてもvalidになり得ます。チェックされるのは埋まっているマスだけです。

アプローチ：各ユニットごとに3つのセット

各行、各列、各ブロックについて、出現済みの数字のセットを保持します。埋まっているマスごとに、その数字を3つのセットすべてで確認し、まだなければ追加します。

少し考える必要があるのはブロックのインデックスだけです。行r、列cのマスのブロック番号は(r // 3) * 3 + c // 3です。これはブロックを左から右、上から下へ0から8まで数えたものです。

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True

トレース

行0の列0に5があり、列4にもう一つ5があるとします。最初の5はrows[0]、cols[0]、boxes[0]に追加されます。列4ではch in rows[0]のチェックがtrueになるので、関数はすぐにfalseを返します。同じブロックや同じ列で数字が重複した場合も、残り2つのセットが同様に検出します。

計算量

盤面は常に9×9なので、時間は定数で、81マスの走査です。n×nの盤面に一般化すると、時間はO(n squared)、空間はO(n squared)です。面接官はスケールの仕方をよく聞くので、両方とも伝えましょう。

面接官が聞くバリエーション

ビットマスク版は各セットを整数に置き換えます。mask & (1 << d)で数字をテストし、mask |= 1 << dで記録します。より高速ですが、時間に追われる中ではセット版のほうが正しく書けるので、まずはそちらを書きましょう。

よくある間違い

• 行と列は確認するが、ブロックを忘れる。
• r // 3 + c // 3のような誤ったブロックの式。これでは異なるブロックに同じインデックスが割り当てられる。
• .を数字として扱ってしまい、2つの空きマスを重複と数えてしまう。
• 問題が求めているのは妥当性の確認だけなのに、盤面を解こうとする。

テストすべきエッジケース

面接での説明の仕方

1. ルールを言い換え、解くのではなく検証するだけだと述べる。
2. 3つのユニットを挙げ、それぞれに出現済みセットが必要だと述べる。
3. ブロックのインデックスの式を示し、1つの例で説明する。
4. 1回の走査と早期リターンを書く。
5. 計算量を述べ、求められればビットマスク版を提案する。

公開前に、上記のコードを単純な行・列・ブロックのチェックと、20,000個のランダムな盤面（有効なものも、意図的に壊したものも含む）で照合してテストしました。こうした簡単なランダムチェックは、練習するときの良い習慣です。

関連する練習

計算量の用語についてはBig O チートシートを、次に何を練習すべきかについてはLeetCode Blind 75リストを、練習方法についてはコーディング面接アシスタントガイドをご覧ください。

コードを書きながら、アプローチを声に出して説明しましょう。文字起こしを見れば、書く前に重要な観察を述べたかどうかがわかります。ライブの評価では、AIツールに関する雇用主のルールに従ってください。