puzzle-generator-py

本ソースコード公開の方針

方針

元々Javaのナンプレの問題の自動生成プログラムを公開していた。このところ、Pythonが著しく普及してきたので、Python版を用意した。

本書は、進化計算の実際を知ってもらうための実際的な解説。

９ｘ９の標準的なナンプレを自動生成するのに、進化計算を使うことで、パズル作家でも困難な良質のナンプレ問題を簡単に作れることを体験してもらう。

そのため、問題作成のアルゴリズムの理解や実験に関係ないことは全部省略する。

本解説を元に、進化計算に興味を持ってもらう。学生に興味をもってもらい、さらに高度な進化計算に挑戦することを期待する。

ソースコードを公開することで、進化計算の実際を知ってもらう。コードを改変し、学習・研究に役立ててもらう。

内容は、高校、専門学校、大学初年度レベル（プログラミング初心者）にも分かるようにする。

なお、Pythonは、Java, C/C++ などのコンパイラ言語のような高速に実行できる言語と比較すると2桁程実行速度が落ちる。それで、あとでPythonの高速版・コンパイラ版であるCythonを用いたCython版を別途用意する予定である。速度は、約100倍になる。

説明しないこと

ナンプレの問題をとにかく自動生成できるところまでの説明に留める。

GUIは無し。難易度の判定、調整は説明しない。特殊なバラエティナンプレは説明しない。遺伝的アルゴリズムも説明しない。

説明を省略したことについては、発展課題編の中で言及する。説明はせず、すべて読者への課題として示す。最後に、パズル以外への社会の課題解決など、実用的な面についても言及する。

すごく頑張れば、ギネス世界記録(TM)になった280合体ナンプレも作れる。そのためには、Pythonではなく、高速なコンパイラ言語を用いなくてはいけない。

プログラムについて

ナンプレ(数独)の問題をPythonで自動生成するためのプログラムの小さなセット

Pythonプログラム

237 NP.py
168 generator.py
  9 parameter.py
 62 solution.py
244 solver.py
720 合計

メインモジュールはNP.pyです。

Problem500.txt	問題サンプル500問
Pattern500.txt		問題ヒントパターン500問分

HeartQ.txt		ハートの形の問題
HeartP.txt		ハートの形のヒントパターン

18P.txt			ヒント数18のパターン数種
17P.txt			ヒント数17のパターン数種

Python$ python3 NP.py
===== arguments input error =====
python3  NP.py  -s  problem_file   [answer_file]
python3  NP.py  -g  pattern_file   [problem_file]

-sで問題を解く、-gで問題を作ることを指示する。その直後のファイルが、問題ファイルまたは問題パターンファイルとなる。問題を解いた結果の解、あるいは作成された問題をファイルに出力したい場合には、出力ファイルを指定する。画面上には、解あるいは問題の表示と、途中経過が示される。

詳細はドキュメントを参照のこと。

実行するだけの場合は、「実行するだけ」を参照のこと。

実行するだけ Python版

とりあえず、動かしてみたい人のため説明です。都合により、Linux上での動作について説明しています。その他のOSの場合には、一部変更になる可能性があります。

LinuxのUbuntu 20で実行しており、Intelのi5-7500 CPU @ 3.40GHzで確認しています。

GitHubから、とりあえずまとめてダウンロードに、適当なところに展開してください。ここでは、C:\Users\fuji\Desktop\ナンプレ\Pythonに展開した場合の実行を示しています。

現在、Pythonにいて、ファイル構成が以下のようになっているとします。

Python$ tree
フォルダー パスの一覧
src
├── NP.py
├── data
│   ├── 17P.txt
│   ├── 18P.txt
│   ├── 20P.txt
│   ├── 22P.txt
│   ├── 24P.txt
│   ├── Heart1Q.txt
│   ├── Heart2Q.txt
│   ├── HeartP.txt
│   ├── HeartQ.txt
│   ├── ImpossibleP.txt
│   ├── Pattern500.txt
│   └── Problem500.txt
├── generator.py
├── parameter.py
├── solution.py
└── solver.py

Pythonは、バージョン３を使用してください。本書では、python3 コマンドを用います。

