集合で数独の盤に同じ数字の重なりが無いか確かめる

配列とハッシュ問題 97

途中まで数字の入った 9 × 9 の数独の盤で、行、列、3 × 3 の箱のどれにも同じ数字が 2 回入っていないかを確かめます。見た数字を「どの行、どの列、どの箱か」と組にして集合に覚える、ハッシュの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

数独の盤を、9 本の文字列の並び board で受け取ります。board[r] は上から r 番目の行で、9 文字のそれぞれが "1" から "9" の数字か、まだ空いているマスを表す "." です。

入っている数字だけを見て、次の 3 つを全部守っていれば true、1 つでも破っていれば false を返す関数を書いてください。

どの行にも、同じ数字が 2 回入っていない
どの列にも、同じ数字が 2 回入っていない
盤を縦横 3 つずつに割った 9 個の 3 × 3 の箱のどれにも、同じ数字が 2 回入っていない
空いたマスは数えません。空いたマスに数字を入れて最後まで解けるかどうかは問いません
board は必ず 9 本で、どの文字列も 9 文字です。文字は "1" から "9" と "." だけです

入力と出力の例

例 1

入っている数字は、どの行、列、箱でも重なっていません。

board = ["1.3..6.8.", ".5.78..2.", "7..1.3.5.", "..45...9.", "5.7.9.2.4", ".9..3.5.7", "3..6.89..", ".7.9..3.5", "9.2..5.7."]

true

例 2

左上の箱に 4 が 2 つあります。行も列も違いますが、箱が同じなので false です。

board = ["4..2.....", "..4...7..", ".........", ".........", ".........", ".........", ".........", ".........", "........."]

false

例 3

例 1 の最後の行の 7 を 8 に替えた盤です。右から 2 番目の列に、いちばん上の行の 8 と合わせて 8 が 2 つ入ります。

board = ["1.3..6.8.", ".5.78..2.", "7..1.3.5.", "..45...9.", "5.7.9.2.4", ".9..3.5.7", "3..6.89..", ".7.9..3.5", "9.2..5.8."]

false

面接での聞かれ方

面接では、盤を見せて短く聞かれることがよくあります。

「この数独の盤が、決まりを破っていないか確かめてください」
「解けるかどうかも見ますか？」と、範囲を自分から確かめるかを見られます
書き終えたあとに「盤を 1 回だけなめて確かめられますか？」と広げられることもあります

確かめるのは、すでに入っている数字の重なりだけです。最後まで解けるかどうかはバックトラックの別の問題なので、書く前に範囲をそろえておきます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

ハッシュは、値から番地を計算して、探す手間をほぼ 1 回にする仕組みです。重複や回数の問題は、この形で解けます。

まず考える手順

段 1

決まりを 3 つに分けます。行、列、箱です。行と列はすぐ分かりますが、箱はマスの位置から番号を出す必要があります。行の番号を 3 で割った商と、列の番号を 3 で割った商の組で、箱が 1 つに決まります。

段 2

素直に書くなら、行を 9 本、列を 9 本、箱を 9 個、それぞれ別の繰り返しで確かめます。盤の大きさは決まっているので遅くはありませんが、同じような繰り返しを 3 回書くことになり、箱の範囲の計算で間違えやすくなります。

段 3

マスを 1 回ずつ見て、数字が入っていたら「行 r に v がある」「列 c に v がある」「箱 b に v がある」の 3 つの印を作ります。この印を集合に覚えておけば、同じ印が 2 回目に出たときが重なりです。箱の番号 b は、r // 3 * 3 + c // 3 で 0 から 8 に振れます。

段 4

印を作るとき、行と列と箱を区別する文字を入れておきます。区別しないと、「行 2 に 5」と「列 2 に 5」が同じ印になり、重なっていないのに false を返します。

解答

Python

def valid_sudoku(board):
    seen = set()
    for i in range(81):
        r, c = divmod(i, 9)
        v = board[r][c]
        if v == ".":
            continue
        b = r // 3 * 3 + c // 3
        keys = (("row", r, v),
                ("col", c, v),
                ("box", b, v))
        for k in keys:
            if k in seen:
                return False
            seen.add(k)
    return True

JavaScript

function validSudoku(
  board
) {
  const seen = new Set();
  for (let i = 0; i < 81; i++) {
    const r = Math.floor(i / 9);
    const c = i % 9;
    const v = board[r][c];
    if (v === ".") continue;
    const b =
      Math.floor(r / 3) * 3 +
      Math.floor(c / 3);
    const keys = [
      `row${r}-${v}`,
      `col${c}-${v}`,
      `box${b}-${v}`,
    ];
    for (const k of keys) {
      if (seen.has(k)) {
        return false;
      }
      seen.add(k);
    }
  }
  return true;
}

Go

func validSudoku(
	board []string,
) bool {
	var rows [9][10]bool
	var cols [9][10]bool
	var boxes [9][10]bool
	for i := 0; i < 81; i++ {
		r, c := i/9, i%9
		if board[r][c] == '.' {
			continue
		}
		d := board[r][c] - '0'
		b := r/3*3 + c/3
		if rows[r][d] ||
			cols[c][d] ||
			boxes[b][d] {
			return false
		}
		rows[r][d] = true
		cols[c][d] = true
		boxes[b][d] = true
	}
	return true
}

81 マスを 1 本の繰り返しで回し、番号 i から行と列を出しています。Python と JavaScript は「どれの何番に、どの数字か」を 1 つの印にして集合に入れ、Go は数字が 1 から 9 に決まっているのを使って、行、列、箱ごとの真偽の表で覚えています。どちらも、同じ印を 2 回目に見たら重なりです。

計算量

時間は O(1) です。盤はいつも 81 マスで、1 マスにつき印を 3 つ見るだけです。盤の一辺を n とした広い数独なら O(n²) です
使う記憶も O(1) です。印は多くても 81 × 3 個です
段 2 の行、列、箱を別々に確かめる書き方も同じ O(1) ですが、盤を 3 回なめます

よくある間違い

空いたマスの "." も数字と同じに数える。 空きは 1 つの行に何個でもあるので、すぐ重なりと見なして false を返します。数字のマスだけを見ます
行と列と箱の印を区別しない。「行 2 に 5」と「列 2 に 5」が同じ印になり、例 1 のような正しい盤でも false を返します。印に row、col、box のような区別を入れます
箱の番号を r // 3 + c // 3 と書く。 左上から 1 つ右の箱と 1 つ下の箱が同じ番号 1 になります。行の商に 3 を掛けてから列の商を足します
最後まで解けるかまで確かめようとする。問いの範囲を広げてしまい、時間内に書き終わりません。範囲は最初に確かめます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def valid_sudoku(board: list[str]) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(valid_sudoku(["1.3..6.8.", ".5.78..2.", "7..1.3.5.", "..45...9.", "5.7.9.2.4", ".9..3.5.7", "3..6.89..", ".7.9..3.5", "9.2..5.7."]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します