pythonで数独の問題を解く方法!

投稿: 2019年07月23日更新: 2019年07月25日

おはようございます！にわこまです。今回はpythonで数独（ナンプレ）の問題を解くプログラムを作ってみました.

何かご指摘があればご連絡ください！

スポンサードサーチ

数独（ナンプレ）を解く方法

Pythonを使って数独を解くプログラムを作りました。プログラムは約300行で書くことが出来ました。もっとスマートに出来るかもしれませんが、現在の私の実力だとこれが限界です。

プログラムを載せると長くなってしまうのでこちらに全プログラムを載せてあります。

このページではどのように作ったのかについて書いていきます。

今回作った数独を解くプログラムは、世界一難しい数独の問題を解くことが出来るレベルに仕上がっています。

下記に世界一難しい問題のURLと問題を載せておきます。また、何も代入されていない問題でも解けるようになっています。

数学のエキスパートが3カ月かけて作成した「世界一難しい数独」
https://gigazine.net/news/20100822_hardest_sudoku/

（注釈）今回の説明にあたって3×3のマスをボックスと呼ぶことにします。

今回は数独を解くプログラムですが、Pythonを使って数独の問題を生成する方法はこちら

アルゴリズム

まず、数独のルールを確認しておきます。説明が足りない部分もあると思いますが、簡単に説明すると以下のようなルールです。

数独のルールは
・空いているマスに数字を代入する
・代入した数字が縦、横、ボックス内で重なってはいけない
というものです。

アルゴリズム
1.　問題から代入可能なマスを選出する
2.　代入可能なマスに代入可能な数字のリストを作る
3.　代入可能な数字が1つであるマスに数字を代入する
4.　代入可能な数字のリストの更新
＊3,4を繰り返す
5.　3,4では終わらない場合、代入可能な数字のリストが一番小さいマスに適当な数字を入れる
6.　5の数字で解くことが出来なければ違う数字を入れる
＊3,4を繰り返す

3~6を1つの関数として定義し、再帰を使って数独を解いていくプログラムにしました。

1を実現するには、問題が2次元の「np.array」で、空欄は0で表現されていますので、「np.array」に合わせて座標を選出していく必要があります。

2を実現するには、各種（縦、横、ボックス）の代入可能な数字の共通の数字を選出する必要があります。また、各種の範囲で重複がない数字はその数字を返す必要があります。

上の画像の左上のボックスにおいて、各種の代入可能な数字の共通の数字は緑色の数字の通りです。

しかし、数字の8において代入可能なマスは赤丸のマスだけです。ゆえに、各種の範囲で重複がない数字はその数字を返す必要があります。

3~6の部分は下のコードの項目で詳しく説明します。

スポンサードサーチ

コード

プログラムの全文はこちらから

使用環境
OS : Windows 10
CPU : intel CORE i7 7th Gen / 2.7Ghz, 2.9Ghz

ここでは3~6の部分について説明します。

3~6を「solver」という関数として定義しました。
また、後述する「dic_length」を更新する関数を「solve_func」として定義しました。

「emp」: 代入可能なマスの座標、
「emp_dic」: empに代入可能な数字のリスト、
「field」: 問題(マス目)、
「dic_length」: 代入可能な数字のリストの長さ
として定義しました。

empを順番に調べていき代入可能数字が1つであるときに数字を代入します。また、emp_dicを更新します。

3の動作では数字を代入出来なくなったら、dic_lengthから一番小さい数字のインデックスを取得して、座標に直します。その座標に適当な数字を入れ、再帰します。

＊再帰とは… 関数の中でその関数を呼び出すこと

いろんなところでコピーしている理由は、変数に代入されていた元の数字などを返却したり、再帰する前の状態を返却したりするからです。

今回作ったプログラム「solver」を簡単に言うと、
「かたっぱしからあり得る数字の組み合わせを試す」というものです。

問題を入力する部分は以下のようになっています。

# 問題を入力する
def set_field(field):
    # 空欄は0を入れてください
    field = np.array([[0, 0, 5,   3, 0, 0,   0, 0, 0],
                      [8, 0, 0,   0, 0, 0,   0, 2, 0],
                      [0, 7, 0,   0, 1, 0,   5, 0, 0],

                      [4, 0, 0,   0, 0, 5,   3, 0, 0],
                      [0, 1, 0,   0, 7, 0,   0, 0, 6],
                      [0, 0, 3,   2, 0, 0,   0, 8, 0],

                      [0, 6, 0,   5, 0, 0,   0, 0, 9],
                      [0, 0, 4,   0, 0, 0,   0, 3, 0],
                      [0, 0, 0,   0, 0, 9,   7, 0, 0]])
    return field

問題を見たまま入力していただければ問題なく動きます。上のコードでは「世界一難しい数独」が入力されています。

使い方

こちらのページにあるプログラムをダウンロードしてください。

(1)pythonのプログラムを任意の名前で保存してください(名前は何でも問題ありません。)
(2)プログラムをエディターで開き問題を入力してください
(3)コマンドプロンプトを開いてください
(4)pythonのプログラムを保存したフォルダまで移動してください
(5)「python solver.py」と入力してエンターを押すと、少し時間がかかって答えがコマンド

場合によっては(4)の「python」の部分は「python3」になるかもしれません。

注意
解くことが出来ない問題を入力すると無限ループしてプログラムが終了しません。

遅くても1分以内には解くことが出来ると思います。 5分や10分など1分以上処理に時間がかかっている場合はコマンドプロンプトを閉じて、入力した問題を確認してみてください。

スポンサードサーチ

まとめ

今回はPythonを使って数独（ナンプレ）の問題を解くプログラムを作ってみました。

やはり、ゲームを実装するのは難しいですがとても楽しかったです。

今回のプログラムは、while文や再帰を使ってゴリ押しましたが、人間が解くようにプログラムを実装出来たらもっとスマートにプログラムを書けると思います。

問題の入力がめんどうくさいので、改良する余地があります。webアプリケーションのようにwebから操作出来るように作りますのでお楽しみに！

最後までお読みいただきありがとうございます。

スポンサードサーチ