Python$ python3 NP.py
===== arguments input error =====
python3  NP.py  -s  problem_file   [answer_file]
python3  NP.py  -g  pattern_file   [problem_file]

パラメータなしでNP.pyを起動すると、上記のように入力形式を表示します。パラメータにエラーがある場合も、上記の表示になります。

データを、GitHubの配置と同じで、dataフォルダに置いた状態になっているとします。

問題を解く

パラメータ−sは問題を解く(solve)指示です。 −gは問題を生成する(generate)指示です。 -sに引き続いて、問題ファイルを与えると、問題を解きます。

正常な問題を解く

Python$ python3 NP.py -s data/HeartQ.txt
Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 3 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -
0
2 8 7 5 1 9 4 3 6
3 1 6 4 2 8 5 9 7
4 5 9 3 6 7 1 8 2
7 9 4 8 5 2 3 6 1
8 3 1 7 4 6 2 5 9
5 6 2 9 3 1 8 7 4
9 7 5 1 8 4 6 2 3
6 4 8 2 9 3 7 1 5
1 2 3 6 7 5 9 4 8

Total 1	Success 1
Time    0.021309 sec

最後に

与えられた問題数
きちんと解けた問題数
全体の計算時間（秒単位）

を表示します。

問題と答えの間にある数字（この場合は０）は、解けきれなかったマス数を示します。 きちんと解ければ、０になります。 正の数になった場合は、解けきれなかったマス（空白ます「−」）の数を示し、多重解の問題になってしまったことが分かります。

解ききれない問題（多重解の問題）を解く

次の例は、正しい問題の数字を一箇所だけ変更したものです。 すると、残りマス数が23になり、最後の成功数が0になっています。

Python$ python3 NP.py -s data/Heart1Q.txt
Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 1 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -
23
- 8 7 5 - 9 1 4 6
- 1 6 - - - 5 9 7
4 5 9 1 6 7 8 3 2
7 9 - - 5 - - 6 1
8 - - 7 - 6 - 5 9
5 6 - 9 - - - 7 8
9 7 5 - - - 6 2 3
6 4 8 2 9 3 7 1 5
1 - - 6 7 5 9 8 4
Total 1	Success 0
Time    0.017244 sec

エラーの場合

さらに、問題の同じマスの値を変更してみます。

Python$ cat data/Heart2Q.txt
Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 8 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -

これで実行すると、以下のようになりました。現バージョンでは、エラーの場合は、問題を表示しません。ちょっと不親切ですね。

Python$ python3 NP.py -s data/Heart2Q.txt
Heart   H 20
ERROR
Total 1	Success 0
Time    0.002460 sec

問題を作る

−gオプション付きでパターンファイルを与えると、パターンを表示後、*を次々と表示します。 *１つが、試行錯誤(TRY)1回を示します。

Python$ python3 NP.py -g data/HeartP.txt
No.1   H 20
- - - - - - - - -
- X X - - - X X -
X - - X - X - - X
X - - - X - - - X
X - - - - - - - X
- X - - - - - X -
- - X - - - X - -
- - - X - X - - -
- - - - X - - - -
************************SUCCESS  TRY 23
- - - - - - - - -
- 2 9 - - - 7 8 -
1 - - 3 - 5 - - 4
4 - - - 9 - - - 3
2 - - - - - - - 1
- 1 - - - - - 5 -
- - 6 - - - 9 - -
- - - 4 - 1 - - -
- - - - 2 - - - -

total 1  failure 0
Time    252.955505 sec

この例では、23回の再トライで成功しました。最も少ない場合は、*１つで成功し、 TRY 0 と表示されます。

次の例は、

Python$ python3 NP.py -g data/ImpossibleP.txt
No.1   H 17
- - - - - - - X X
- - - - - - - - -
- - X X X - - - -
- - X - - X - - -
- - X - - - X - -
- - - X - X - X -
- - - - X - X - -
X - - - - X - - -
X - - - - - - - -
****************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************FAILURE

total 1  failure 1
Time    3712.912889 sec

このパターンでは、多数回試してもだめで、あきらめてしまいました。現在は、400回試してだめだったらあきらめ、FAILUREと表示します。

このパターンは、このプログラムには組み込んでいない手筋を使って解く・作るプログラムでは、以下のような問題を作ることができます。

