Python正月特集：ナンプレを解く (1)準備編

ナンプレ（数独）のブームが来てから約10年が経過し、問題を人工知能を使って自動生成するのが普通になった。しかし、そのあたりを説明しだすと長くなるので、AIを使った自動生成の話は止める。

Pythonで、リストではなく、集合や辞書を多用して問題を解くことをやってみようと思う。
要するに、世の中であまりやっていないと思われる方法で解いてみよう。
実はこの方法の方が汎用性があり、抽象度を高くすることで、多種多様なナンプレのバラエティにも対応できる。

とりあえず、問題を用意した。以前学研の『IQナンプレ300vol.2』の表紙になった問題である。



この問題を、以下のようにして解こうと思う。
問題の数字（ヒントという）は、数字の入っているマスを[x,y,n]の形の長さ３のリストで表す。
すると、問題全体は、このリストが数字の個数あれば表現できる。

以下のプログラムでは、リストhintに問題データを与えている。
もっと便利なインターフェイスを作るべきだが、問題を解くことと本質的に関係ないので、とりあえずこの形にしておく。

問題をあれこれ調べるために問題盤面が欲しいので、問題を示すhintを与えてBoardオブジェクトを作ると、Boardオブジェクトは初期化された状態になっている。
bd.print()により、現状の盤面が表示されるので、以下では問題そのものが表示されるはず。

次に、初期化状態のBoardオブジェクトを与えてSolverオブジェクトを作り、solve()メソッドで問題を実際に解く。

こんな感じになるといいな。

NumPlace.py

def main():
hint = [[1,0,1],[1,1,2],[1,2,3],[2,3,4],[2,4,5],[2,5,6],[3,6,5],[3,7,6],[3,8,7],
[5,0,2],[5,1,3],[5,2,4],[6,3,3],[6,4,4],[6,5,5],[7,6,6],[7,7,7],[7,8,8]]
bd = Board(hint)
bd.print()                       # 問題のプリント

Solver(bd).solve(0)

main()

これを実行すると、

Labs$  python NumPlace.py

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

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
8 5 2 6 3 9 1 7 4
9 6 3 7 4 1 2 8 5

となって欲しい。

 次回は、Boardクラスを作ろう。