(31) 公開されているナンプレの解法

2006年7月11日　インターネットでナンプレ(数独）の解法なるものを検索した。これまで数独単行本の最初にのっている「解き方のガイド」なるものを参考にしてきたが、できるだけ自力で解法を見つけようとする方針というか性格であるので意識して独創的な解法をめざしてきたのだ。しかし、その解法は見つからないままAサーチに頼るという道を歩み始めた。真似はしなくとも独創性は発揮できることに気づいて、解法を体系的に論じたものがないかと思った。結果はなかった。というか見つからなかった。解法のいろいろな技術的方法は少し形は違うがにたようなものはたくさんあるが、理論的分類のようなのもはみつからなかった。

「ナンバープレース解法教室」（藤原）には一番分かりやすく、解法の種類も豊富である。「平行線の常識」とか解法のネーミングもユニークである。少なくともこれらの解法はマクロに加えるべきであろうと思った。ただし、どれが重要なものか、頻度が高いのかなどは、数独を実際に解いたことのないものにはわからなかった。わたしはいまでも、ほんのビギナーの問題しかとくことが出来ないのである。その理由は自分が一番よく知っている。恐ろしくせっかちで、数独を解く根気にかけているのである。

インターネットでさらに調べると、すでに数独ソルバーなるものはいくつもあるらしい。どんなものか分からないが、連続で全自動というのはないだろうとおもった。現在、開発中のものには、解法とレベルをうまく組合すと、これまでにないユニークな数独ソフトができあがるだろうと楽観した。

和歌山ソフトウエアーコンテストの締め切りまで、あと二ヶ月もあるので、新しい手筋を3つばかりは付け加えるようにしようと決心した。

(30) Aサーチ(仮定法）の候補の選択方法

　Sudoku_Ver.14　において、新しく購入した「激辛１」の衝撃の105問を、Sheet12のインプット・シートとして使う。（isheet） Sheet13 は dsheet （解答シート）とする。

　A サーチは二つの候補を持つセルを選び、そのうちの一つを仮定して先の計算を進める。どちらかが正解なのだが、選びようによっては、また仮定する必要がでてくる。プログラムでは、5階層まで扱えるようにはなっているが、計算時間が掛かったり、答えに至らない場合がある。

そこで、二つの候補をもつセルの選び方を変えてその状況を調べてみた。正回転はBlock 1 から最初に出てきたセルを選択、逆回転とは、Block 9 から逆に探し出したセルから取り出す。中央回転とは、empty_cell の真ん中から最初のものをとる場合である。

　「激辛　Vol.3」の問題を例にとり、試してみた結果は次の通りである。
　　　　　　　　　　　　正回転　　　　　逆回転　　　中央回転
　問題　32番　　　　47　　　　　　　　　19　　　　　　７　
　問題　35番　　　　9　　　　　　　　　　57　　　　　　52
　問題　44番　　　　27　　　　　　　　　－　　　　　　61
　問題　68番　　　　28　　　　　　　　　－　　　　　　24
　問題　70番　　　　58　　　　　　　　　22　　　　　　29
　問題　80番　　　　31　　　　　　　　　68　　　　　　19
　問題　90番　　　　15　　　　　　　　　80　　　　　　12
　問題　99番　　　　65　　　　　　　　　－　　　　　　60
　問題　100番　　　－　　　　　　　　　18　　　　　　10
　問題　104番　　　61　　　　　　　　　25　　　　　　48
　ここに、「－」は解が得られなかったもの（5階層以上）である。

仮定法において、どのセルの候補を選ぶと効率よく解がえられるかはまだ理論はない。

(29) Ver.13 で全「激辛」を一応征服した。

SUDOKU　Ver.13　は2006年6月27日に着手、 refine_search_table を使用して　search_table の候補の中から、
①　二つのセルで二つの候補が同じため、同blockのたのセルでは使えない数字や
②　他のblockの同行、同列に、二つのセルのみ candidate を二つ持つセルがあるのでこれは使われないとき、
これらの候補を消去して、候補数を絞った新しい表を作成する。

また、どの検索が有効であるかを見るための ON OFF 機能を追加する。

また、refine_M_search を新設、候補が一つしかないセルを満たす「MR」として区別した。

これらの改良により、激辛　Vol.1～Vol.3　をすべてクリアした。

（２８） refine_search_table を作成する。

2006年6月25日　数独の新手筋を考える。手筋としては簡単だが、分かりやすい簡潔なアルゴリズムをどうするかが問題である。いろいろ考えていると時間が直ぐすぎた。
2006年6月27日新手筋完成。refine_search_table を作成、kosuu　が一つであるセルに直接その時点で値を代入する方法を採用するとすごく効率があがった。激辛Vol.2、Vol.3　を完全にクリアした。　part_search_second をやめにして、すぐに refine をかけた方がよいのではないかと気付く。

2006年7月1日（土）に天久堂にて｢激辛vol.1｣を購入。本体700円。7月2日にそのインプットを一日でおえる。102番が通らない。

二つの候補を選ぶのを以前逆まわりで解決したが、二つの数の候補でやって見る方法を思いつく。それも、二つのセルに二つしか入る候補がない数字が同じblockにいくつあるか、一つのセルにダブっているセルからやるといいということを思いついた。

(27) V サーチを追加

Ver12　の激辛２　では　100題中　15題が　Not Conquer となった。これは、まだまだ探索法が少なく、A サーチにのみ頼っているためで、人間の思考にははるかに及ばないことの証拠であろう。これからは、人間の思考に近い探索法をマクロにすることに心がけよう。その手始めに、新しい探索法である gloval_victory_search マクロを作成した。現在の V_search に相当し、「VL」と「VC」からなる。

V_search の探索法
①　igrp　でブロック順に空白セルにいる候補を調べる。
②　数字を numb=1 から 9 まで順番に調べる。ここに、numb　はセルに候補として入る数字をあらわす。
③　igrp　の中で、numbの候補の数を調べる。もしこれが　一つしかなかったら、Pサーチで求まる決定値に相当する。各ブロックで　numbの数を数えて　num　とする。　num=2　であれば、( i1 , i2 )=a1 , ( j1 ,j2 ) =b1=numb として二つだけの候補が求まる。
④　igrp　の同行　i1=j1　または　同列　i2=j2　の他のセルには数字　numb　ははいりえないので、もし他のblock　の同行、同列に　numbがあれば、それを除外する。結果として、除外したセルの属する　block　で、numb　の入るセルが一つあれば、そのセルはnumbとなり、数字が確定する。

　

2006年６月２７日にこのマクロが完成し、激辛２の15題あった　Not　Conquer　は９６，９７，９９，１０３の四つになった。計算時間も　8.7分に短縮された。　

(26) 激辛数独2を購入

SUDOKU_Ver12 のSheet 8 およびSheet9に、2006年6月17日に購入した「激辛数独２」の入力を開始、6月２０日までかかった。解けない問題が多々あり、問題を今一度見直して見るとインプットミスが多い。数字は一行ずれていたり、一番多いのは、数字の入れ忘れである。その他 Excel VBA に関していくつかの奇妙な現象に遭遇した。まだまだ未熟な点が多いなあ。

SUDOKU_Ver12 ではいくつかの改良を行った。これまで空白セル毎に i=1 to 9 , j=1 to 9 で回していたのだが、 igrp （ブロック番号）で回すように、block_search を新しく採用した。

Ver12 で決定版数独は、６４、７０、８０、１１３、１１６、１１８　の六つの Not Conquer があり、時間は　８．９５分を記録した。また名品１００選では、４５、５４、７５、９１　の五つの Not Conquer があり、時間は　9.33分に短縮された。
　

(25) P, M サーチに G サーチを追加 （Ver.11)

　2006年6月14日、SUDOKU_Ver11を立ち上げた。このVersionより新しい探索法を取り入れることとし、同時に探索法に名前をつけて、問題をとく次の手順を示すこととした。

（１）　Primary と Medium に分けて、一覧表の候補から、その数字が一つしかないのを探索するのが M search,　コンピュウターでは、一番分かりやすい解法（とにかくセルに候補が一つしかないのですぐにわかる）であるのに、人間には見つけにくいらしく、名品100選では、上級パターンその②にランクされている。

（２）各Blockにおいて数字を１から９まで当てはめて、該当数字を洗い出す。該当数字が一つしかないもの（つまり candidate が一つのもの）を P search と名付けた。（現在の B search に相当する）

（３）Block 内で同じ二つの候補を持つセルを見つけ出す。どちらかにその候補がはいるので、そのセルの他の候補を消去する。結果として、消去した数字が他のセルでsingle candidate になる。これが G search である。

2006年6月18日、このマクロを備えたVer11において、名品100選のなかで、45、67、75　の三つが Not Conquer であった。消費時間は25.25分を要した。