問題を連続して解く

ナンプレ500問が１つのファイルになっている Problem500.txt の問題を解いてみます。

Python$ python3 NP.py -s data/Problem500.txt
No.1   H 18
- - - - 8 - - - -
- - - 9 - 7 - - -
4 2 - - - - 3 - -
- - 7 - - 9 - - -
- 8 - - - - - 3 -
- - - 1 - - 4 - -
- - 2 - - - - 8 7
- - - 3 - 4 - - -
- - - - 5 - - - -
0
7 9 3 4 8 2 1 6 5
5 6 1 9 3 7 8 2 4
4 2 8 5 1 6 3 7 9
1 3 7 8 4 9 6 5 2
9 8 4 2 6 5 7 3 1
2 5 6 1 7 3 4 9 8
3 4 2 6 9 1 5 8 7
8 7 5 3 2 4 9 1 6
6 1 9 7 5 8 2 4 3

No.2   H 18
- 8 - - - - 6 - -
- 9 - 1 - - - 3 -
- - - 5 - - - - -
- - - - - 7 3 - -
- - 1 - - - 8 - -
- - 5 4 - - - - -
- - - - - 6 - - -
- 3 - - - 8 - 4 -
- - 2 - - - - 1 -




◇ ◇ 中略 ◇ ◇


No.500   H 24
- - 2 3 - - - - -
- - 4 - - 5 - - -
- - - - - 6 - 1 8
- 2 8 5 - 7 - - 6
- - - - - - - - -
7 - - 6 - 1 5 9 -
9 5 - 7 - - - - -
- - - 2 - - - - -
- - - - - 3 7 - -
0
8 9 2 3 1 4 6 7 5
6 1 4 8 7 5 9 2 3
3 7 5 9 2 6 4 1 8
1 2 8 5 9 7 3 4 6
5 6 9 4 3 2 1 8 7
7 4 3 6 8 1 5 9 2
9 5 1 7 6 8 2 3 4
4 3 7 2 5 9 8 6 1
2 8 6 1 4 3 7 5 9

Total 500	Success 500
Time    10.892606 sec

一気に解いて、1問平均で21.8ミリ秒の速度で解きました。

ヒント数が18〜24個の問題500問の問題集です。

あまりにも高速に解くので、時間計測が正しくなるように、一気に解きながら解を記憶し（表示しない）、解いたときの経過時間を記憶しています。解き終えてから、問題と解を示し、最後に経過時間を表示しています。これは、解く時間に比べて表示の時間が圧倒的に長いための措置です。問題を連続して作る

ヒント数24

問題集の数字を全てXにしたパターンファイルが Pattern500.txt です。 Java版はこれで試しましたが、Python版は遅いので、とりあえるヒント数24個の問題が６問入ったファイル 24P.txt で試してみます。

Python$ python3 NP.py -g data/24P.txt
No.1   H 24
- X - - - X - - -
X - - X - - X - -
- - X - - - - X X
- - - - X - - X X
- - - X - X - - -
X X - - X - - - -
X X - - - - X - -
- - X - - X - - X
- - - X - - - X -
*SUCCESS  TRY 0
- 4 - - - 2 - - -
7 - - 5 - - 4 - -
- - 5 - - - - 2 7
- - - - 7 - - 3 1
- - - 2 - 9 - - -
9 3 - - 1 - - - -
8 2 - - - - 3 - -
- - 9 - - 1 - - 2
- - - 3 - - - 5 -

No.2   H 24
- - X X - - - - -
- X - - - - X X -
- X - - X - - - X
- - - - X - - - X
- - X X - X X - -
X - - - X - - - -
X - - - X - - X -
- X X - - - - X -
- - - - - X X - -
*SUCCESS  TRY 0
- - 5 4 - - - - -
- 7 - - - - 2 5 -
- 8 - - 6 - - - 3
- - - - 7 - - - 8
- - 6 1 - 2 7 - -
3 - - - 4 - - - -
6 - - - 5 - - 7 -
- 4 8 - - - - 1 -
- - - - - 6 5 - -

