Sudoku Solver
数独盤は、9 × 9 のマス目を9つの 3 × 3 のブロックに分けたものです。解答済みの盤では、各行、各列、各ブロックに1から9までの数字がそれぞれちょうど1回ずつ入っています。
パズルは9個の文字列として、上から各行につき1つずつ与えられます。.は空のマスです。すべての空のマスを埋め、同じ形式で解答済みの盤を返してください。この盤には解が1つだけあります。
関数
- boardstring-array
- パズルの9行、それぞれの空欄に1つずつ点
- 戻り値string-array
- 解答済みの盤面の9行
制約
boardは長さ9の文字列を9個保持しています。- すべての文字は
.または数字の1から9のいずれかです。 - 与えられた数字は、行、列、またはブロック内で重複しません。
- 盤面には解がちょうど1つあります。
例
- 入力
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- 出力
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- 説明
- 一番上の行
9.7.....6にはすでに9、7、6が入っているので、6つの空きマスには1、2、3、4、5、8が入ります。それぞれの数字がどこに入るかは、列とブロックによって決まり、この行は957214386になります。
発展問題
キラー数独では、マスのケージの合計も指定された数になる必要があります。このルールを探索に追加し、枝を早い段階で打ち切るにはどうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各行、各列、各 3 × 3 のボックスにすでにどの数字が入っているかを記録しておきましょう。そうすれば、空のセルにある数字が入るかどうかを O(1) で判定できます。
空のマスを1つずつ埋めていきます。そのマスに入る数字をすべて試し、次のマスに進み、残りの盤面を完成できない場合はその数字を取り消します。
セルの順序は重要です。次は、残っている数字の選択肢が最も少ない空のセルを埋めましょう。選択肢が1つのセルなら分岐は必要ありません。選択肢がないセルがあれば、すぐに戻る必要があるとわかります。
解説
バックトラッキングで解きます。条件に合う数字を置いて先に進み、盤面を完成できない場合はその数字を取り消します。セルを処理する順序によって速度が変わります。難しい盤面では、左から右、上から下の順に調べると、途中までの盤面を何億個も確認することがあります。一方、選択肢が最も少ないセルを先に埋めれば、確認するのは約100個です。
読み順でのバックトラッキング
正しいが、最大のテストでは終わらない
考え方
空のマスを読み取り順に埋め、それぞれに当てはまる最小の数字を入れます。あるマスに入れられる数字がなくなったら、前のマスに戻って次の数字を試します。ルールを満たすすべての組み合わせを順に試すため、探索によって解が見つかります。
3つの表を使うと、各適合性チェックを O(1) で行えます。rowUsed[r][d]、colUsed[c][d]、boxUsed[b][d]です。ここで、ボックスは b = (r / 3) * 3 + c / 3 です。数字を置くと3つのエントリーが設定され、取り除くとそれらがクリアされます。
順序を固定するのが弱点です。探索では、局所的には当てはまる数字で行全体を埋めた後になって、それらの数字のせいで多くのマスに入れる余地がなくなったとわかることがあります。上の行に手がかりがほとんどなく、答えが大きな数字になる盤面では、探索対象が3億件を超える部分盤面に及びます。
アルゴリズム
- 盤面を読み込み、空のマスを0としてグリッドに格納し、
rowUsed、colUsed、boxUsedを埋め、空のマスを読み取り順に列挙します。 backtrack(k)：kが空のマスの数と等しい場合、trueを返します。- マス
kの行、列、ボックスで未使用の1から9までの各数字dについて、その数字を配置して使用済みとして記録し、backtrack(k+1)がtrueを返した場合はtrueを返します。そうでなければ、使用済みの記録を解除します。 - どの数字も使えない場合は、マスを空にしてfalseを返します。
backtrack(0)を呼び出し、グリッドを文字列に戻します。
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]最も空いているセルを最初に埋める
考え方
解答は埋める順序に依存しないため、探索範囲が小さくなる順序を選びます。各ステップで、入れられる数字が最も少ない空のマスを埋めます。入れられる数字が1つのマスは確定しており、分岐は増えません。入れられる数字がないマスはすぐに選ばれるため、誤った盤面をただちに検出できます。
各ステップで81個のマスに入れられる数字を効率よく数えるため、各行、列、ブロックをビットマスクとして保持します。rows[r]のビットdは、数字dが行rにあるときにセットされます。マスに入れられる数字は~(rows[r] | cols[c] | boxes[b]) & 0x3FEで表されます。0x3FEはビット1から9を保持し、セットされたビットの数が候補の数です。dを配置すると、3つのマスクでビットdをセットします。排他的論理和を使うと、そのビットを取り除けます。
アルゴリズム
- 与えられた数字から、グリッドとマスク
rows、cols、boxesを作成します。 backtrack(): すべてのマスを調べ、空のマスごとに使用可能な数字を計算し、その数が最も少ない最初のマスを選びます。空のマスがなければ、trueを返します。- そのマスで使用可能な数字を1つずつ試し、その数字を置いて、3つのマスクの対応するビットをセットします。
backtrack()がtrueを返したらtrueを返し、そうでなければビットをクリアします。 - どの数字も使えなければ、そのマスを空にしてfalseを返します。
backtrack()を呼び出し、グリッドを再び文字列に変換します。
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
落とし穴と境界ケース
- 取り消したときに、行・列・ボックスの記録から数字を消し忘れること。後続のセルはその数字が使用済みだと認識し、探索で解を見つけられなくなります。
- ボックスの計算に
r / 3 + c / 3を使うこと。セル(0, 4)と(4, 0)はどちらも 1 になり、2つのボックスが同じ記録を共有するため、盤面を埋められなくなります。整数除算を使って(r / 3) * 3 + c / 3としてください。 - 最初の解が見つかった時点で停止しないこと。その後、読み取る前に取り消し処理によって盤面が再び空になります。
よくある質問3
バックトラッキングによる数独ソルバーの時間計算量はどのくらいですか？
最悪の場合は指数時間で、m 個の空きマスに対して O(9^m) です。各マスで最大9個の数字に分岐する可能性があるためです。実際のパズルでは、行・列・ブロックのルールによってほとんどの分岐が除外され、さらに最も空き候補が少ないマスから埋めることで、残りの大部分も除外されます。
数独に解がちょうど1つだけあることを、どう確認しますか？
同じバックトラッキング探索を実行しますが、解の数を数え、数が2に達したら停止します。数が1ならパズルは一意に解け、0なら解がありません。パズル生成器は、手がかりを1つ削除するたびにこのチェックを実行します。
数独をバックトラッキングより速く解く方法はありますか？
ほとんどの高速なソルバーは依然としてバックトラックを行いますが、推測する前により多くのことを推論します。制約伝播では、候補が1つだけのセルと、行、列、またはブロック内で1つのセルにしか入らない数字をすべて埋め、その後これを繰り返します。数独は完全被覆問題として表現し、KnuthのAlgorithm Xで解くこともできます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def solveSudoku(board):
# ここにコードを書いてくださいテスト #1
引数
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
期待される出力
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]