(34) 基本系 Sサーチの発見

2006年7月21日(金）　イオン旭屋書店にて、「ナンバープレース40号記念号」という数独の雑誌を買った。これを見ていると突然　Sサーチというのを思いついた。これまで漠然と数字を決定するのはPサーチとMサーチの二つの基本系ばかりに目を奪われていたのだが、Block と同様にColumn（列） と Row（行）も同様の役割を果たすのだ。つまりBlock, Column, Row は対等でBlock　で考ええる手法はColumn や　Row でも同等に成立するし、一つのセルはどのセルも、そしてすべてのセルが、ひとつのBlock , 一つのColumn そしてひとつのRow　に属するということである。

目からうろことはこの事か。乙女の姿がよく見るとおばあさんの顔にも見えるという「隠し絵」のように、Pサーチとおもっていたのが、実はSサーチでも解けるということがわかった。（ニコリ数独名品100選
の初級パターン①から⑤は、すべてPサーチであると同時にSサーチでもあるのだ。純粋にPサーチであるのは初級パターン④だけである。）

この発見により、数独の基本手順は4通りに分類できることがわかった。基本系とはその手順だけで、数字が決定する手順のことである。そこで、プログラムの書き換えを行い、かつ探索法の名前の変更をおこなった。
　
　Bサーチ（Pサーチ）　あるBlock　の中で入るセルが一つしかない数字を探す。
　Lサーチ（Sサーチ）　ある 行　の中で入るセルが一つしかない数字を探す。
　Cサーチ（Sサーチ）　ある 列　の中で入るセルが一つしかない数字を探す。
　Mサーチ（Mサーチ）　ひとつの候補しか持たないセルを探す。

　

(33) Ver.16（ポケット数独）の開発

2006年7月17日(月）　和歌山近鉄百貨店のとなりの本屋で、ニコリ社から最近発売された「ポケット数独」の初級版と中級版を購入、SUDOKU＿Ver.16 の新しいシートに入力した。新しい解法として、refine_special_search_table を作成した。数独の解法において著しい進歩があった。

　実際に人間が数独を解く場合どのような順序で探して、考えるのだろうかと思いをめぐらした。初級の問題では、表出数（givens）の多い数字から「平行線の常識」（つまりPサーチ）で single candidate のセルを見つけ、同じ数字をしつこく追いかける。これで初級問題は大体とける。パソコンでは、candy table を作るから、「残り物の常識」（Mサーチ）が一番さきに分かりやすい。これが将来 ｇ_matrix となる。

(32) ナンプレの雑誌・本を買う。

2006年7月15日（土）　本屋に行ったら、ナンプレの雑誌がたくさん並んでいた。そこで「ナンプレ・ファン」という雑誌を買った。通常のナンプレのほかに対角線ナンプレとか幾何学ナンプレとかいう種類のナンプレがあり、どういう風にマクロを変更すればこれらのナンプレに対応できるのかを考えた。

通常のナンプレもファーストステージからサードステージまで、レベルごとのたくさんのナンプレがのっていた。順番に解いてみたが、最初の方は簡単すぎて面白くなかった。

2006年7月16日（日）　本屋さんでまた400円の雑誌をかった。これも簡単すぎて手ごたえがなかった。「MR」と同じような手筋で「PR」というマクロをつくった。これは、refine_search_table の中の single value を抽出するものである。single candidate を抽出する「MR」と対をなすものだと思うが、V,　B,　Q　サーチとの関係を調べておく必要がある。あまりにも多くのアイディアが次から次へと思い浮かぶので整理しておかないと自分でも分からなくなるのではと心配である。

(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にいくつあるか、一つのセルにダブっているセルからやるといいということを思いついた。