No.3   H 24
X - - - - X X X -
- - X - - - - - X
- X - - X - - - X
- - - X - - - - X
- - X - - - X - -
X - - - - X - - -
X - - - X - - X -
X - - - - - X - -
- X X X - - - - X
*SUCCESS  TRY 0
7 - - - - 9 6 3 -
- - 4 - - - - - 5
- 5 - - 1 - - - 9
- - - 5 - - - - 4
- - 1 - - - 5 - -
9 - - - - 8 - - -
1 - - - 3 - - 8 -
8 - - - - - 7 - -
- 2 3 9 - - - - 6

No.4   H 24
X - - - - X - - X
- X - X - - X - -
- - - - X - - X -
- X - - - X - - X
- - X - - - X - -
X - - X - - - X -
- X - - X - - - -
- - X - - X - X -
X - - X - - - - X
*SUCCESS  TRY 0
3 - - - - 5 - - 1
- 9 - 4 - - 6 - -
- - - - 6 - - 3 -
- 7 - - - 4 - - 8
- - 5 - - - 4 - -
4 - - 2 - - - 1 -
- 6 - - 5 - - - -
- - 8 - - 3 - 9 -
2 - - 9 - - - - 3

No.5   H 24
- - - - - X X - -
- - - - - X - X -
- - X X - - X X -
- X - X - - - - -
- X X - - - X X -
- - - - - X - X -
- X X - - X X - -
- X - X - - - - -
- - X X - - - - -
*SUCCESS  TRY 0
- - - - - 5 4 - -
- - - - - 7 - 6 -
- - 6 9 - - 1 2 -
- 8 - 2 - - - - -
- 1 5 - - - 2 7 -
- - - - - 4 - 8 -
- 4 1 - - 9 3 - -
- 5 - 7 - - - - -
- - 3 1 - - - - -

No.6   H 24
- - X X - - - - -
- - X - - X - - -
- - - - - X - X X
- X X X - X - - X
- - - - - - - - -
X - - X - X X X -
X X - X - - - - -
- - - X - - X - -
- - - - - X X - -
**SUCCESS  TRY 1
- - 9 1 - - - - -
- - 1 - - 8 - - -
- - - - - 2 - 3 9
- 1 4 9 - 5 - - 6
- - - - - - - - -
3 - - 4 - 6 2 5 -
5 4 - 2 - - - - -
- - - 8 - - 7 - -
- - - - - 9 3 - -

total 6  failure 0
Time    17.409099 sec

失敗(failure)は0です。ヒント数24の問題を6問作成して、17.4秒で終えました。 1問あたり2.9秒で作れています。かなり高速です。

ヒント数22

ヒント数22の問題を50問のパターンファイル 22P.txt

Python$ python3 NP.py -g data/22P.txt
No.1   H 22
- X - - - X X - -
X - - - X - - - -
- - - - X - - - X
- - - X - - - - X
- X X - - - X X -
X - - - - X - - -
X - - - X - - - -
- - - - X - - - X
- - X X - - - X -
**SUCCESS  TRY 1
- 5 - - - 4 9 - -
4 - - - 3 - - - -
- - - - 9 - - - 3
- - - 2 - - - - 9
- 7 6 - - - 4 5 -
1 - - - - 5 - - -
5 - - - 1 - - - -
- - - - 2 - - - 1
- - 4 9 - - - 6 -

◇ ◇ 中略 ◇ ◇

No.50   H 22
- X - - - - - - X
X - X - - - X - -
- X - - - X - X -
- - - - X - X - -
- - - X - X - - -
- - X - X - - - -
- X - X - - - X -
- - X - - - X - X
X - - - - - - X -
***SUCCESS  TRY 2
- 7 - - - - - - 8
1 - 6 - - - 2 - -
- 9 - - - 5 - 4 -
- - - - 5 - 6 - -
- - - 4 - 1 - - -
- - 5 - 6 - - - -
- 3 - 7 - - - 8 -
- - 2 - - - 5 - 4
8 - - - - - - 7 -

total 50  failure 0
Time    680.092216 sec

失敗(failure)は0です。ヒント数22の問題を50問作成して、680秒で終えました。 1問あたり13.6秒で作れています。ちょっとゆっくりになってきました。

ヒント数20

ヒント数20の問題を38問のパターンファイル 20P.txt

