TIM Labs

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

| コメント(0) | トラックバック(0)
そろそろ年末なので、Pythonの内容も正月らしいというか、遊びを取り上げよう。
ナンプレ(数独)のブームが来てから約10年が経過し、問題を人工知能を使って自動生成するのが普通になった。しかし、そのあたりを説明しだすと長くなるので、AIを使った自動生成の話は止める。

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

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


IQNumPlay300V2 (141x200).jpg       num18sym.png

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

以下のプログラムでは、リスト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クラスを作ろう。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/545

コメントする

このブログ記事について

このページは、fujiが2016年12月30日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「Python簡単実験:集合は大きくなっても小さくならない」です。

次のブログ記事は「謹賀新年:人工知能でナンプレ問題集をつくる」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。