Valid Sudoku
9 × 9 の数独盤面が board として与えられます。これは、各行に対応する9文字の文字列を9個含むリストです。各文字は 1 から 9 までの数字、または空のマスを表す . です。同じ行、同じ列、または同じ 3 × 3 のボックスに同じ数字が2回以上現れない場合は true を返し、それ以外の場合は false を返してください。チェックするのは埋まっているマスだけです。盤面が解ける必要はありません。
関数
- boardstring-array
- 各行に1つずつ、9文字の文字列が9つ。数字は1～9、空のセルは .
- 戻り値boolean
- true（行、列、または3 × 3のボックスで数字が重複していない場合）、それ以外はfalse
制約
board.length == 9とboard[i].length == 9board[i][j]は1から9までの数字、または.です- 盤面は完成できない場合があります。重要なのは、埋まっているマス同士での繰り返しだけです。
例
- 入力
- board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
- 出力
- true
- 説明
- 各行、各列、各ボックスには、それぞれの数字が1回までしか現れません。0から数えて4行目の
.74..89.3には、7、4、8、9、3がそれぞれ1回ずつあり、ほかの26グループも同様なので、答えはtrueです。
- 入力
- board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
- 出力
- false
- 説明
- 行 0 と行 7 はどちらも
3で始まるため、列 0 には 3 が 2 つあります。この 2 つのセルは異なる行、異なるボックスにあります。この場合、列のチェックだけが重複を検出します。
- 入力
- board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
- 出力
- false
- 説明
- 行 0、列 8 の
5と行 2、列 7 の5は、異なる行かつ異なる列にありますが、どちらも右上のボックスにあるため、答えはfalseです。
提出時に隠しテスト+16件
発展問題
チェックを、4 × 4 のボックスがある 16 × 16 の盤面と、1 から 9 および A から G の記号に一般化してください。コード内のどの数値が盤面のサイズに依存していますか。また、ボックスの計算式はどうなりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルールが言及しているグループを列挙してください。グループはいくつあり、インデックス化が最も難しいのはどの種類ですか？
行
r、列cのセルは、ちょうど1つのボックスに属します。整数除算では、r / 3は3行ごとのどの帯にあるかを示し、c / 3は3列ごとのどの縦列にあるかを示します。この2つを組み合わせて、0から8までの数にします。各セルを1回ずつ訪れます。(行、数字)、(列、数字)、(ボックス、数字)の各ペアについて、確認済みフラグを保持します。3つのグループのいずれかでフラグがすでに設定されているセルに数字が入っていたら、それは重複です。
解説
各桁は同時に3つのグループに属します。行、列、そして3 × 3のボックスです。行と列はそのままインデックス化できますが、ボックスはバグの温床になりがちです。ボックスに0から8までの番号を付けるには (r / 3) * 3 + c / 3 を使います。81個のセルを1回走査するだけで、27個すべてのグループをまとめてチェックできます。
各行、列、ボックスをそれぞれ個別に確認する
考え方
ルールでは27個のグループを指定します。9行、9列、9つのボックスです。各グループの9個のセルを集め、ドットを無視して、その中に同じ数字が繰り返し現れるかどうかを調べます。どのグループにも重複がなければ、盤面は有効です。
行 i は board[i][0..8]、列 i は board[0..8][i] です。ボックス i は、整数除算を使って、行 3 * (i / 3)、列 3 * (i % 3) から始まります。そのため、ボックス5は行3、列6から始まります。その角から見て、セル k は k / 3 行下、k % 3 列右にあります。
9個のセルの中から重複を見つけるには、数字ごとに確認済みフラグを保持し、すでにフラグが立っている数字が見つかった時点で処理を止めます。81個のセルは、それぞれ属する3つのグループについて1回ずつ読み取られます。つまり、読み取りは243回で、処理量は一定です。n × n の盤面では、同じ方法の計算量は O(n²) です。
アルゴリズム
iを0から8まで動かし、行i、列i、ブロックiのそれぞれから、9個のセルを集めます。- ブロック
iはtop = 3 * (i / 3)、left = 3 * (i % 3)から始まります。そのブロック内のセルkは、行top + k / 3、列left + k % 3にあります。 - 各グループについて、新しいseenフラグを用意し、ドットをスキップしながらセルを順に調べます。
- 数字にすでにフラグが立っている場合は、
falseを返します。 - 27個すべてのグループを調べた後、
trueを返します。
def has_repeat(cells):
seen = set()
for ch in cells:
if ch == '.':
continue
if ch in seen:
return True
seen.add(ch)
return False
def isValidSudoku(board):
for r in range(9):
if has_repeat(board[r][c] for c in range(9)):
return False
for c in range(9):
if has_repeat(board[r][c] for r in range(9)):
return False
for top in (0, 3, 6):
for left in (0, 3, 6):
box = (board[top + i][left + j] for i in range(3) for j in range(3))
if has_repeat(box):
return False
return True行、列、ブロックごとに確認済みテーブルを使って1回走査
考え方
グループごとに集計する代わりに、各セルを一度ずつ調べ、3つの質問を同時に確認します。9 × 9 のフラグ表を3つ用意します。seenRow[r][d] は、数字 d+1 がすでに行 r にあることを示します。列とボックスについても、seenCol と seenBox が同様に機能します。
セル (r, c) はボックス (r / 3) * 3 + c / 3 に属します。最初の部分は3つのボックスからなる帯を選びます（行0～2は帯0、行3～5は帯1、行6～8は帯2）。そして c / 3 が帯の中のボックスを選びます。セル (4, 7) はボックス 1 * 3 + 2 = 5、つまり中央右のボックスに入ります。
値が入っている各セルについて、3つのフラグのいずれかがすでに立っていれば、その数字は該当するグループ内で重複しているため、ただちに false を返します。そうでなければ、3つすべてのフラグを立てます。各セルは一度だけ読み取られ、表には243個のフラグがあるため、9 × 9 の盤面では時間とメモリの使用量は一定で、n × n の盤面では O(n²) です。
アルゴリズム
seenRow、seenCol、seenBoxを作成します。それぞれ9 × 9で、すべてfalseにします。- すべてのセル
(r, c)を調べます。ドットが入っている場合はスキップします。 dを数字から1を引いた値、b = (r / 3) * 3 + c / 3とします。seenRow[r][d]、seenCol[c][d]、またはseenBox[b][d]がtrueの場合、falseを返します。- それ以外の場合は、3つすべてをtrueに設定します。最後のセルの後に
trueを返します。
def isValidSudoku(board):
# seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
seen_row = [[False] * 9 for _ in range(9)]
seen_col = [[False] * 9 for _ in range(9)]
seen_box = [[False] * 9 for _ in range(9)]
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == '.':
continue
d = int(ch) - 1
b = (r // 3) * 3 + c // 3
if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
return False
seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
return True
落とし穴と境界ケース
行と列のチェックで問題が起きることはめったにありません。バグは、ボックスのインデックスと、何を重複とみなすかにあります。
- ボックスを
r / 3 + c / 3として計算する。これでは値が0から4までしかなく、別々のボックスにあるセル(0, 3)と(3, 0)が同じ番号になるため、そこにある2つの7が重複として報告されます。(r / 3) * 3 + c / 3を使いましょう。 4 / 3がボックス番号ではなく1.33になるJavaScript、Python 3、またはLuaで、/による除算を使う。Math.floor、//、またはmath.floorを使いましょう。.を値として扱う。空の盤面では各行に9つのドットがありますが、それでも有効です。- パズルを解こうとする。行0が
12345678.で、列8の下の方に9がある場合、行0の最後のセルには決して数字を入れられませんが、どのグループにも数字の重複はないため、答えはtrueです。 - 行と列をチェックしても、ボックスをチェックしない。各行がひとつ前の行を左に1つずらした完全なグリッドでは、どの行にも列にも重複はありませんが、すべてのボックスには重複があります。
よくある質問4
Valid Sudoku の時間計算量はどれくらいですか？
ボードのセル数は常に81なので、どちらの方法も実行時間はO(1)、使用するメモリはO(1)です。一般的なn × nの数独では、1回の走査によるチェックでn²個のセルをそれぞれ1回読み取り、3n²個のフラグを保持するため、時間計算量とメモリ計算量はO(n²)です。
有効な数独盤面は解ける必要がありますか？
いいえ。ここでの「有効」とは、すでに埋まっているマスの間で、同じ数字が行、列、または 3 × 3 のブロック内に重複していないことだけを意味します。このチェックに合格しても、解がない盤面はありえます。解けるかどうかを判定するには、バックトラッキングなどの探索が必要ですが、これは別の問題です。
セルがどの 3 × 3 ボックスにあるかは、どうすればわかりますか？
整数除算では、r / 3は行の帯（0、1、または2）を表し、c / 3は列の積み重なりを表します。(r / 3) * 3 + c / 3は、ボックスに左から右、上から下へ0から8の番号を付けます。セル(7, 1)はボックス2 * 3 + 0 = 6、つまり左下のボックスにあります。
有効な数独はビットマスクで解けますか？
はい。各行、各列、各ボックスに整数を1つ割り当て、ビットdは数字d+1が出現済みであることを表すようにします。埋まっているセルでは1 << dを計算します。これが3つのマスクのいずれかとANDを取って0でなければ、その数字は重複しています。そうでなければ、3つすべてにORします。これなら243個のフラグではなく27個の整数で済み、同じ1回の走査で処理できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isValidSudoku(board):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
期待値
true