Python$ python3 NP.py -g data/20P.txt
No.1   H 20
X X - - - - - - X
- - - - - - - - X
- - - X X - - - -
- - - X - X X - -
- - X - - - X - -
- - X X - X - - -
- - - - X X - - -
X - - - - - - - -
X - - - - - - X X
*****************SUCCESS  TRY 16
3 8 - - - - - - 6
- - - - - - - - 3
- - - 1 4 - - - -
- - - 6 - 8 1 - -
- - 1 - - - 5 - -
- - 4 3 - 2 - - -
- - - - 7 4 - - -
9 - - - - - - - -
7 - - - - - - 9 2


◇ ◇ 中略 ◇ ◇


No.38   H 20
- - X - - - - - -
X - - X - - - - -
- X - - X - - - X
X - - X - - - X -
- - X - - - X - -
- X - - - X - - X
X - - - X - - X -
- - - - - X - - X
- - - - - - X - -
*****SUCCESS  TRY 4
- - 5 - - - - - -
2 - - 5 - - - - -
- 3 - - 4 - - - 9
1 - - 2 - - - 6 -
- - 7 - - - 2 - -
- 4 - - - 5 - - 3
6 - - - 9 - - 1 -
- - - - - 7 - - 5
- - - - - - 6 - -

total 38  failure 0
Time    4510.304476 sec

失敗(failure)は0です。ヒント数20の問題を38問作成して、4510秒で終えました。 1問あたり118.6秒(約２分)で作れています。かなりゆっくりになってきました。

500問連続生成

では、500問のパターンファイルで、一気に500問を自動生成してみよう。

Python$ python3 NP.py -g data/Pattern500.txt
No.1   H 18
- - - - X - - - -
- - - X - X - - -
X X - - - - X - -
- - X - - X - - -
- X - - - - - X -
- - - X - - X - -
- - X - - - - X X
- - - X - X - - -
- - - - X - - - -
**************SUCCESS  TRY 13
- - - - 3 - - - -
- - - 6 - 2 - - -
9 8 - - - - 1 - -
- - 2 - - 9 - - -
- 7 - - - - - 8 -
- - - 1 - - 5 - -
- - 6 - - - - 2 9
- - - 5 - 7 - - -
- - - - 8 - - - -

No.2   H 18
- X - - - - X - -
- X - X - - - X -
- - - X - - - - -
- - - - - X X - -
- - X - - - X - -
- - X X - - - - -
- - - - - X - - -
- X - - - X - X -
- - X - - - - X -
*************************SUCCESS  TRY 24
- 3 - - - - 7 - -
- 9 - 2 - - - 5 -
- - - 8 - - - - -
- - - - - 4 6 - -
- - 1 - - - 3 - -
- - 2 1 - - - - -
- - - - - 6 - - -
- 4 - - - 3 - 9 -
- - 8 - - - - 2 -

◇ ◇ 以下略 ◇ ◇

とても時間がかかるので、中断しました。１日くらいかかりそうです。

問題作成の難易度（失敗のしやすさ）は、パターンによってかなり違います。ヒント数が少なくなることも、作りにくくします。

このような感じで、問題を作成することができます。

問題ファイルはパターンファイルとして使用可能

実は、問題ファイルを、そのままパターンファイルとして利用することができます。同じファイルを、-s で動かすと、指定されたファイルを問題ファイルとして実行します。 -g で動かすと、マスが - になっていない箇所は全てヒントマスの指定と解釈して解きます。

Python$ cat data/HeartQ.txt
Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 3 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -
Python$ python3 NP.py -g data/HeartQ.txt
No.1   H 20
- - - - - - - - -
- X X - - - X X -
X - - X - X - - X
X - - - X - - - X
X - - - - - - - X
- X - - - - - X -
- - X - - - X - -
- - - X - X - - -
- - - - X - - - -
********************************SUCCESS  TRY 31
- - - - - - - - -
- 2 6 - - - 8 9 -
3 - - 2 - 5 - - 1
1 - - - 9 - - - 4
5 - - - - - - - 3
- 3 - - - - - 5 -
- - 8 - - - 6 - -
- - - 1 - 4 - - -
- - - - 3 - - - -

total 1  failure 0
Time    386.002062 sec

immunity39/puzzle-generator-py