puzzle-generator

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

方針

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

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

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

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

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

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

説明しないこと

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

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

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

すごく頑張れば、ギネス世界記録(TM)になった280合体ナンプレも作れる。

プログラムについて

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

Javaソースプログラム(/src)

169 Generator.java
231 NP.java
62 Solution.java
278 Solver.java
740 合計

メインクラスはNPです。パッケージは、簡易にnp0(package np0)にしています。

NP.jar 実行プログラム

Problem500.txt 問題サンプル500問
Pattern500.txt 問題ヒントパターン500問分
HeartQ.txt ハートの形の問題
HeartP.txt ハートの形のヒントパターン
18P.txt ヒント数18のパターン数種
17P.txt ヒント数17のパターン数種

以下、Eclipse上で実行ファイルNP.jarを作成した場合の実行。

$ java np0/NP
===== arguments input error =====
java -jar NP.jar  -s  problem_file	[answer_file]
java -jar NP.jar  -g  pattern_file	[problem_file]

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

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

実行するだけ

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

現在、\Users\fuji\Desktop\ナンプレに居て、ファイル構成が以下のようになっているとします。

C:\Users\fuji\Desktop\ナンプレ>tree /F

//フォルダー パスの一覧
C:.
│  NP.jar
│
├─data
│  	17P.txt
│  	18P.txt
│  	HeartP.txt
│  	HeartQ.txt
│  	Pattern500.txt
│  	Problem500.txt
│
└─src
    	contributing.md
    	Generator.java
    	NP.java
    	Solution.java
    	Solver.java

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar
===== arguments input error =====
java -jar NP.jar  -s  problem_file	[answer_file]
java -jar NP.jar  -g  pattern_file	[problem_file]

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

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

問題を解く

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

正常な問題を解く

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar -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
total time : 759200 nano sec,	average : 759 micro sec

最後に与えられた問題数きちんと解けた問題数全体の計算時間（ナノ秒単位）１問あたりの平均計算時間（マイクロ秒）を表示します。

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

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

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

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar -s data\HeartQ1.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
total time : 666900 nano sec,	average : 666 micro sec

エラーの場合

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

C:\Users\fuji\Desktop\ナンプレ>type data\HeartQ2.txt


Heart   H 20
- - - - - - - - -
- 1 6 - - - 5 9 -
4 - - 8 - 7 - - 2
7 - - - 5 - - - 1
8 - - - - - - - 9
- 6 - - - - - 7 -
- - 5 - - - 6 - -
- - - 2 - 3 - - -
- - - - 7 - - - -

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

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar -s data\HeartQ2.txt


Heart   H 20
ERROR
Total 1	Success 0
total time : 175200 nano sec,	average : 175 micro sec

問題を作る

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

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar -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 91
- - - - - - - - -
- 7 5 - - - 9 2 -
6 - - 4 - 9 - - 3
1 - - - 5 - - - 4
3 - - - - - - - 6
- 4 - - - - - 3 -
- - 2 - - - 5 - -
- - - 3 - 1 - - -
- - - - 4 - - - -

total 1  failure 0
total time : 3902 mili sec,	average : 3902 mili sec

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

次の例は、

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar -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
total time : 15727 mili sec,	average : 15727 mili sec

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

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

問題を連続して解く

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

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar -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
total time : 55101600 nano sec,	average : 110 micro sec

一気に解いて、1問平均で110マイクロ秒の速度で解きました。

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

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

問題集の数字を全てXにしたパターンファイルが　Pattern500.txt　です。

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar -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 8
- - - - 7 - - - -
- - - 4 - 6 - - -
5 2 - - - - 3 - -
- - 4 - - 9 - - -
- 8 - - - - - 7 -
- - - 3 - - 5 - -
- - 1 - - - - 4 8
- - - 7 - 3 - - -
- - - - 5 - - - -

No.2   H 18
- X - - - - X - -
- X - X - - - X -
- - - X - - - - -
- - - - - X X - -
- - X - - - X - -
- - X X - - - - -
- - - - - X - - -
- X - - - X - X -
- - X - - - - X -
*****SUCCESS  TRY 4


◇　◇　中略　◇　◇


*SUCCESS  TRY 0
- - - - - 8 3 - -
- - - - - 4 - 5 -
- - 1 3 - - 7 8 -
- 5 - 8 - - - - -
- 6 3 - - - 1 2 -
- - - - - 5 - 6 -
- 7 8 - - 6 9 - -
- 4 - 9 - - - - -
- - 2 4 - - - - -

No.500   H 23
- - 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 4
- - 9 2 - - - - -
- - 8 - - 7 - - -
- - - - - 9 - 1 4
- 1 2 5 - 4 - - 3
- - - - - - - - -
9 - - 1 - 3 2 8 -
4 5 - 3 - - - - -
- - - 4 - - - - -
- - - - - 8 7 - -

total 500  failure 0
total time : 133233 mili sec,	average : 266 mili sec

失敗(failure)は0です。500問の作成を133秒で終えました。 1問あたり266ミリ秒(0.266秒)で作れていますので、かなり高速に作成できています。

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

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

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

C:\Users\fuji\Desktop\ナンプレ>java -jar NP.jar -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 11
- - - - - - - - -
- 3 8 - - - 7 4 -
2 - - 3 - 6 - - 1
6 - - - 4 - - - 5
1 - - - - - - - 3
- 2 - - - - - 1 -
- - 7 - - - 8 - -
- - - 1 - 5 - - -
- - - - 6 - - - -

total 1  failure 0
total time : 518 mili sec,	average : 518 mili sec

Name		Name	Last commit message	Last commit date
Latest commit History 2 Commits
data		data
src		src
.gitignore		.gitignore
NP.jar		NP.jar
README.md		README.md
puzzle-generator_guide.pdf		puzzle-generator_guide.pdf

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

puzzle-generator

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

方針

説明しないこと

プログラムについて

Javaソースプログラム(/src)

NP.jar 実行プログラム

実行するだけ

問題を解く

正常な問題を解く

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

エラーの場合

問題を作る

問題を連続して解く

About

Releases

Packages

Languages

timedia/puzzle-generator

Folders and files

Latest commit

History

Repository files navigation

puzzle-generator

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

方針

説明しないこと

プログラムについて

Javaソースプログラム(/src)

NP.jar 実行プログラム

実行するだけ

問題を解く

正常な問題を解く

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

エラーの場合

問題を作る

問題を連続して解く

About

Resources

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages