数独を深さ優先探索で解きます。
プログラム作成の優先順位は
- 簡単
- 分かり易い
- 早い
の順で作りました。早さは犠牲にしてます。
#データ構造
一般的な二次元配列で表現します。
def values_from_grid(grid):
"テキストから２次元配列のvaluesを作成する"
values = []
digits = "123456789"
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
grid_int = map(lambda x: int(x) if x != "." else 0, chars)
count = 0
row = []
for i in grid_int:
row.append(i)
count += 1
if count % 9 == 0: #行毎に分割
values.append(row)
row = []
return values
テキストを読み込んで二次元配列に変換する関数です。
テキストの形式は空欄を0または.で表現したものでそれ以外の数字を順番に登録して
81文字であればOKとしています。
下記のテキスト形式等に対応しています。
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
..53.....8......2..7..1.5..4....53...1..7...6..32...8..6.5....9..4....3......97..
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
#プログラム
深さ優先探索で再帰的にチェックします。
呼び出し方は
values = values_from_grid(数独データ)
solver(values)
です。solver関数にvaluesを渡します。解き終えるとvaluesが答えの配列になっています。
##メイン関数
左上のマスから右下のマスまで、1マスづつ1から9の数字を当てはめます。
この時当てはめる数字が「縦・横・3×3」のマスになかった場合のみ数字を当てはめます。
xは横軸、yは縦軸を表しています。xが8になったら、つまり横軸の最後に達したら
縦軸を一つ下にして横軸を0にして、下の行の一番初めのマスをチェックします。
最後のマスに達したら問題が解けているのでTrueを返します。
def solver(values, x=0, y=0):
"数独を解く"
if y > 8: #ポインタが最後までいったら完成
return True
elif values[y][x] != 0: #空欄ではないなら飛ばす
if x == 8: #8列までいったら次の行に移動
if solver(values, 0, y+1):
return True
else:
if solver(values, x+1, y):
return True
else:
for i in range(1, 10):#1から9までの数字を全て試す
if check(values, x, y, i): #チェックする
values[y][x] = i #OKなら数字を入れる
if x == 8: #8列までいったら次の行に移動
if solver(values, 0, y+1):
return True
else:
if solver(values, x+1, y):
return True
values[y][x] = 0 #戻ってきたら0に戻す
return False
返り値はTrueかFalseを返します。解けたらTrueです。
##チェック関数
横軸・縦軸・3*3の領域をチェックします。
それぞれの関数を呼び出す関数です。
def check(values, x, y, i):
if row(values, y, i) and column(values, x, i) and block(values, x, y, i):
return True
return False
###横軸のチェック
横軸をチェックするために現在の行を示す縦軸の値を引数に取ります。
iは入れようとしている数字です。
横軸を1マスずつチェックして、入れようとしている数字と同一ならFalse、ではないなら
Trueのリストを作成し、それをall関数でチェックします。
全てTrueなら数字の重複はなしでTrueを返します。
一つでも重複があればFalseを返します。
def row(values, y, i):
"横をチェック"
return all(True if i != values[y][_x] else False for _x in range(9))
###縦軸のチェック
横軸のチェックを縦軸にしただけです。
def column(values, x, i):
"縦をチェック"
return all(True if i != values[_y][x] else False for _y in range(9))
###3×3のチェック
以下の関数はPythonで数独ソルバーを実装したを参考に作成しました。
0~8の数を3で割って小数点以下を削除した値を3倍するとそれぞれ0, 3, 6が得られるため
マス目が所属しているブロックが分かる、という理屈です。
def block(values, x, y, i):
"3x3のブロックをチェック"
xbase = (x // 3) * 3
ybase = (y // 3) * 3
return all(True if i != values[_y][_x] else False
for _y in range(ybase, ybase + 3)
for _x in range(xbase, xbase + 3))
#実行例
問題
8 5 . |. . 2 |4 . .
7 2 . |. . . |. . 9
. . 4 |. . . |. . .
------+------+------
. . . |1 . 7 |. . 2
3 . 5 |. . . |9 . .
. 4 . |. . . |. . .
------+------+------
. . . |. 8 . |. 7 .
. 1 7 |. . . |. . .
. . . |. 3 6 |. 4 .
回答
[8, 5, 9, 6, 1, 2, 4, 3, 7]
[7, 2, 3, 8, 5, 4, 1, 6, 9]
[1, 6, 4, 3, 7, 9, 5, 2, 8]
[9, 8, 6, 1, 4, 7, 3, 5, 2]
[3, 7, 5, 2, 6, 8, 9, 1, 4]
[2, 4, 1, 5, 9, 3, 7, 8, 6]
[4, 3, 2, 9, 8, 1, 6, 7, 5]
[6, 1, 7, 4, 2, 5, 8, 9, 3]
[5, 9, 8, 7, 3, 6, 2, 4, 1]
このパズルを解くのにこのプログラムは私の環境で大体23秒かかりました。
それに対してあらゆる数独パズルを解くにあるプログラムは0.01秒で解きます。
これはあらゆる数独パズルを解くは「取り得る値が１つに決定できるマスを埋めると、他のマスも同様に埋まる」という戦略を実行して、それでも埋まらないマスはマスごとに取り得る値のみ探索して解を求めているからです。
このプログラムは例え9しか入らないマスでも1から8までチェックしていますし、縦・横・3×3のマス目をチェックする際にそれぞれ重複するマス目が発生しますがそれも個別にチェックしています。
なので遅いです。
#参考サイト
あらゆる数独パズルを解く
Pythonで数独ソルバーを実装した