AIを利用した
ナンプレの問題自動生成
進化計算（山登り法）によるゼロからの進化計算

株式会社タイムインターメディア
知識工学センター
UECアライアンスセンターはじめに

第１部 問題を解く
第２部 問題を作る
第３部 発展課題編

1

はじめに
タイムインターメディアは、世界最大の合体ナンプレ問題制作や、あらゆる業務で発生する複雑な組み合わせ問題を最適化する進化計算「天啓｜TENKEI」のサービスなど、パズル自動生成の研究によって培った技術を用いて、幅広い分野に貢献してまいりました。
そんな技術により興味を持っていただきたいとの想いから、 問題を解くプログラムの作成ではなく、さらにその先の「問題を作る(作問)プログラム」を公開します。
公開されるソースコードは、数多くのパズル問題を世に生み出し、世界記録の達成を果たした藤原 博文によって作られたものです。
パズル作家が多くの時間を費やすような難解で複雑な問題も、もちろん作成可能です。
本ソースコードと一般的なPCで、短時間で良質な問題を自動生成します。
また、世の中にある様々な最適化問題にも応用が可能な「進化計算」というAIアルゴリ
ズムを用いた作成を行うため、今回のプログラムで学習したアルゴリズムをパズル以外のことへ応用することが可能です。
以下に、ナンプレ自動生成エンジンの作成手順とソースコードを公開しておりますので、お気軽にエンジン自作に挑戦してみてください。
GitHub: https://github.com/timedia/puzzle-generator
関連リンク：● ギネス世界記録™達成！TIM提供、世界最大のマルチナンプレ・パズル～『数学の祭典 MATH POWER 2018』にて正式認定～ プレスリリース 2018年10月10日(https://www.timedia.co.jp/news/20181010-release/)● 「進化計算 天啓｜TENKEI」公式サイト(https://www.timedia.co.jp/service/tenkei/)● 「進化計算 天啓｜TENKEI」特設サイト(https://tenkei.ai/)● 超絶難問ナンプレ キャンペーン
(https://www.timedia.co.jp/puzzle/puzzle-202104/)2

ナンプレとはナンプレのルール・遊び方
ナンプレ(ナンバープレイス)とは、歴史ある数字パズルゲームです。
海外では、SUDOKU(数独)とも呼ばれ、世界的な流行が今も続いています。

1.右図の様に、9x9のマスが、太さの違う罫線で描かれており、マスの一部に数字が入っています。
2.たて9マス、よこ9マス、太線で囲まれた9マス(ブロックと呼ぶ)の中には、1から9までの数字がそれぞれ１つずつ入ります。
3.2.のルールにしたがって、空白の各マスに、1から9の数字を入れます。
4.この問題を、ルールに従って解くと右図のように全マスが埋まります。どのたて列、どのよこ列、どのブロックを見ても、1から9までの数字が1つずつ配置されています。
書店では、ナンプレの問題集が数多く販売されており、ネット上でも無料で遊べるWebサイト、アプリが多数あります。
さらに、問題が難しくて解けないときには、解を教えてくれる親切なサイトも存在します。
この解説では、問題を解くプログラムの作成ではなく、さらにその先の「問題を作る(作問)プログラム」の説明をします。
問題を何とか作れる程度ではなく、パズル作家が多くの時間をかけて制作するレベルの問題を、普通のパソコンでラクラクと作れる方法をご説明します。
それも、非常に簡単なアルゴリズムで。

3

大まかな作成手順
右図のように最初から見える数字(ヒント)の配置を与えて、これらのマスの数字を適当に決めることで、解が1つだけ(ユニーク解)の問題(最初の図)を自動生成する方法を説明します。
ただ、適当に数字を並べて入れ替える程度では、延々と入れ替えを繰り返してもユニーク解にはなりません。
人工知能技術の1つに進化計算という方法があり、これは生物の進化にならって、少しずつ良くする(進化する)ことで最終的な目的を達成しようという方法です。ナンプレの自動生成の場合には、解がただ1つ(ユニーク解)のちゃんとした問題を完成させます。
人工知能技術というと高度で無理と思うかもしれませんが、とても簡単な方法しか使わないので、プログラミングを始めたばかりの方でも十分理解できると思います。プログ
ラムもそんなに長くなく、全体を把握しやすくなっています。
人工知能の中の、進化計算という技術の中で最もやさしい手法である山登り法を用いて説明します。
山登り法は簡単な問題にしか適用できない方法ですが、ここではそれをさらに簡単化した方法を紹介しています。
9x9の標準的なナンプレ問題の自動作成なら、これでも楽勝です。
プログラミング言語はJavaを用いていますが、Java以外の言語でも全然問題ありません。Java,C,C++,C#などが一般的に適しているでしょうが、Pythonでもできます。
Scratchでナンプレの自動生成を作った例もあります。

元になったプログラム
ここで紹介するプログラムは、2019年2月に、タイのタマサート大学シリントーン国際
工学部の学生を日本に招待し、インターンシップ実習をしたときに用意したプログラムが元になっています。
当時はRaspberry Pi3で動かしており、Javaの開発環境であるEclipseも使っていませんでした。

4

関連リンク:● インターンシップfromThailand！@電気通信大学(UEC)(https://www.timedia.co.jp/news/20190319-timrelease/)

最終目的と注釈
Javaのプログラムは自由に改変してご利用ください。実際に問題を便利に作ったり、できた問題を画面上で遊ぶためにはGUIも必要でしょう。でも、本説明はあくまで自動生
成はこうすれば簡単にできるという一例を示すのが目的ですので、本質的以外の部分は全部省略しています。

Javaのコーディングも、模範的でない箇所も多々あります。また、ファイル入力の扱いなど、柔軟性を欠いているところもありますが、それらも皆さんへの課題として残したままにしています。
本格的な進化計算を行う場合は、山登り法ではなく遺伝的アルゴリズムを使うことが多くなります。また、計算量が増えるため、高速化にマルチスレッドを使うのが一般的です。
さらに、現実の最適化問題は、複数の相反する項目の調整も必要になることが多く、多目的遺伝的アルゴリズムが使われるようになります。
本プログラムのソースコードを使い、進化計算の第一歩を経験してください。そして皆さんの技術や興味がさらに広がり、進んでいかれることを期待しています。

5

第１部 問題を解く

ナンプレの問題を作るのですが、その前に、ナンプレの問題を解くプログラムを完成させる必要があります。問題を解くプログラムのことをソルバーと呼び、問題を作るプロ
グラムをジェネレータと呼びます。
問題の自動生成をするとき、ジェネレータは頻繁にソルバーを呼び出します。普通は、市販の問題集とか、ネット上に公開されている問題などを解くことが多いので、解が一意に決まる問題を解くソルバーを作ることが多いと思います。
しかし、問題を作る場合には、未完成の色々トラブルのある問題を解く必要があり、どのくらいトラブルがある問題かを調べます。そのため、不完全な問題、矛盾している問題を解けるところまで解くプログラムが必要になります。

6

では、実際にプログラムを見ていきましょう。
プログラムは、自動生成も含め全体で744行になっています。
169 Generator.java
235 NP.java
62 Solution.java
278 Solver.java
744 合計

NP.javaがメインプログラムで、問題を解くときは問題ファイル、問題を作成するときはパターンファイルを読み込みます。その後、実際に問題を1問解くのがSolver.java
で、１つのパターンに対して問題を自動生成するのがGenerator.javaです。
Solverの方が、Generatorより行数が多くなっています。このプログラムでは、解くための様々なテクニックを組み込んでいないので、Solverはかなり簡単になっています
が、それでもGeneratorよりも長くなっています。様々な高度なナンプレを解くテク
ニックを組み込もうとすると、Solverがどんどん長くなっていきます。
Generatorが非常に難しいという印象が世間にはあるようですが、実際にはSolverの方が面倒です。さらに、Generatorは、別のパズルの自動生成をする場合もほとんどそのまま使えますが、Solverはパズルが異なれば作り直す必要があります。

まず、問題ファイルを用意します。
問題ファイルは、問題のタイトル行と、それにつづく問題を図のように用意します。
１〜９のマスは、そのまま数字が入り、数字のないマ
スには−(マイナス)が入っています。また、カラムとカラムの間、横方向には間にスペース１文字が入っています。
複数の問題が１つのファイルに入っている場合、問題間に行は開けず、タイトル行、問題、タイトル行、問題を繰り返します。

7タイトル行の内容は任意ですが、適当な名前（問題番号）とヒント数を示すようにしています。
プログラムをコンパイルし、実行可能なjarファイルを用意します。
ここでは、NP.jarという実行可能なjarファイルを作った場合について説明しています。
HeartQ.txtの場合、この問題を解くコマンドおよび実行結果は次の問題ファイルがようになります。

8

実行はLinux上で行っていますが、同じことをWindows上のコマンドプロンプトで行うことができます。
まず、読み取った問題をそのまま表示しています。
その直後に0だけの行があります。
この行は、問題の不都合度を示し、0は、ユニーク解だったことを示しています。従って、上記のハートは、正しい問題だったことが分かります。
その次に、解を示しています。
問題、解のいずれも、数字、空きマスだけを示し、罫線は省略しています。
ファイル中の全問題を解いた後に、トータルの問題数と成功数が示されます。
最後に、全体の時間(total time)をナノ秒(10億分の1秒)単位で示し、最後に平均時間(average)をマイクロ秒（100万分の1秒）単位で示しています。
添付のサンプル問題500題を解くと以下のようになります。

1問あたり、183マイクロ秒で解けていることが分かります。

9

NP.java
では、プログラムで、問題を読み込み、実行する部分を追いかけていきましょう。
NP.javaの最後に、main(String[] args)があります。
コマンドオプションで−sを付けた時に、引数のファイルを問題ファイルとみなして

解きます。
223

np.solveNP();

これが、解くプログラムを呼び出しています。

class Problem
solverNP()の説明の前に、ソルバー、ジェネレー共通でよく利用する問題データクラス(class Problem)を説明します。

３つの配列が宣言されています。いずれも９×９の配列ですが、ここではサイズを指定していません。
Problemは問題を、answerは解を、patternはヒントパターンを入れておく配列です。
idは、問題のタイトルを文字列で記憶しておくためのものです。
blanksは、問題を解いた時に決められなかったマスの数（ブランクのマス数）で、問題を自動生成するときの参考にします。

10

solveNP()
問題を連続して解くメソッドがsolveNP()です。
98

private void solveNP() {99

Solver solver = new Solver();

100

ArrayList<Problem> problems = new ArrayList<>();

101
102

try {

103

while( datainput.hasNextLine()) {104

Problem pr = new Problem();

105

pr.id = readProblemTitle();106

pr.problem = readProblemBody();107

problems.add(pr);

108
109

}
} catch( Exception ex ) {}

110
111

long startTime = System.nanoTime();

112
113

for( Problem pb : problems ) {114

pb.blanks = solver.solve(pb.problem);

115

if( pb.blanks >= 0 )

116
117

pb.answer = solver.getAnswer();
}

118
119

long endTime = System.nanoTime();

120
121

int success = 0;122for( Problem pb : problems ) {123

if( dataoutput!=null)

124
125

dataoutput.println(pb.id);
System.err.println(pb.id);

126
127
128

if( pb.blanks < 0 ) {if( dataoutput!=null)
11

129

dataoutput.println("ERROR");130

System.err.println("ERROR");131} else {132

if( dataoutput!=null) {133

dataoutput.println(pb.blanks);

134

printBoard(dataoutput,pb.answer);

135

}

136

printBoard(System.err,pb.problem);

137

System.err.println(pb.blanks);

138

printBoard(System.err,pb.answer);

139

System.err.println();

140

}

141

if( pb.blanks==0 )142++success;

143

}

144
145

int probSize = problems.size();

146

System.err.println("Total "+probSize+"

Success "+success);

147
148

long timediff = endTime - startTime;149

System.err.println("total time : " + timediff +" nano sec,

150

" +

"average : " + timediff/probSize/1000 +" micro sec" );151}

最初のwhileループで全問題をArrayList<Problem> problemsに次々と読み込みます。
１問読んでは解き、次の問題を読んでは解くという方法もありますが、これでは解く時の時間計測が面倒になるので、最初に全問を読み込んでArrayListの形で溜め込んでおき、次に全問を次のforループで解きます。

12

113

for( Problem pb : problems ) {114

pb.blanks = solver.solve(pb.problem);

115

if( pb.blanks >= 0 )116

pb.answer = solver.getAnswer();117}

どんなに多い問題数でも、このforループの中で全部解かれます。
1つの問題を解くのは、solver.solve(pb.problem)で行われます。
戻り値が負だと、何らかのエラー（不都合）が発生しています。
戻り値が0または正の場合、ソルバーから答えを取り出し、pbオブジェクトのanswerに入れます。
この2番めのforループの前後で時間計測をして、その差を実行時間として最後に示しています。
最後の長めのforループで、解いた結果を表示したりファイルに書き込んでいます。
盤面のプリントとして２つのprintBoardメソッドがあり、引数により盤面のプリント
か、パターンのプリントかを区別しています。
printBoard(PrintStream ps, int[][] bd)
printBoard(PrintStream ps, boolean[][] bd)
あまり本質的な部分ではないので、説明は省略しますので、各自でご確認ください。
114

pb.blanks = solver.solve(pb.problem);

ここで、ソルバークラスのsolveメソッドを呼び出しています。

13

Solver.java
では、Solverクラス(Solver.java)を調べましょう。
12

public class Solver {13

private14

private boolean[][][]

int[][]

board;
candidate;

ソルバークラスの先頭で、２つの配列が宣言されています。
これらは、いずれも問題を解く時の作業用配列です。
problemは、今解いている問題が入っています。
基本的にはNPの方から渡される問題と同じですが、引数で渡された問題の数字を１つずつチェックしながら、Solverのメンバー変数problemにコピーしていきます。（詳しくは後述）
boardは問題を解き進めるための作業用の配列で、解き終わったときには問題を解が入っています。
problem, boardのいずれも、0は空白（未定）を意味します。
candidateは3次元のboolean配列です。
第1次元は行（y座標）、第2次元は列（x座標）を示すのは、problem、boardと同じです。値の範囲は0〜8で、ゼロベースになっています。これは、１ベースよりも計算上都合が良いので、そのようにしています。
candidate[r][c][n]r : 行（row）（0〜8）

c : 列（column）（0〜8）

n : 候補数字（1〜9）

第3次元が候補数字を示します。

14

問題を解く時、まだ数字の入っていないマスには、１〜９までの数字が入る可能性があります。しかし、問題の初期ヒントの数字の影響や、解き進んたときに決めたマスの数
字の影響で、各マスに入れられる数字はどんどん減っていきます。
右図の白マスに小さく書かれている数字が候補数字です。ルールに従って、同じタテ、
同じヨコ、同じ３×３のブロックにある数字を候補から削除すると、図のように減ってきます。
候補数字の部分だけ、添字として１〜９を使っています。これは、0〜8を使うより便利
なので、配列が少し無駄になるけれども、そのようにしています。
このcandidateを監視し、決まる箇所を次々と決めていくことがナンプレを解くことになります。同じカラムの9つの候補の内、１つだけがtrueになったとき、そのマスはその数字に決定します。
では、実際にプログラムに従って、動きを見ていきましょう。

15

solve( int[][] bd )18

public int solve( int[][] bd ) {19

int blanks;

20
21

initialize();

22

blanks = setProblem(bd);23

if( blanks < 0 )24

return -1;

25

return solve();26}

最初にinitialize()で初期化します。
initialize()は49行からですが、Solverオブジェクトの3つの配列を予期化しているだけです。
setProblem(bd)で、引数で渡された問題を、オブジェクトのメンバー配列にセットします。そして、その間にも問題のチェックを行い、問題があれば負の値を返してきます。
問題がないことが分かれば、そこでsolve()を呼び出し、実際に解きます。solve()も空白マス数を返してくるので、その値をそのまま戻り地にします。この最後のsolve()
は、延々と可能な限り解き進めます。（詳細は後述）
したがって、solve( int[][] bd )の戻り値は、空白マス数になります。

setProblem( int[][] bd )setProblem( int[][] bd )は、引数で与えられた問題の数字をチェックしながら、作業用ボード配列boardと、候補配列candidateを変更していきます。
全体をtry-catchで括っていますが、これは矛盾することがあればSolverExceptionが発生するのを捉えるためです。
最初の２重のforループで、与えられた問題の実際に数字が入っているマスについてだ
け

setValue( c, r, bd[c][r] );を呼び出している。

16

これは、与えられた数字を、指定の場所に設定するためのメソッドを呼び出しているのですが、この呼び出したメソッドの中で、マスに数字を入れる場合のチェックが行われ
ています。
48

private int setProblem( int[][] bd ) {

49

try{

50

for(int r = 0; r < NP.SIZE; r++)51

for(int c = 0; c < NP.SIZE; c++)52

if( bd[c][r] != 0 )53

setValue( c, r, bd[c][r] );54} catch(SolverException e) {55

return -1;

56

}

57
58
59

return blankCount();}

全体をtry-catchで括って、SolverException例外を補足していました。
SolverExceptionは、Solver.javaの先頭の方で宣言されています。
10class SolverException extends Exception {}// Exception

setValue( int r, int c, int v )第１、第２引数でマスの位置を示し、第３引数でマスにセットすべき値を示します。
単にマスにその値を入れるのではなく、きちんとチェックして問題がなければ値をセットします。
もし何らかの矛盾が起きると、throw new SolverException();により例外処理を発生させ、より上位の

try-catchで捕捉します。

17

90

private void setValue( int r, int c, int v )throws SolverException {91

if( !candidate[r][c][v] ) {92

throw new SolverException();

93

}

94

if( board[r][c]!=0 ) {95

if( board[r][c] != v ) {96

throw new SolverException();

97

}

98

return;

99

}

100
101

board[r][c] = v;

102

for( int n=1; n<=NP.SIZE; ++n )103

candidate[r][c][n] = false;

104
105

int r0 = (r/NP.SUBSIZE)*NP.SUBSIZE;

106

int c0 = (c/NP.SUBSIZE)*NP.SUBSIZE;

107

for( int i=0; i<NP.SIZE; ++i ) {108

candidate[r][i][v] = false;

109

candidate[i][c][v] = false;

110

candidate[r0+(i/NP.SUBSIZE)][c0+i%NP.SUBSIZE][v]= false;

111
112

}
}

まず、candidate[y][x][v]がtrue、つまりそのマスにその数字をセットして良いか確認します。
次に、数字を入れるマスに既に０以外の数字が入っていて、その数字がこれから入れようとする数字と異なる場合、例外を発生します。問題として与えられた数字が、他のマスの関係から既に決定しいることもあるので行っている確認です。
これで問題なければ、board[y][x] = v; で数字をセットします。

18

次に、数字を決めたことで、候補配列candidateの、入れた数字の影響を受ける部分を全部falseにします。

solve()
28

public int solve() {

29

try {

30

checkLoop();31} catch( SolverException e) {32

return -1;

33

}

34

return blankCount();

35}

現状のboardで、どこまで解けるか延々と試します。
実際に試すのは、checkLoop();の中です。
問題なく解き進められたら、最後にブランクマスを数えて戻り値とします。

checkLoop()
ルールに従って、決まるところがあるか、延々と調べます。
全体は、何らかの変化がある限り、forループを永久に回ります。そのうち変更することが無くなるか、矛盾が発生してループが終了する筈です。
Forループの中が4つの処理に分かれています。
①3x3のブロックで、決まるところを探す。行rと列cを、3ずつ増加。
②ヨコ列について決まるところをチェックする。
③タテ列について決まるところをチェックする。
④マス（cellと呼ぶ）についてチェックする。

19

61

private void checkLoop() throws SolverException {62

for(boolean changed=true; changed; ) {63changed = false;64
65

for( int r = 0; r < NP.SIZE; r+=NP.SUBSIZE ) {// 3x3 Block Check66

for( int c = 0; c < NP.SIZE; c+=NP.SUBSIZE )67

if( checkBlock(c,r) )68changed = true;

69

}

70
71

for( int r = 0; r < NP.SIZE; ++r ) { // HLine check72

if( checkHline(r) )73changed = true;

74

}

75
76

for( int c = 0; c < NP.SIZE; ++c ) { // VLine check77

if( checkVline(c) )78changed = true;

79

}

80
81

for(int r = 0; r < NP.SIZE; r++ )82

for(int c = 0; c < NP.SIZE; c++ )83

if( checkCell(c,r) )84

changed = true;85
86// Cell check}}

それぞれについて、専用のチェックメソッドが用意されています。チェックメソッドがtrueを返してきた時、新たに数字が決まった、つまり変化があったので、変更フラグ
checkをtrueにします。
forループを一周して何か変化が起きた場合には、forループをまた最初から続けます。

20

一周して何も変化が起きなかった場合は、これ以上ループを回り続けても無駄なので終了します。
ループ中に矛盾を発見することがあり、その場合にはチェックメソッドがSolverExceptionを発生します。

checkBlock( int c0, int r0 )3x3のブロックをチェックするのがcheckBlockメソッドです。
引数c0,r0は、ブロックを左上隅で指定します。
一番外側のforループのnは、指定した3x3のブロック内で決められる数字
を1から順に調べるための変数です。
既にブロック内に数字nが存在する場合があり、その場合はそれ以上調べる必要がありません。
154

private boolean checkBlock( int c0, int r0 )throws SolverException {155boolean changed = false;

156
157

for( int n=1; n<=NP.SIZE; ++n ) {158boolean exist = false;

159

int cnt = 0;160

int col = 0;161

int row = 0;

162

for( int r=r0; r<r0+NP.SUBSIZE; ++r )163

for( int c=c0; c<c0+NP.SUBSIZE; ++c ) {164

if( board[r][c] == n )165

exist = true;166

if( candidate[r][c][n] ) {167++cnt;

168

col = c;169

row = r;

21

170

}

171

}

172
173

if( !exist ) {174

if( cnt == 1 ) {175

setValue( col, row, n );176

changed = true;177} else if( cnt == 0 ) {178

throw new SolverException();

179

}

180

}

181

}

182
183
184

return changed;}

そうでない場合には、ブロック内のどこかのマスが数字nに決まる可能性があります。
そのため、ブロック内の数字nの候補の数(candidate[r][c][n]がtrueの数)を数えます。
そして、そのマスの位置をcolとrowに記憶しておきます。
前半のforループを終えたら、ブロック内の数字nの候補数と、数字nが既にブロック内
で決まっているかが分かっています。
後半で、数字nが決まっていなかった時、そして候補が１つだけだった場合には、そのマスに数字nを入れます。数字をセットするのは、既に説明したsetValueメソッドを用います。このメソッドは、単にマスに数字をセットするだけではなく、その数字をセットしたことで影響を受ける候補の削除も行ってくれます。
まだ数字nが決まっていなくて、数字nの候補数が0、つまりどこにも入れられるところがない場合には矛盾しているので、SolverExceptionを発生します。
このメソッドでは、外側のnのループでは、１つの数字が決まっても、さらに次の数字について調べるようになっていますので、複数の数字を一度の呼び出しだけで決めることもあります。

22

最後に、changedを返すことで、本メソッドで変更があったかどうかが呼び出し元に返されます。

checkHline( int r ),checkVline( int c )private boolean checkHline( int r )private boolean checkVline( int c )この２つのメソッドは、ヨコ列またはタテ列について、決まる数字があるかどうかチェックするもので、checkBlock( int c0, int r0 ) と同じ構成になっています。
ヨコ列またはタテ列の9マスについて調べるので、checkBlockよりも簡単になっていますので、ご自身で内容を確認してください。説明は省略します。

checkCell( int c, int r )checkCellは、１つのマスの候補をだけを調べて数字を決められるかどうかをチェックします。つまり、マスに候補を小さい数字で書き込んだ時、マスに小さい数字（候補）が１つだけだと、その数字がそのマスの数字になります。これを行うのが、checkCellです。
candidate[r][c]は、rとcで指定されたマスに入れられる数字の候補のboolean配列です。もし、この配列でtrueの数を数え上げたとき、１だとその数字に決定します。

23

244

private boolean checkCell( int c, int r )throws SolverException {245

if( board[r][c] != 0 )246

return false;

247
248

int cnt = 0;249

int v = 0;250

for( int n=1; n<=NP.SIZE; ++n ) {251

if( candidate[r][c][n] ) {252++cnt;

253v = n;

254

}

255

}

256
257

if( cnt == 1 ) {258

setValue( c, r, v );259

} else if( cnt == 0 ) {260

throw new SolverException();

261

}

262
263
264

return cnt == 1;}

blankCount()
268

private int blankCount() {269

int cnt = 0;

270
271

for( int r=0; r<NP.SIZE; ++r )272

for(int c=0; c<NP.SIZE; ++c )273

if( board[r][c] == 0 )274++cnt;

275
276
277

return cnt;}
24

同じハートの問題ですが、一番下の２を３に変更しただけで、結果が下図のように変わります。上側が問題、次の１行が残りブランクマス数、最後が問題を解けるところまで解いた結果です。
左は解き切ることができたので、残りブランクマス数は0になっています。
右は解き切ることができず、ブランクマス（未決定マス）を示す−(ハイフン)が29個あることを示しています。
この解けるところまで解き進んで、その時に盤面を示す配列boardの要素が0（ブランク）のマスを数え上げ、戻り値として返します。

ブランクマス数は、問題の自動生成で重要な働きをします。この数字が0に近づくように問題の数字をどんどん入れ替えていき、0になったところでユニーク解になったことが分かるので、そこで問題の調整を完了とし、問題を取り出して表示するのが自動生成で
す。

25

その他
以上が、問題を解くための主要なメソッドです。
それ以外にもいくつかのメソッドを用意しています。
プリント関係では、
printCandidate()

候補(candidate)をプリントする

printBoard()

盤面(board)をプリントするプリントの実体はNP.javaの中のprintBoard
メソッドを利用しているだけです。

がありますが、説明は省略します。
ところで、盤面のプリントなど、さまざまな情報を出力するのに、普通ならSystem.out（標準出力）を使うのですが、このプログラムでは、ほとんどの場合
System.err(エラー出力)を使っています。
わざわざSystem.errを使っているのは、以下の理由からです。何らかのトラブルに対してシステムから出力されるエラーメッセージはSystem.errに出力されるのすが、エラー出力は標準出力もよりも優先して出力されます。こうなると、エラーが発生するよりも前にプリントしたはずの出力が、エラー出力よりも後に表示され、出力の順番とプ
ログラムの流れに不一致が発生し、デバッグに不都合になります。そのため、ほとんどの出力でSystem.errを使っています。
値の取得関係では、
getAnswer()
解をコピーして戻り値として返します。
getValue( int x, int y)
指定したマスの値を返します。
getCandidate( int x, int y)
指定したマスの候補の配列を返します。
がありますが、いずれも簡単ですので、説明は省略します。

以上だけから、500問の問題が入ったProblem500.txtを解かせると、次図のように表示します。解くのにかかった時間は、0.1秒以下になっています。

26

27

第２部 問題を作る

問題を解くソルバーができたので、第2部では、このソルバーを利用して問題を自動生成してみましょう。
問題を作る部分はGenerator.java(Generatorクラス)にまとめられています。
ソルバーSolver.javaよりもGenerator.javaの方がプログラムが短くなっています。
問題を作るのは、解くよりも遥かに困難だと思っていませんか。でも、プログラムの長さを見ると、Generator.javaの方が短くなっています。
これは、問題を解くより作るほうが簡単ということかも知れません。
では、実際に、Generatorはどのようになっているか調べてみましょう。

28

問題を作るときには、コマンドパラメータに -g で問題生成であることを伝え、その後に問題パターンファイルを指定します。
すると、以下のように実行されます。
$ java -jar NP.jar -g 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 - - - *********************SUCCESSTRY 20- - - - - - - - - 1 2 - - - 9 3 9 - - 6 - 5 - - 8
1 - - - 2 - - - 6
8 - - - - - - - 7- 7 - - - - - 8 - - 5 - - - 2 - - - - 2 - 8 - - - - - - 1 - - - total 1

failure 0

total time : 1077 mili sec,

average : 1077 mili sec

29

30

その後に、問題が表示され、*が次々に表示され、SUCCESSと表示されると問題作成に成功したことを示します。その後のTRYは成功までに何度やり直したかの回数を示します。問題作成に成功した場合には、その後に出来上がった問題を表示します。
何度やり直しても成功しない場合には、FAILUREと表示され、問題は表示されません。
最後に、全体の作成時間と、1問あたりの平均作成時間を表示します。
以上が自動生成をしたときの動きですが、これをプログラムでどのように実現しているか見ていきましょう。

NP.java
自動生成(generator)とソルバーはかなり似た構成部分もあり、共通するような部分
は、自動生成関連のプログラムもNP.javaの中に書かれています。

generateNP()
154

Generator generator = new Generator();

155

ArrayList<Problem> problems = new ArrayList<>();

156
157

try {

158

while( datainput.hasNextLine()) {159

Problem pb = new Problem();

160

pb.id = readProblemTitle();161

pb.pattern = readPatternBody();162

problems.add(pb);

163
164

}
} catch( Exception ex ) {}

165
166

long startTime = System.nanoTime();

167
168

int failureCount=0, successCount=0, n=0;
31

169

for( Problem pb : problems ) {170boolean [][] pattern = pb.pattern;

171

System.err.println("No."+(++n)+"172

H "+ coutHint(pattern));if( dataoutput!=null)

173

dataoutput.println("No."+(n)+"174H "+ coutHint(pattern));

printBoard(System.err, pattern);

175
176

if( generator.generate(pattern) ) {177

pb.problem = generator.getProblem();178

if( dataoutput!=null)

179

printBoard(dataoutput,pb.problem);180

printBoard(System.err,pb.problem);

181++successCount;

182} else {183

if( dataoutput!=null)

184

dataoutput.println("FAILURE");

185

System.err.println("FAILURE");

186++failureCount;

187

}

188

System.err.println();

189

}

190
191

long endTime = System.nanoTime();192

long timediff = endTime - startTime;193

int probSize = problems.size();

194

System.err.println("total "+(successCount+failureCount)
+ "

195

failure "+failureCount);

System.err.println("total time : " + timediff/1000000+ " mili sec,

196
197

average : "+ timediff/probSize/1000000 + " mili sec" );}32与えられたパターンファイルを一気に読み込んで、延々と問題を作るメソッドです。構成は、ソルバーのsolveNP()に非常に似ています。
最初にgeneratorインスタンスを生成します。
次に、出来上がった問題を格納するためのArrayList<Problem> problemsを初期化します。
最初のwhileループで、問題パターンを読み込んで、problemsにパターンを入れます。パターンをbooleanの2次元配列に読み込むのが、readPatternBody()メソッドです。（後で説明）
延々と問題を作り続けるのが、真ん中あたりの大きなforループです。
forループの前半で、ヒントの数を数えて、ヒント数とヒントの配置をプリントします。
１つのパターンに対して問題を実際に作るのが、generator.generate(pattern)
で、問題作成に成功するとtrueを、失敗するとfalseを返してきます。
成功のときは出来上がった問題を表示し、失敗したときにはFAILUREの表示します。
そして、成功、失敗の数も数えます。
最後に、現在時刻を求め、問題作成直前の時刻との差より経過時間を求め、1問あたりの時間も表示します。
ということで、実際に問題を作っている部分はgenerator.generate(pattern)であることが分かりました。

33

Generator.java
では、Generatorクラス(Generator.java)を調べましょう。
ここが、問題を実際に作っているクラスであり、肝心な部分です。
プログラムに沿って詳しい説明をする前に、このクラスでは何をしているのかの概要を
説明をします。
最初、指定されたヒント位置の数字を適当に決めます。でも、完全にランダムに決めると、同じ列、同じ行、同じ3×3のマスの中に同じ数字が入ってしまう可能性が非常に高いです。また、解けるかどうか確認する時に、解くことが出来ない矛盾のある問題になっている可能性も高いです。
これを避けるため、適当な全マス数字が詰まっていて、ルールを満たす任意の解を用意します。この任意の解はどんな方法で作っても構いませんが、できるだけランダムになるように作ります。

次に、全部詰まった盤面から与えられた問題パターンで指定されたマスの数字だけ残し、それ以外は全部0にクリアします。すると、問題の形をした問題らしきものができあ
がります。

34

問題らしきものを解いて、ユニーク解であることが分かれば、これで問題作成が完成です。
普通は、空白マスがいくつも残ります。
上の例では、解いても6マスしか決まらず、残りの空白マス数は55になりました。
この、空白マス数をどんどん減らす方法を考えます。
ここでは、ヒントのうちから２箇所（マス）をランダムに選び、その２つのマスの数字を色々入替えた問題をつくり、それを解いて空白マスがどれだけ残るかを調べます。

入れ替える数字によっては、ルール上不可能な場合（最初からルールと矛盾したり、解き進めていくと途中で矛盾する）には、その入替えはマズイということで、無視することにします。
このヒント２箇所の入替えを行って解くと、残り空白マスの数が、入替え前よりも減る
ことがあります。これは、問題がより完成に近づいたと考えられます。それで、次からより残り空白マスの数が少なくなった問題を基準に、同様の変更を繰り返して、残り空白マスがより少ない問題を探していきます。そして、残り空白マスが0になったら、ユ
ニーク解になったので、問題の完成です。

35

２箇所の全入替えを調べても残り空白マス数が少なくならない場合があります。そのときは、問題盤面を入替え前の状態に戻し、異なる2箇所の組み合わせを選択し、同じことを繰り返します。
これを延々と続けても、全然空白マス数が減らないこともあります。このような状態が延々と続いてしまうことがあるので、減らない状態が何回続くか数えて、一定の回数続いたら諦めることにします。
以上は、最初に解サンプルから問題のヒントパターンに従って問題を型抜きした状態から徐々に改良（進化）を繰り返して完成するまでの流れです。
しかし、この方法では、最初の解サンプルによっては上手く行かないこともよくあります。それで、これで一度駄目だったら、再度解サンプルを作り直してから同じことを繰り返すと、できるかもしれません。
解サンプルから作り直すのを何度も何度も繰り返せば、そのう
ち完成するのではないかとの甘い考えで本プログラムは作られています。
実際にどのくらい上手く行くか
は、ご自身で動かして確認して
ください。

36

では、プログラムに沿って説明します。

getHintArray()
ヒントパターンが与えられた時、このパター
ンのXの位置を配列で持っておくと都合がよいです。
そのヒントの位置配列を作って返すのがこのメソッドです。

86

private int[][] getHintArray() {87

int[][] hintpos = new int[hintcount][2];88

int idx = 0;89

for(int r = 0; r < NP.SIZE; r++)90

for(int c = 0; c < NP.SIZE; c++)91if( pattern[r][c] ) {92

hintpos[idx][0] = r;93

hintpos[idx][1] = c;94++idx;

95

}

96
97
98

return hintpos;}

ヒントの9x9のboolean配列であるpatternに既にヒントが入っていると仮定しています。
これから、ヒントの位置配列（2次元配列）に、ヒント位置を記録していきます。
最初にヒントの位置配列hintposを作ります。
次に、pattern配列の全要素を調べ、もしtrueだったらその位置を記録します。全位置を調べる時に、水平方向をr(row)、垂直方向をc(column)という変数をインクリメン
トしながら調べています。

37

上のハートの場合には、次のようにhintposに記録され、これを戻します。
(1,1), (1,2), (1,6), (1,7), (2,0), (2,3), (2,5), (2,8), (3,0),(3,4), (3,8), (4,0), (4,8), (5,1), (5,7), (6,2), (6,6), (7,3),(7,5), (8,4),
では、最初から説明していきます。最初にいくつかの変数が宣言されていますが、これらは利用する都度説明していきます。

generate( boolean[][] pat )引数で与えられたヒントパターンから問題を作るメソッドです。
中央付近の、generateOnce( pat ) が頑張って「一度」だけ、解サンプルから問題を作るメソッドです。一度だけではなかなか成功しないので、問題作成に成功するまで400回まで繰り返し試します。
400回のループの途中で完成すれば成功の表示と再試行回数をプリントし、ループを中断しtrueを返します。
400回ループしても完成しなければ、falseを返し、あきらめたこと(false)を返します。
400は実行してみて、適当に決めた値です。
22

public boolean generate( boolean[][] pat ) {23

for( int i=0; i<400; ++i ) {24

System.err.print("*");25

if( generateOnce( pat ) ) {26

System.err.println( "SUCCESS

27

return true;

28

TRY "+i);

}

29

}

30
31
32

return false;}38これ以外に、1回ループする毎に*をプリントしています。そのため、なかなか完成しな
いと*が多数並びます。

★generateOnce( boolean[][] pat )このメソッドが、１つの解サンプルを出発点にして、延々と最大200回までループを回りながら問題の完成を試みるもので、本プログラムで最も肝心なメソッドです。
ここの200も適当に決めた値です。

34

public boolean generateOnce( boolean[][] pat ) {35

pattern = pat;36

backup = new int[NP.SIZE][NP.SIZE];

37

xcells = new int[XCOUNT][2];38

initialSetting();

39
40
41
42

for( int i=0; i<200; ++i ) {if( blankcount == 0 )// SUCCESS!!

break;

43
44

NP.copyBoard( problem, backup );45
46// select XCOUNT cells and changed them47

selectXCells();

48

clearXCells();49
50// change some cells value on problem

51

int blk = changeXCells();

52
53// if new problem is better, update current
blankcount, and continue

54// else restore problem55

if( blk >= 0 && blk < blankcount ) {56

blankcount = blk;// update blankcount

39

57

i = 0;

58} else {59// restore from backup

NP.copyBoard( backup, problem );

60

}

61

}

62
63
64

return blankcount==0;}

メソッドの最初で、引数で渡されたパターンをGeneratorの変数も指すようにしています。
backupは、問題盤面を元に戻すときのためのバックアップです。
xcellsは、問題の中の数字を変更するセルの位置を記憶するための配列です。XCOUNT
は何箇所変更するかで、現在は2になっています。

次に、initialSetting()を呼んで、必要な初期化を行っています。
initialSetting()は以下のようになっています。
66

private void initialSetting() {67

int[][] solution = Solution.getANewSolution();68
69

problem = makeInitialProblem( pattern, solution );70
71

blankcount = solver.solve(problem);72
73

hintcount = countTrue(pattern);

74

hintarray = getHintArray();

75}

最初にSolution.getANewSolution()で、解サンプルを入手し、solutionに入れます。
次に、solutionと問題パターンから、最初の問題を作るのがmakeInitialProblemメ
ソッドです。makeInitialProblemはGenerator.javaの最後の方にありますが、簡単なので説明は省略します。

40

次に、
空白マス数を数えて、blankcountに入れます。
問題パターンからヒント数を数えて、hintcountに入れます。
ヒント位置の配列を作り、hintarrayに入れます。
ここまでが初期化で、その後forループを200回繰り返します。
ループの最初で、完成したか(残り空白マス数が0)を確認し、0だと問題が完成している
のでループを抜けます。
次に、問題の配列problemをバックアップ配列backupにコピーします。
単なる代入ではだめで、深いコピーを実行します。
selectXCells() で、変更するマス（セル）をランダムに選択します。
clearXCells() で、problemの変更するマスを0クリアします。
changeXCells() で、変更するマスをランダムに適当な値に変更し、残り空きマス数をblk(変更後の空きマス数)に入れます。詳細は後述。
blkが負だと、不可能な問題だったときに、backupからproblemにコピーすることで以前の状態に戻しforループを続けます。
blkが今までの(最小の)空白マス数以上の場合も、空白マス数が減らなかったので進化は無かったとして、同様にbackupからproblemにコピーして元に戻してループを続けます。
blkが今までの(最小の)空白マス数より少ない場合は、進化が進んだということで、変更後のproblemはそのままにし、空白マス数blankcountをblkに更新してからfor
ループを続けます。
forループを抜けてくるのは、問題が完成したとき(blankcount==0)と、200回ループを周り終えたときです。
このメソッドは、問題作成に成功したか否かを戻すので、blankcount==0により、成否を調べて戻すことができます。

41

changeXCells()
121

private int changeXCells() {122

int blk = solver.solve(problem);

123
124

for( int i=0; i<XCOUNT; ++i ) {125

int r = xcells[i][0];126

int c = xcells[i][1];127

int val = solver.getValue(r,c);128

if( val > 0 ) {129

problem[r][c] = val;

130

continue;

131

}

132

boolean[] cans = solver.getCandidate(r,c);133

val = selectCandidate(cans);

134

if( val < 0 )135return136-1;

problem[r][c] = val;

137
138

blk = solver.solve(problem);

139

if( blk < 0 )140

return -1;

141

}

142
143
144

return blk;}

入替える予定のマスに実際に適当に数字を入れて、解いてみて、空白マス数を戻すメ
ソッドです。
まず最初に、今の問題problemを解いて、空白マス数をblkに入れます。
42

解くのは、空白マス数を求めるだけではなく、入替えマスに入れられる数字がどうなるか調べるためでもあります。
次に、入替えマスの個数だけforループを回ります。一回周るごとに、入替えマスの数
字を決めていきます。
forループの最初で、入替えマスの位置(r行c列)を求めます。
入替えマスは空白(0)にしたのですが、問題を解くと勝手に数字が決まるマスかも知れないので、それを調べます。
空白マスのまま解いていますが、それでもその入替えマスの値valが決まっている場合
は、その入替えマスの値をその値にするしかないので、問題problem[r][c]にその値を代入し、次のループに進みます。
入替えマスの数字を決定する前に、入れられる数字の候補をgetCandidate(r,c)で取り出し、cansで参照できるようにします。
problem[r][c]のマスに入れられる値は、selectCandidate()で決められます。
これは、候補の中から可能な数字をランダムに１つ選びます。詳しくは後述。
133

val = selectCandidate(cans);

戻ってきた値が-1だとエラーなので、中断します。
大丈夫だったら、problem[r][c]にその値を代入します。
これで、１つの交換マスに入れる数字が設定されました。
その状態で問題を解いて、空白マス数を求めます。
もし負の値だったらエラーなので中断します。
大丈夫だと、forループの次の周回により、次の交換マスに対して同じ処理を繰り返します。
これを繰り返すことで、forループが終了した時、全ての交換マスについてランダムに値を変更し、解いて空白マス数がカウントされた状態になっています。
最後に、空白マス数を戻り値としてリターンします。

43

selectCandidate( boolean[] cans )changeXCells()の中で呼ばれます。
引数で渡された可能な候補の中から、ランダムに１つの数字を選択し戻します。
146

private int selectCandidate( boolean[] cans ) {147

int r = NP.random.nextInt(NP.SIZE);

148

for( int i=0; i<NP.SIZE; ++i ) {149

int v = (r+i) % NP.SIZE + 1;

150

if( cans[v] )151

return

152

}

153

return

154

v;

-1;

}

まず、rに0〜8までの範囲の乱数を求めます。
このrから初めて、１つずつ増やしながら、引数で渡された候補がtrueになっている候
補数字を調べ、trueだと、その候補数字を返します。
1から9を順に調べるだけだと、もっと簡単なプログラムになりますが、1から順に調べて最初にtrueになっている数字を返すと、小さい数字になる確率が高くなり、問題の数
字が小さい数字になりやすくなります。
ここでは、候補の中のtrueになっている数字から、片寄ること無くランダムに数字を選ぶために、少し工夫をしています。
そのため、最初の乱数ｒから順に増やしていき、数字が一巡したら終わりにしています。
149

int v = (r+i) % NP.SIZE + 1;

この式が少し難しいかもしれません。
最後の＋１は、候補配列のサイズは10で、添字の0は使わず、実際にマスに入れる数字（１〜９）を添字として渡された候補配列を参照(cans[v])することで、まだ候補であるかどうか判断しています。

44

trueだったら候補として可能なので、その値を返します。
そして、このzのループの中で、その数字zが入れられるかをcans[z]で調べています。
可能なら、problem[r][c]に書き込むことで、入替えマスの１つを決めています。決められたら、それ以上調べる必要がないので、ループを抜けます。
forループを終えてしまった場合は、可能な数字は無かったということで、-１を返します。

数字の入替えは、このプログラムではできるだけ単純なアルゴリズムながら、ちゃんとした問題を作れるものを採用しています。
より効率の良い方法とかありますが、それらは皆さんへの課題として残しています。良ければ、改良にチャレンジしてみてください。

次ページの実行例は、ヒント数18個のきれいな配置の場合の自動生成実行例です。
ヒント数が少なくなると、問題作成が可能なパターンでも、なかなか成功しなくて何度も作り直しを繰り返すことが多くなります。また、パターンにより、作りやすいパター
ンや作りにくい（成功しにくい）パターンがあります。

45

46

第３部 発展課題編

ナンプレの問題を自動生成する簡単だけれど強力な方法を説明しました。
ヒント数が少なくなるに従って問題は作りにくくなります。ナンプレの問題は人が作ることもできますが、ヒントの少ない問題は手作業だけでは非常に困難になりますが、人工知能を使うことで、ヒント数の少ないスッキリした問題を作ることができることがおわかりいただけたでしょか。
ここでは、紹介したプログラムの抱えている問題点や改良点を紹介しますので、ぜひチャレンジしてみてください。
内容的には、プログラミングに関する事柄、パズルに関する事柄、人工知能の進化計算に関する事柄などがあります。

47

入力ファイル
現在は問題やパターンの前に1行のヘッダー行が入っていますが、途中に空白行をいれてより見やすくしたファイルが使えません。
空白行を無視するように変更してみましょう。
入力ファイルを読み込む部分を try-catch で括っていますが、これはファイルの最後に改行が入っていると、次の問題も存在すると思って読みに行き、エラーが発生するのを補足するためにとりあえずの乱暴な措置です。
入力ファイルの形式がもっと自由になるように、改善してみてください。

GUI
現在のプログラムは、CUIといって文字によるユーザインターフェイスになっています。
マウスなどを使ってグラフィカルな画面で操作できるようにGUIになると便利でしょう。
1. 問題パターンを画面で入力できる
2. 出来た問題を解いて遊べる
3. ルール違反の部分のマスを明示して警告する
4. 解く時に各マスに候補を表示できるようにする
他にも色々考えられるでしょう。
GUIになると、急に実用的になったと感じることでしょう。

作成中の問題の数字の入れ替え個数
作成中の問題の数字のうち、2マスを選んで別の数字に入れ替えることを繰り返すことで徐々にユニーク解に近づけています。
入替え個数の指定は、Generator.javaの最初の以下で指定されています。
11

staticint XCOUNT = 2;48

この値を、1にした場合、3にした場合、性能はどのように変化するでしょうか。
ぜひ試してください。

山登り法の改良
今の自動生成は、調整中の問題の2マスを選んで数字を適当に入れ替えて、もし残りの空白マス数が減ったら、入れ替え後の問題を調整中の問題するようになっています。
これでは、せっかく選んだ2マスの入れ替えですが、たった１種類の入れ替えを行っただ
けで、また別の２マスを選ぶということをしています。
選んだ２マスに入れられる数字の組み合わせは複数あります。それらの全組み合わせの中で最も残り空白マス数が少なくなったのを次の調整中の問題とすれば、もっと効率よく進化が進むかも知れません。
ぜひプログラムを変更して、調べてみましょう。

問題の難易度
本自動作成プログラムでは、問題の難易度の計算は省略しています。
問題を作れても、生成された問題がどのくらい難しいか易しいか、どのくらいの時間がかかりそうかが分からないと、人が解いて確認することになり、とても面倒です。問題を多数提供しようとすると、難易度の自動判定が必要になります。
難易度はどうすれば判定できるか、チャレンジしてみてください。

再帰で解いてはいけない理由
ナンプレの問題を解くだけでしたら、再帰(リカーシブコール)プログラムにより、簡単にソルバーを作れます。再帰回数は数万回程度ですので、今のコンピュータなら瞬時で終わります。
しかし、再帰を使った場合には、色々困ったことになります。
まず、複数解がある問題を普通は判定できません。自動生成に対応するためには、論理的に決まらない部分は残したまま残さなければいけません。

49

ナンプレの問題を人が解いて説明する時、再帰で解けましたではパズルとして成立しま
せん。ちゃんと論理的に解ける、きちんとした理由でマスを埋めることができることが重要です。理由自体はとても難しくても構いません。そのときには、とても上級の理由（手筋）で決まるということで、上級の問題ということになります。

ナンプレの上級手筋への対応
本プログラムは、基本手筋と言われる、①タテ列、ヨコ列、3x3ブロックという9マスの集合の中である数字の候補が１つのマスだけになった場合は、そのマスはその数字に決まる②1つのマスの中に入れられる候補が１つになったら、そのマスはその数字がに決まるだけを利用しています。Solver.javaのcheckLoop()以下のメソッドで、これらの基本手筋に従って調べています。
ナンプレを解くための解法テクニック、解き方、定石、などがネット上に多数公開されています。checkLoop()に他の上級テクニックを入れると、入れた上級テクニックも使って数字を決めていくので、より難度の高い問題が作れるようになります。
知っているより高度なテクニック、あるいはネット上などで調べてより高度なテクニッ
クを加えてみましょう。

調整中の問題の数を複数個にこのプログラムでは、１つの調整中の問題を、延々と変更してユニーク解に近づけよう
としています。しかし、これではいつまでたってもユニーク解にたどり着けないことが多いので、適当な回数（現在は200回）試みて駄目だったら、最初からやり直しという方法になっています。
ちゃんとした問題を生成できるパターン配置でも、最初の解サンプルや変更する2マスの場所により、残り空白マスがゼロに達しないことがあります。このようになってしまった調整中の問題を局所最適解といいます。もうどんな2マスを入替えても、これ以上よくならない状況に陥ってしまったわけです。

50

これを避ける方法がいろいろ考えられるでしょう。
上手く行かなくなったら、一度に2マスではなく3マス変更してみるのはどうでしょうか。
今のプログラムは、調整中の問題はただ１つでした。調整中の問題を多数にするとどうなるでしょうか。
調整中の問題を多数用意します。ここで、進化計算の用語にしたがって、２つ用語を定義しておきます。
個体：調整中の問題のこと
プール：多数の個体（調整中の問題）を入れておく容器
多数の個体を同時に進化させたいのですが、どうすれば可能でしょうか。
新しいプールを用意しておき、プールから個体を取り出し、変更しては新しいプールに変更後の個体を入れます。
そして、元のプールに入っていた良い個体(空白マス数の少ない個体)も全部新しい個体に移してしまいましょう。すると、新しいプールの個体数は増えてしまいます。個体を残り空白マス数でソートして、空白マス数が少ない個体から順に、前のプールと同じ個数だけ残して、あとの個体は捨てましょう。
すると、プール内の残り空白マス数の平均値は徐々に少なくなるでしょう。
この手順を延々と繰り返すと、残り空白マス数はどんどん減っていき、残り空白マス数が0の個体ができないでしょうか。
このやり方、ちょっと生物の進化に似ていると思いませんか。
こんな方法を試してみましょう。

51

バラエティーナンプレ
ナンプレも9x9の標準的な問題だけではなく、対角線上のマスにも１から９の数字を１つずつ入れる「対角線ナンプレ」という亜種があります。
対角線ナンプレに対応したSolverとGeneratorはどうすればできるでしょうか。
２つの対角線上に対する制約条件だけが追加されているので、その部分だけプログラムを追加すれば解くのも作るのもできるようになるでしょう。
対角線ナンプレ以外にも様々なバラエティーナンプレがあります。また、通常のナンプレが重なり合った合体ナンプレといのもあります。
いずれも基本は同じです。興味があれば、プログラムを拡張してみましょう。

9x9の標準的なナンプレの問題が重なった「合体ナンプレ(GATTAI)」というのもあります。
重なっている部分には、同じ数字がはいります。
これも基本的には同じ考え方で解ける
し、作ることもできます。

52

2018年10月には、MATH POWERという数学の祭典が、六本木のドワンゴのニコファーレというイベント会場で開催され、280合体の問題を提供しました。本イベントは2日間に渡る31時間連続イベントで、多数の来場者により解かれました。
本問題は、合体ナンプレとして世界最大であるとギネスワールドレコード(TM)に認定さ
れました。

53

他のパズルナンプレ以外にも、多数の論理的に解くパズルが存在します。書店でパズル雑誌を見るとか、ネット検索すると簡単に確認できます。
どのパズルもルールがあり、ルールに従って解き進めます。
これらのパズルの多くも、コンピュータで解くことができます。
さらに、ナンプレの問題自動生成と同様に、問題を自動生成できるパズルも多数存在します。
パズルの解き方は、パズルのルールに沿ったプログラムを書くことで解くことができます。つまり、ソルバーの作成は、個々のパズルに依存します。
しかし、自動生成に関しては、ナンプレと同様の方法で、あるいはほぼそのままナンプレの自動生成を流用することができます。
興味のあるパズルがあれば、ぜひチャレンジしてみましょう。
アルファ碁がプロ棋士よりも強くなって、人工知能が急に脚光を浴びました。人間が行うもっとも高度な知的ゲームである囲碁は当分人工知能が人間に追いつけないだろうと言われていましたが、今では囲碁も将棋も、プロ棋士が人工知能を利用して腕を磨くのが一般的になりました。
そして、これをきっかけに、一気に様々な分野への応用が急激に進みました。
ゲームあるいはパズルは、昔から人工知能あるいはアルゴリズムの研究に非常によく利用されました。また、社会のさまざまな活動は、ゲーム（経済ゲーム）やパズルとして捉えることができると言われています。したがって、ゲームやパズルに強い人工知能が生まれたら、当然社会の課題の解決にも役立つだろうことは予想でき、実際コンピュータの歴史を見ても、ゲームやパズルで生まれた技術が応用されることは少なくありません。

54

さまざまな社会課題への応用問題（データ）を多数用意し、その問題を元に色々な方法で新しい問題を作り、良い問
題だけを残しては同じ方法を繰り返すのは、生物の進化と同じですので、進化計算といいます。
とくに、遺伝の仕組みを模倣し、DNAの交叉と突然変異と同様にデータを変更し、良いものを残していくことを続けるのが遺伝的アルゴリズムです。
詳しい説明はしませんが、とても強力なアルゴリズムで、人工知能における重要なアルゴリズムの１つになっています。単独で利用することもあるし、他の人工知能手法と組み合わせて利用することもあります。
進化計算、あるいは遺伝的アルゴリズムをキーワードしてネット検索してみてください。いろいろな解説があります。また、書籍も出ているので、参考にしてください。
進化計算・遺伝的アルゴリズムは、さまざまな社会の課題を解決するために使われています。面倒な組み合わせを最適化しないといけない場合はよくあります。多数のパラメータを同時に変更することは人間には大変面倒な、あるいは不可能なことですが、進化計算により実現することができます。
有名な応用例の１つが新幹線のN700系の先頭車両のフロントノーズの形状です。この形
状は人が設計したのではなく、さまざまな条件下での最適化を遺伝的アルゴリズムで行って得られたもので、とてもエコでありながらスピードも出せるようになりました。
様々な機器の自動運転、配置や分割の最適化、人員調整など多方面で利用されている技術です。
ぜひ人工知能の重要な分野の１つである進化計算/遺伝的アルゴリズムをマスターして、様々な社会課題の解決に取り組んでみましょう。

55

進化計算 天啓｜TENKEI
株式会社タイムインターメディア
知識工学センター
東京都調布市小島町1-1-1
電気通信大学 UECアライアンスセンター217
puzzle@timedia.co.jp
藤原博文
2021年3月22日

56