(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　では３０ルートまでたどることができるし、何よりその山のぼりの方法に工夫を凝らしたのである。

(17) 連続計算マクロ

SUDOKU_Ver7 　では新たに難易度の表示、決定セルの数値と解法、経過時間などを順次書き込むようにした。また、解けない問題は同じことを数回繰り返した場合に「 Not Conquer 」と表示することにした。

操作は3つのコマンドボタンで行う。①　start ボタンは ippatsu により、レベル1の段階だけ行う。　②は一つの問題だけに対応している。　complete ボタンにより、Only_one_problem マクロを稼動する。③は、continous calculation ボタンにより、連続して問題を解く。Sheet 2 に予め問題を入力しておき、連続計算を行なうと、Shee4 に問題別の Final Answer と　Sheet 5に問題別の時間やレベルなどの要目の一覧表を作成する。

SUDOKU_Ver8(数独ニコリ決定版)では、120問の連続計算が始めて可能になったが、まだ解けない Hard な問題がいくつかあった。計算時間はSheet 1　のA 面に途中経過を表示すると、いちじるしく時間が掛かることがわかった。ソフコン応募資料によると、最終的には「ニコリ数独名品100選」を2分34秒で解けるをかいてある。

(16) わかやまソフトウエアコンテスト’06

丁度その頃(2006年5月22日）和歌山情報サービス産業協会というところが、毎年ソフトウエアコンテストを開催していて、作品募集のパンフレットが事務室にあるのを見つけた。今年で15回になるというから相当古いコンテストである。

その日のゼミでN君（第13回）にこれに応募してみることを提案した。数独の解析ソフトはまだ目途は立っていなかったが、ここ5年間で開発を進めてきた研究テーマの「乗り物酔い」のソフトがいくつかあった。そのどれかを応募してはどうかということだ。応募の受付は9月1日からで、11月23日に入賞者によるプレゼンと表彰式がある。

時間的にはまだまだ準備期間があるし、何か目標があるほうがモチベーションがあがるというものだ。これはN君だけでなく、私のモチベーションでもあった。その結果最終的には、2編応募することになり
N君は「乗り物酔いの解析ソフト」を担当、数独ソフトはI君にやってもらうことが叶わず、私自身がプレゼンをすることになった。

(15) 初めての数独本「決定版数独」

SUDOKU_Ver6 では、大容量の問題入力が可能になった。数独問題は Sheet2 に専用シートをもうけ、cell_location というマクロで規則的に表の位置を指定した。これにより、200題以上の問題が収納できたが、問題のインプットがまた大変時間のかかる作業でミスも多くでた。

2006年5月27日に初めて数独の問題集をかった。パズル通信ニコリ別冊「決定版数独」（945円）でこれにはレベルが、Ｅａｓｙ，Ｍｅｄｉｕｍ，Ｈａｒｄ　の9×9の数独問題が120題、16×16の数独が6題載っていた。SUDOKU_Ver8 はこれらの問題専用のバージョンとして、新しく連続計算用のマクロ Evaluation_of_SUDOKU というマクロを作成した。ただし120題のインプットには数日を要した。

(14) 自動化マクロの進展

すべての数独を一回のコマンドのクリックで自動的に解くというのが当初の目標であった。まづ Ver.1 の ippatsu というマクロで　やさしい問題はこれを達成した。空白セルの候補の一覧表をつくり、ひとつしかない数字、または候補がひとつしかないセルを探すということを繰り返す。 ippatsuの中の search_single というマクロでそれを達成したのだが、このマクロにはブロックにひとつしかない数字を探す Bサーチしかなかったことは先に書いた。

行にひとつしかない数字を探す L サーチや列にひとつしかない C サーチについては後にN君より指摘されその存在に気がつく。現在数多ある数独の解き方の解説でもこれらの探索法を明確に区別しているものはないようだ。ニコリ社の「ニコリ数独名品100選」の最初にある「数独解法の手引き」でも中級、上級パターンのほとんどが L サーチで解ける。これについては後ほど詳説しよう。

自動化の第二段階は Ver.4 に現れる auto_search というものだが、これは ippatsu を内蔵し、Ａサーチの初期のものであるが開発期のものでその名は現存しない。

Ver.5 になって初めて complete というマクロが現れる。ippatsu および back_to_win2 マクロを内臓しこれを繰り返す。Ver.5 には、ippatsu の中に transfer_result マクロを作成して 新設した Sheet3 に問題毎に問題と解答それに解き順をアウトプットできるようにした。