(24) 補足 search_table

これは（２３）search_table マクロの補足である。いま、Sheet1 の（７，２）から（１５，１０）のRange の81個のセルに数独の問題が書かれている。その中の空白セルのすべて　(empty_cell 個) に対してそのセルに入る可能性のある数字の候補を　11列目から (10+empty_cell) 列にわたって選び出す。その空白セルの順番が numj である。10+numj 列の行には、次の情報が入る。
　　4行目　セルの行　(iii）
　　５行目　セルの列　（ｊｊｊ）
　　6行目　セルの番地　( iii, jjj )
　　7行目から15行目までは候補の数字
　　16行目　候補の数
　　17行目　Block　の番号

候補の数字の選出は、まずBlockごとに、数字1から9までが候補になりえるかを　check する。行と列に対しては、check　の中で Block に対しては checkmate で行う。表出数（givens） でない候補は　sheet1 の search table にかきこまれる。

table を作る方法はいろいろあると思われるが、このアルゴリズムでの長所は、7行目から書き込まれる候補の数字は小さい数字の順番であることである。このことは後々探索法のアルゴリズムを簡単にしている。

(23) 演習：候補の一覧表を作るマクロ

SUDOKU_Ver９　までで一応、力づくで解を得ることができるようになった。しかし使っている探索法はたった３つに過ぎない。数独を人間が解くのに用いる方法で人間の思考過程をシミュレートするようなソフトを作るためには、用いる探索法を網羅し、解く過程のヒントが得られるようなそれぞれのフェーズに適したソフトにしなければならない。

SUDOKU_Ver10 から数独のソフトを作る基本的なマクロの例をいくつか書き留めておきたい。そうすれば自ずからそのアルゴリズムも理解しやすくなるであろう。まづは、空白セルにはいる候補の一覧表を作るマクロ search_table (これまでは mixy とか mixy_part と呼んでいた。また最終的には candy_table と呼ぶ）マクロである。

Sub search_table()
clear_answer　　　　　
numj = 0
For ii = 1 To 9
For jj = 1 To 9 　
If Cells(6 + ii, 1 + jj) = "" Then
iii = ii jjj = jj 　
group_search
check
Cells(6, 11 + numj) = "(" & iii & "," & jjj & ")"
Cells(4, 11 + numj) = iii
Cells(5, 11 + numj) = jjj
Cells(17, 11 + numj) = grp
numj = numj + 1
End If
Next jj
Next ii
count_kosuu
End Sub

Sub check()
num = 0
For aaa = 1 To 9
For i = 1 To 9
ccc = Cells(6 + i, 1 + jjj)
If aaa = ccc Then GoTo contaaa
Next i
For j = 1 To 9
bbb = Cells(6 + iii, 1 + j)
If aaa = bbb Then GoTo contaaa
Next j
checkmate
If flag = 1 Then GoTo contaaa
num = num + 1
Cells(6 + num, 11 + numj) = aaa
contaaa:
flag = 0
Next aaa
End Sub

Sub checkmate()
group_search
For ci = igs To ige
For cj = jgs To jge
If Cells(6 + ci, 1 + cj) = aaa Then
flag = 1: Exit Sub
End If
Next cj
Next ci
End Sub

(22) マクロはオブジェクト指向プログラムに最適。

Excel VBA のマクロは数独ソフトのプログラミングに最適のものである。いろいろと不勉強で十分に使いこなしていないところはあるが、文法やデバッグでは、格段と使いやすい。

オブジェクト指向プログラムは文字とおり、オブジェクト(目的対象物)によってプログラムを組み立てて使う。ある仕事をするのに必要な人材（マクロ）をかき集めて行うプロジェクト（ソフト）に似ている。効率よく目的を達成するために、有能なマクロをもっていることがソフト価値をきめる条件になる。

人材（マクロ）はいつ何時に呼び出されてもすぐに仕事ができるように生きた状態で存在しなければならない。そこがサブルーチンとマクロの違いである。プログラムで END というコマンドを入れると死んだ状態になる。マクロで注意しなければならないのは、ENDはすべてご破算になるので注意を要する。

マクロでは他のマクロがどうなっているのかに関係なく仕事が出来るようにしておくべきなので、連絡手段・方法は非常に大切である。マクロの中では必要な情報はすべて内臓するか、参照できる状態にしておかねばならず、PUBLIC　ステートメントや文字の選択には細心の注意が必要である。

(21) Excel VBA に潜む怪

プログラミングに長く慣れ親しんできた人は、人間は過ちを犯すもので、コンピューターの馬鹿正直なおろかさをいやと言うほど知っている。すらすらと通ったプログラムも思わぬところでバグがでることがある。ちょっとしたことで確認を怠ったためにその原因を突き止めるのに、一週間も無駄にすることもある。ケアレスミスでデータをなくしてしますこともある。コピーをこまめに取らなかったために、古いファイルを数日掛かった新しいファイルに逆に上書きして、唖然とする経験はだれにでもある。大抵の場合、コンピューターは正しく、プログラマーの無知や正確に起因するトラブルである。

Excel でも、数独開発において、VBA特有のトラブルに何度か遭遇した。それは決定版数独の第５４問でおこった。当時のメモから抜粋すると、「５４番が最終状態まで到達しないので調べてみた。随分とかかった。まず、全部のケースでblindになること。正解と比較してみると、（７，２）のセルには８がはいらなければならないのに、６が入っていたためだった。これは（７，３）が実際には空白セルであるにもかかわらず、””ではカウントしているためであった。つまり（７，３）の候補が６とその他であるにもかかわらず、一覧表から漏れたため、６がそのグループの唯一の候補であると認識したためであった。何故空白セルであるにもかかわらず、値がはいっているものと認識するのか？　Number_of_cell というマクロで調べてみると、確かに　””　空白セルを（７，３）はカウントしていなかった。原因はわかったが対策は分からない」

おそらく私のVBAを良く知らない我流のプログラミングによるためであろう。この問題は一度マトリックスに問題を読み直すことでより、エラーを見出せるようになった。プログラミングは頭のさえている時に、はやる気持ちをぐっとこらえて、一歩一歩進めなければならない。と同時に、何かおかしいなと感じる感性を培うことが肝要である。

(20) L サーチに遭遇する。

基本サーチは4種類で、B,L,C,M サーチであることはすでに書いた。SUDOKU_Ver10,Ver11 の段階ではまだこのいとも簡単な解法の中で、BサーチとMサーチしか使っていない。それと強力な A サーチだけで「ニコリ数独名品100選」は3題を除いて全部とくことができた。Ver10では、42分32秒であったが、Ver11ではアルゴリズムを少し改良した結果25分25秒に短縮された。

解けなかった3題は45番、67番、75番で、最初　Lサーチを使うと簡単に解けるのである。それを教えてくれたのは、他でもないN君であった。彼は数独の解き手としてかなりの上達を見せており、解法もいくつか心得ているようだった。

この頃から、ただ力づくで解くのではなく、人間の脳で考える、そして見つける方法をシミュレーションするアルゴリズムを見つけようとおもいだした。つまり人間の考えられる範囲の解法を順番に引き出すことが出来ないかと思ったのである。

(19) 「ニコリ数独名品100選」を買う。

先の文芸春秋6月号の鍛冶真起氏の記事に予告があった数独本「ニコリ数独名品100選」を本屋で見つけて買った。私の習慣で買った本の後ろの見開きには必ず購入した日を記入しておくのだが、それによると2006年6月5日とある。

丁度 A サーチが完成しかかっていたころなので、100選のうちどの程度の問題が解けるのか大変興味があった。100題をインプットするのに3日ほど掛かった。大体10題くらいインプットするといやになる。それも仕事の合間にするのでなかなか時間が取れない。またインプットの方法にも、いくつかのノウハウがあることがわかった。

インプットのミスで多いのは数字の入れ忘れである。入れ忘れでも解ける問題ではミスに気がつかない。名品100選の6番の問題で右下（９，１）のセルの８を空白セルとして解いていたことがある。100選のこだわりは「対称性」であるらしい。しかし難問になると非対称のほうが多い。

SUDOKU_Ver10 になると、A サーチは62ルートをカバーできるようになった。さらに、number_tree　というマクロをつくりその樹木図をSheet1にかけるようにした。これにより、解がどのような経路をたどり Final answer にたどり着いたかが検討できる。Ver9 の 30ルートは 30=2+4+8+16 で　4階層に相当する。 Ver10 では　62=2+4+8+16+32 で 5階層をカバーすることになる。

このAサーチは現在のものと同じであり、これ以上のものは必要がない、というより　このAサーチそのものが蛇道ではないかと気がついたからである。それもこの「ニコリ名品100選」の最初についている「数独解法の手引き」が参考になった。およそ理論から離れた実務的な考え方が。

(18) Back_to_win との決別 （A サーチ新展開）

西山豊著｢数学を楽しむ」の第27話に「Sudokuがイギリスで大ブレイク」がある。この中で「Sudokuはたしかに達成感の味わえるパズルである。クロスワードパズルのように鉛筆と消しゴムというスタイルには向かないような気がする。それは、難しい問題になると数字の配置を仮定することが多く、行き詰った場合どこまで戻ればよいのかわからなくなるからだ。これはやはりパソコン向きのパズルではないのだろうか。」

実際にはそうでなく、数字の見つけ方がいくつもあり、そこに数独の醍醐味があるのだが、その頃にはまずこの仮定法とか山登り法とかいう探索法を何とかしたいという思いでいっぱいであった。

数独の解く過程を山登りに例えると、EasyやMedium　の問題では、山頂(Final answer)にたどり着くルートはいくつものあり、緩やかなルートもあり、険しいルートもあるが、どの道を通っても山頂にたどり着ける。ところが、Hardな問題では、途中に山小屋にたどり着いてもその先、道は二つに分かれていてどちらか一つだけが正しい道なのだ。誤った道を選んでもまた山小屋があり、また道をえらぶ。また山小屋という風なことが数回繰り返し挙句の果てに行き詰まりでもとに戻るということになる。何回も山小屋を通過しているので「どこまで戻ってよいのかわからない」のだ。

back_to_win というのは、いうなれば山小屋が二つ、つまりルートは四つに対応している。だからHard な問題では解けないことになる。ごく初歩のAサーチであった。

Sudoku_Ver9 では　back_to_win マクロと決別し、新たなアルゴリズムの new_class_search というのに変更した。Ver9　では３０ルートまでたどることができるし、何よりその山のぼりの方法に工夫を凝らしたのである。