Python正月特集：ナンプレを解く (3)Solver編

前回、Boardクラスの説明をしたが、実はそれでほんとんど準備は済んでいる。

前回のBoardクラスを利用することで、問題を解くのがSolverクラスで、初期化と解くクラスのたった２つのメソッドがあるだけ。とても簡単である。

まず、コンストラクタについて。

class Solver:
def __init__(self,board):
self.board = board
self.searchorder = self.board.makeblanklist()

問題が入った状態のBoardオブジェクトを与えて初期化が行われる。
このとき、問題の空きマスのリストをsearchorderに入れる。
searchorderは、名前の通り、マスをどの順番で調べるか（埋めていくか）の情報が入っている。

で、次に、問題を実際に解くメソッド solveである。

    def solve(self,idx):
if idx == len(self.searchorder):
self.board.print()       # 解けた！ 解のプリント
return
x,y = self.searchorder[idx]
possibles = self.board.possibles(x,y)
for c in possibles:          # 可能な数字を順番に試す
self.board.setnum(x,y,c)
self.solve(idx+1)
self.board.rmnum(x,y,c)

solveには引数idxがあるが、このidxは最初に作った空きマスリスト(searchorder)の何番目の要素（空きマス）を次に調べるかを伝えている。
メインからは、

    Solver(bd).solve(0)

と呼ばれていたが、solve(0)で、searchorderの最初のマスを試すことになる。
もし、searchorderを全部使いきっていたら全部埋まっているはずなので解が出来上がっているはずなのでプリントする。
そうでなければ、次に数字を試すマス(x,y)を求め、マス(x,y)に入れることができる数字のリストをpossiblesとし、可能な数字すべてについてforループで調べる。
forループの中は、ます(x,y)に調べている数字cを置いて、次の空きマスを指示するためにidx+1を引数にして再帰呼出しをする。
戻ってきたら、元の状態に戻すために、マス(x,y)からcを取り除く。

これだけで、ちゃんと動く。
再帰を使えば、簡単である。

次の盤面は途中の状態をプリントしたものである。

4 1 7 8 5 2 6 3 9
5 2 8 9 6 3 7 4 1
6 3 9 1 7 4 8 5 2
1 7 4 2 8 5 3 9 6
2 8 5 3 9 6 4 1 7
3 9 6 4 1 7 5 2 8
7 4 1 5 2 8 9 6 3
9 5 2 6 3 1 _ 7 _
_ _ _ 7 _ _ _ 8 _

最初の空きマス(_)は、(7,6)のマスであるが、ここには１〜９のいずれも入れられないので、再帰はこの先に進まず、戻っていく。
ということで、ナンプレを解くプログラムの説明は終える。

なお、実際にナンプレを解くプログラムを作る場合、このような再帰呼出しで虱潰しはしない。
これでは難易度が分からないし、それに遅い。
また、各マス、各グループ(タテ列、ヨコ列、ブロック)に何が入っているかを集合で実現したが、もちろん集合は遅いので使わないのが普通だ。
実際のナンプレ関連のプログラムでは、ビット演算を多用し高速化を実現する。
また、使った数字を集合に入れていたが、実際は使える数字(まだ使っていない数字＝候補)を管理することで解いていく。

9×9のナンプレを解くのはとても簡単で、プログラミング初歩の練習問題である。
もうちょっと頑張ってみたい場合は、16×16、25×25の問題を解くプログラムを作ってみよう。
あるいは、ナンプレを自動生成するプログラムを作ってみよう。

正月も終わったので、この正月特集もこれで終わる（完）