https://neetcode.io/problems/valid-sudoku/question?list=neetcode150
9×9 の盤面が、行・列・3×3 の箱それぞれで数字が重複していないかを判定する。空マス . は無視。埋まっている必要も、解ける必要もない。今ある数字が矛盾していないかだけを見る。
まず用語を分けておく。この問題は数えるものが 2 種類あって、そこが混ざると読めなくなる。
| 何か | 個数 | |
|---|---|---|
| マス | 数字が 1 つ入る最小の枠。座標は (r, c) | 81 |
| 箱 | 太線で区切られた 3×3 のかたまり | 9 |
81 マスが 9 個の箱に分かれている（1 箱に 9 マス入っていて 9 × 9 = 81）。以降、番号 0〜8 が出てきたらマスではなく箱を数えている。
やっていることは 1（Contains Duplicate）と同じ「重複判定」。違うのは1 マスの数字が 3 つのグループに同時に属していること。board[4][7] の数字は「4 行目の仲間」であり「7 列目の仲間」であり「箱 5 の仲間」でもある。
1 の重複判定: 数字の行き先は1つ -> Set 1個
この問題: 数字の行き先は3つ -> Set を 行9個 + 列9個 + 箱9個 = 27個
だったら袋を 27 個用意して、1 マスごとに 3 つとも確認するだけでいい。袋は「グループの数」だけ要るのであって、マスの数（81）は要らない。
class Solution {
isValidSudoku(board: string[][]): boolean {
// 袋はマスの数（81）ではなく「グループの数」だけ用意する
// 行 0〜8 それぞれに「その行で見た数字を入れる袋」を1つずつ。計9個
// rows[3] は「3行目に出た数字の集合」という意味になる
const rows = Array.from({ length: 9 }, () => new Set<string>());
const cols = Array.from({ length: 9 }, () => new Set<string>()); // 列は9本なので9個
const boxes = Array.from({ length: 9 }, () => new Set<string>()); // 箱も9個（81個ではない）
// 上の行から順に、各行を左から右へ。81マスをちょうど1回ずつ見る
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const val = board[r][c];
if (val === '.') continue; // 空マスは何も主張していないので飛ばす
// 「今いるマスが、9個の箱のうちどれに入っているか」を求める。
// 箱は9個しかないので b は 0〜8。同じ箱の中の9マスは全員おなじ b になる。
// 座標 (r, c) は81通りあるが、b はそれを9通りに畳んだもの。
// この1行だけが本問の考えどころ（詳しくは下で分解する）
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
// 行・列・箱の3つの袋のどれか1つにでも同じ数字が既にあれば、そこが重複
if (rows[r].has(val) || cols[c].has(val) || boxes[b].has(val)) return false;
// なければ3つの袋すべてに登録して次のマスへ
rows[r].add(val);
cols[c].add(val);
boxes[b].add(val);
}
}
// 81マス見終わって一度もぶつからなかった = 有効な盤面
return true;
}
}
rows[0] の中身は「1 個の Set」
rows は Set が 9 個入った配列。rows[0] はその 1 個目の Set そのもの。配列のマス 1 つに、Set が丸ごと 1 個ずつ入っている（入れ子）。
rows = [ Set{} , Set{} , Set{} , Set{} , Set{} , Set{} , Set{} , Set{} , Set{} ]
↑0 ↑1 ↑2 ↑3 ↑4 ↑5 ↑6 ↑7 ↑8
0行目用 1行目用 8行目用
盤面を進むと、それぞれの袋が独立に育っていく:
rows[0] = Set{ "5", "3", "7" } 0行目でここまでに見た数字
rows[1] = Set{ "6", "1", "9", "5" } 1行目でここまでに見た数字
だから rows[r].has(val) は「r 行目の袋の中に val が入っているか」を聞いていることになる。