Valid Sudoku
boardとして9 × 9の数独盤面を受け取ります。各行に対応する9文字の文字列が9個並んだリストです。各文字は1から9までの数字、または空のセルを表す.です。同じ数字が行、列、または3 × 3のボックス内に2回以上現れない場合はtrueを返し、それ以外の場合はfalseを返します。チェック対象は埋まっているセルのみです。盤面が解ける必要はありません。
関数
- boardstring-array
- 各行に9文字の文字列が1つずつ、数字の1～9と空のマスを表す.
- 戻り値boolean
- 行、列、または3 × 3のボックスで数字が重複していなければtrue、そうでなければ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
- 説明
- 0から数えて4行目の
.74..89.3には、7、4、8、9、3がそれぞれ1回ずつ含まれており、ほかの26グループにも繰り返されている数字はありません。
- 入力
- 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 つあります。同じ行にも同じボックスにもないため、列のチェックだけで検出できます。
- 入力
- 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です。
発展問題
4 × 4のボックスがあり、1から9とAからGの記号を使う16 × 16のボードは、どうやってチェックしますか？ボックスの数式はどうなりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルールが対象としているグループを列挙してください。グループはいくつあり、インデックス化が最も難しいのはどの種類ですか？
行
r、列cのセルは、ちょうど1つのボックスに属します。整数除算では、r / 3によって3行からなるどの段にあるかがわかり、c / 3によって3列からなるどの列のまとまりにあるかがわかります。この2つを組み合わせて、0から8までの1つの数にします。各セルを一度ずつ訪れます。(行, 数字)、(列, 数字)、(ブロック, 数字)の各ペアについて、seenフラグを保持します。3つのグループのいずれかで、フラグがすでに設定されている埋まったセルは重複です。
解説
各桁は3つのグループに属します。行、列、そして3 × 3のボックスです。行と列はインデックスで直接指定できますが、ボックスには落とし穴があります。ボックスには(r / 3) * 3 + c / 3を使って0から8まで番号を付け、81個のセルを1回走査すれば、27個すべてのグループをチェックできます。
各行、各列、各ボックスを個別に確認します
考え方
このルールでは27個のグループを指定します。9行、9列、9つのボックスです。それぞれの9個のマスを集め、ドットを無視して、数字が重複していないか調べます。どのグループにも重複がない場合に限り、盤面は有効です。
数字ごとに確認済みフラグを使うと、9個のマスの中での重複を見つけられます。81個のマスはそれぞれ、3つのグループのそれぞれについて1回ずつ読み取られます。読み取り回数は243回で、処理量は一定です。n × n の盤面では、同じ方法の計算量は O(n²) です。
アルゴリズム
iを 0 から 8 まで動かし、行i、列i、ボックスiを集めます。- ボックス
iの角は行3 * (i / 3)、列3 * (i % 3)にあります。そのセルkは、そこから下にk / 3行、右にk % 3列の位置です。 - 各グループを新しい確認済みフラグで調べ、ドットはスキップします。数字にすでにフラグが立っている場合は、
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つのボックスからなる帯を選び、c / 3で帯の中のボックスを選びます。セル(4, 7)はボックス1 * 3 + 2 = 5、つまり中央右のボックスに入ります。
フラグがすでに設定されている場合、そのグループ内で数字が重複しています。各セルは一度だけ読み取り、テーブルは243個のフラグを保持します。この場合、時間とメモリの使用量は一定で、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]が設定されている場合は、falseを返します。そうでなければ、3つすべてを設定します。- 最後のセルの後に、
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が重複として報告されます。- JavaScript、Python 3、Luaで
/を使って割り算する方法。この場合、4 / 3は1.33になります。切り捨ててください。 .を値として扱う方法。空のボードでは、各行に9つのドットがあっても有効です。- パズルを解こうとする方法。列8の下の方に9がある場合、
12345678.の行0は決して完成できませんが、何も重複していません。結果はtrueです。 - ボックスを確認しない方法。各行が1つ上の行を左に1つずらした完全なグリッドでは、行や列に重複はありませんが、すべてのボックスに重複があります。
よくある質問3
Valid Sudoku の時間計算量は何ですか？
盤面のセル数は常に81個なので、どちらの方法も実行時間はO(1)、使用するメモリはO(1)です。一般的なn × nの数独では、1回の走査によるチェックでn²個のセルをそれぞれ1回読み取り、3n²個のフラグを保持します。実行時間とメモリはO(n²)です。
有効な数独盤面は必ず解けなければなりませんか？
いいえ。ここで「有効」とは、埋められたマスの中で、行、列、または 3 × 3 のブロックに同じ数字が重複していないことだけを意味します。このチェックに合格しても、盤面に解がない場合があります。解があるかどうかを判定するには、バックトラッキングなどの探索が必要であり、これは別の問題です。
ビットマスクを使って Valid Sudoku を解けるでしょうか？
はい。各行、列、ボックスにそれぞれ1つの整数を割り当てます。ビット d は、数字 d+1 がすでに出現していることを意味します。埋まっているセルについて、1 << d と3つのマスクのいずれかとのAND演算の結果が0以外なら、その数字は重複しています。そうでなければ、その値を3つすべてにOR演算で加えます。これなら243個のフラグではなく、27個の整数で済みます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
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