(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 に問題毎に問題と解答それに解き順をアウトプットできるようにした。