(58) 和歌山ソフトウエア・コンテストに応募

　2006年9月14日　数独ソフトとその説明資料が完成したので、応募用紙に、（54）数独パネルの解析ソフト(要約)、（５５）解析ソフトの特徴、（５７）プログラム操作の方法、（50）ナンプレの探索法などの資料を添えて郵送した。

　なお、応募用紙に記入した作品について（目的、アピールポイントなど）の文章は次の通りである。
　
いま全世界で人気沸騰中の「数独（ナンプレ）パズル」の解析ソフトです。Excelの
画面に問題を入力するだけで簡単に誰でもどんな難問でも全自動で数秒にして
解答が得られます。独自の理論に基づき、4つの基本サーチと15種類の探索
マクロを備えており、人間の思考にそった全手筋のセルの値と探索法が出力
されるので、行き詰まったときの次の一手のヒントも得ることができます。問題の
征服に至までの全手順がグラフで示されるので、問題の特徴ややま場が一目
瞭然です。また使用した探索法の種類と数から問題の難易度も判定できるので、
挑戦者だけでなくパズル作成者にとっても大変参考となる解析ソフトです。

(57) プログラム計算のインプットの種類

使用方法

1　画面に.直接入力する方法
（１）　Open Page （Sheet 1）を選択する。
（２）　Clear　（Blue ) のコマンドボタンをクリックして画面の数字を消す。
（３）　画面のセルに直接問題の数字を入力する。
(4)　Problem　の番号を（D2)のセルにインプットする。
(5)　再度問題を使うときには、Store　Problem のコマンドボタンをクリックする。
（６）　Cal.(Input)　のコマンドボタンをクリックして計算を開始する。
（７）　正しい答えが得られたときには、Conquer が赤字で表示される。
（８）　同時に問題のレベルと計算時間が表示される。
（９）　計算手順はProcedure のコマンドボタンをクリックする。
（10）　解析の順番にセルの番地と入る値と使用する解法が表示されている。
（11）　グラフ1には各セルの値を探すのに要した経過時間がプロットされる。
（12）　前にインプットしてストアした問題を再計算する時には、問題番号を（D2）に入れる。
(13)　ReInput Problem をクリックするとストアーした問題が画面に呼び出される。
(15) 再計算の手順は（６）以降と同じである。

2.　データベースから入力する方法
（１）　このファイルには、「ポケット数独上級篇」（Sheet2)と「ニコリ数独名品100選」（Sheet6)
　　　　が入っている。
（２）　データベースを呼び出すのは、Sheet1のAC24に書かれた当該セルをダブルクリックする。
（３）　M1のセルにインプットされたのを確認する。
（４）　D2のセルに問題番号を入力する。
（５）　Input Problem のコマンドボタンをクリックすると画面に問題が表示される。
（6）　あとの操作は1.の（６）以降とおなじである。
（７）　データベースを作るのは空白シートを用意して同じ形式で問題を入力する。
（８）　Sheet 1 のマクロを凡例に沿って書き換える。

3.　　連続計算の方法
（１）　　一冊の本や複数の問題を連続して計算するときに使用する方法である。
（２）　　一連の問題を空白シートにデータベースシート（Sheet2 やSheet 6）と同じ形式で作成する。
（３）　　Sheet1 にタイトルをつけて、A22近辺のセルに書き込む。
（４）　　Sheet1 のマクロに凡例と同様にタイトル名にしたがって、isheet=入力シート、
　　　　　dsheet="Sheet4"を記入する。
（５）　　問題の数を1番から連続番号でつけ、最初と最後の問題をマクロに記入する。
（６）　　問題をインプットして、連続計算の準備は完了する。
（7）　　計算したい問題の最初と最後の問題番号をSheet1 のB2 とC2 にインプットする。
（８）　　Continuous Cal. のコマンドボタンをクリックすると計算が開始する。
　　　（デスプレイの表示画面を映すと時間がかかるので、Z30のコマンドボタンを使うと速い）
（９）　　計算結果の解答はResult of Cal.　のコマンドボタンをクリックする。正解であることの
　　　　Conquer　のマーク、問題のレベルおよび解析時間も同時に表示される。
（10）　Summary of Cal.　のコマンドボタンをクリックすると、連続計算のまとめが表示される。
　　　　表出セルおよび空白セルの数、消費時間、本解法でのレベル評価と作者(出版社)の
　　　　公表レベルおよび使用された解法の種類別の回数などである。　

(56) プログラムの操作の説明

　プログラムの操作は簡単で次の順序で計算が可能である。

　（１） 画面をクリアー
　（２） Database (Sheet 6) にあらかじめ入力した問題の「問題番号」を
　　　　入れる。
　（３） 「計算開始」をクリック。
　（４） 解が得られ、数独ルールを満足していると「Conquer」マークが示され、
　　　　同時に問題の難易度レベルおよび計算時間が示される。
　（５） 解き方の手順を見るには、「とき方のヒント」をクリック。49個の空白セルに
　　　入る順番とその番地と数字と使用した見つけ方が示されます。
　（６）計算過程にかかった計算時間の推移は「解析過程のグラフ」をクリック。
　（７）探索法の種類によって重みをつけてやり、計算でえられた探索法の順番
　　　にしたがって人間の思考の過程をシミュレートするには「シミュレーション」
　　　をクリック。
　　　実際に人間が解いた場合の経過時間の経緯は「Human」をクリック。
　（８）連続計算をする場合には「連続計算」をクリック。
　　　初級の問題ならほぼ2分前後でとくことができる。
　

(55) 数独解析ソフトの特徴

解析ソフトの特徴
（１）　　Excel　VBA で書かれた全自動の数独ソルバーである。部分的にパソコン
　　　　を使うのはあるようだが、全自動は聞いたことがない。
（２）　　誰でもどこでも操作できる容量の小さい（1.4MB）簡易プログラムで難しい
　　　　操作は要らない。数字を入力するだけで、PC嫌いの人でも簡単に使える。
（３）　　独自の理論に基づく特性マトリックスを導入し、バグのない簡素な解法の
　　　　プログラミングを可能にした。また効率のよいマトリックス演算により高速
　　　　計算を実現している。
（４）　　これまで公表されている数独の解法を体系化した。基本解法4種類に
　　　　加え、15種類の解法を組み込み、今のところ難解問題をすべて征服し、
　　　　解けない問題はない。
　　　　　そのため、問題の入力ミスやプリントミスが発見できる。（本や雑誌に
　　　　　掲載されている解法の説明は実に誤りが多い）
（５）　　これを可能にしている最強の解法はAサーチである。このサーチでは
　　　　手順が行き詰まったとき候補の一つを仮定して次に進む。（「矛盾の常識」
　　　　として紹介しているものあり、ただし1階層のみ）本解法では5階層に
　　　　わたって探索する。大抵の場合、基本サーチとAサーチだけで解に到達
　　　　することができる。しかし人間が解く場合色々な解法を見つけるのが
　　　　パズルの醍醐味であるのでこれはすべての他の解法が上手くいかなかった
　　　　場合のみ使うようになっている。
（６）　　解が求まっても正しくルールを満足しているかどうかを調べるルール
　　　　チェックの機能を持っている。解が正しければ「Conquer」と表示し、誤って
　　　　いればその誤りの場所を表示する。これはインプットミスなどで解けない
　　　　場合しばしば起こる。
（７）　　計算は①直接画面に数字をインプットして行う方法と②あらかじめシート
　　　　に書き込んだデータベースから問題を取り出して行う方法および③データ
　　　　ベースの問題を連続して解く方法の3種類が選択できる。
（８）　　解析結果は解答とともに解析の進行にしたがって解の数字と場所および
　　　　使われた解法を現す記号が表示される。途中段階で行き詰まったとき、
　　　　どの数字あるいはセルに注目してどんな解法を使えばよいのかのヒントを
　　　　得ることができる。
（９）　　　同時に計算時間もわかるので、解析の進行とともに消費した時間を
　　　　プロットし（グラフ 1 ）ごく大雑把な問題解析の特徴を類推することができる。
　　　　各解法に評価値を与え、解析の進行とともに変化量を推定する手法を
　　　　提案している。人間の思考脳力と関連付けることも考えられる。
（10）　　本解法独自の難易度レベルの設定を行っている。レベルは8段階で、
　　　　順次、「Beginner」、「Very　Easy」、「Easy」、「Pleasant」、
　　　　「Comfort」、「Hard」、「Very Hard」、「Ultra　Hard」である。難易度の
　　　　測定は人間の勘に頼る部分が多いが、本方法では完全に自動的に行わ
　　　　れる。問題作成者にはよい道しるべとなるだろう。
（11）　　本ソフトは拡大ナンプレや変形ナンプレに対して簡単なマクロの追加や
　　　　変更によってVersion Up　することができる。

(54) 数独パズルの解析ソフト（要約）

数独（ナンプレ）パズルの解析ソフト
はじめに
いま全世界で人気沸騰中の「数独パズル」のソルバーです。
　　(参考：鍛冶真起　文芸春秋6月号｢数独｣パズル世界を制す）

数独のルールは超簡単で次の二つです。
　（１）タテ9列、ヨコ9行のそれぞれに1～9の数字が一つずつ入る。
　（２）太枠で囲まれたブロックにも1～9の数字が一つずつ入る。
解き方も基本は、
　　　①｢数字の入る場所が一つしかないセル」を特定することと
　　　②｢候補の数字を一つしか持たないセル」をさがすことです。
①の解法では、ブロックの中で一つのセルにしか入れない数字を探す方法
（「B」サーチと呼ぶ)と行や列の中で探す方法（それぞれ「L]サーチおよび
「C]サーチと呼ぶ）があります。
②の解法（「M」サーチとよぶ）は解法としては基本なのですが、実際には
①より探しにくいためか高くレベル付けされているのもあります。(100選26番）
　ニコリ名品100選には、Bサーチだけで解ける問題が30題もあります。
このレベルを「Beginner」となづけました。　この4つの基本サーチだけで
解ける問題が７０題ありました。レベル的にはVery Easy が16題、Easy が
24題の内訳です。残った30題をスラスラ解けるのをソフト開発の目標にした
結果、この100題を2分34秒で解くことができました。
　本解析ソフトでは、これら4つの基本解法に加え、15の解法を使ってどんな
難問であっても解くことができます。早く解くことが目的ではないのですが、
ある程度問題の難易度を推定することができるので、難問ナンプレを数冊
解いてみた結果、次のようになりました。

　ポケット数独上級篇　（105題）　　　　　　3分10秒　　　
　激辛数独　3　（105題）　　　　　　　　　　　3分36秒
　ナンプレ超上級編 11　（101題）　　　　　　　5分37秒
　難問ナンプレに挑戦　2　（101題）　　　　　7分50秒
　西尾徹也のナンプレBS 100 (100題）　　　3分23秒

　これまで、数独のどの雑誌やどの本にも最終的な解答はあるものの行き
詰まったとき、どんな解法で、どこに目をつけて進めばよいのかをヒント
として与えているものを見かけたことがありません。
　本解析ソフトでは独自の方法でその手順と解法の表現法を実現しました。
そして問題着手から征服までに遭遇するポイント（次の一手）とそのタイミング
が一目瞭然にわかり解答者の達成感（挫折感？）を浮き彫りにします。
　また、これまで解答者の技量と感覚に頼っていた難易度レベルの評価に
ついても、使用する解法の種類と特徴から判定する独自の手法を提案して
いるので、問題作成者にとっても一助となることが期待できます。
　解析理論は独自に考案した画期的な手法を使用しています。Candidate
matrix(空白セルの数字の候補の集合を貯える行列)とブロック、行と列の
3種類のg-matrix（数字の入るセルの集合を貯えた3次元行列）を車の両輪
のごとく使い解法のプログラミング化を達成しました。
　この理論の構築なくして、この効率のよいソフトの開発はなかったといえます。
　使用している探索法を一覧表にまとめました。
　表中には本などで紹介されている解法と本解法との関係も示しておきました。
　本ソフトはノーマル・ナンプレ（9×9）に対応するものですが、拡大ナンプレ
（16×16、25×25、49×49）用にも容易に変更可能です。また変形ナンプレ
（対角線ナンプレ、幾何学ナンプレ、合体ナンプレなど）にも簡単に改良できます。

(53) 数独本の計算速度の比較

　2006年9月1日、本ソフトの目玉の一つは数独本一冊を自動連続計算ができる点である。探索法毎の重みずけをしなくても、パソコンでの計算時間はほぼ、問題の難易度に比例するようである。そこで、難問ナンプレの本を買って来てあったものについて、連続計算を実施した。結果は次の通りである。

　ニコリ数独名品　100選　（100題）　　　　　　　　　　2分34秒
　ポケット数独上級編　　　（105題）　　　　　　　　　　3分10秒
　激辛数独　1　　　　　　　（105題）　　　　　　　　　　3分　1秒
　激辛数独　2　　　　　　　（105題）　　　　　　　　　　3分23秒
　激辛数独　3　　　　　　　（105題）　　　　　　　　　　3分36秒　
　西尾徹也のナンプレ　BS 100　（100題）　　　　　3分23秒　
　ナンプレ超上級編　11　　（101題）　　　　　　　　　5分37秒　
　難問ナンプレに挑戦　2　（101題）　　　　　　　　　7分50秒

(52) ソフコンのキャッチフレーズ

　2006年第15回和歌山ソフトウエアコンテストの応募が　9月1日から始まる。応募作品はほぼ完成したが、そのプレゼン資料を作成するに当たって、何かキャッチフレーズが必要だと思っていた。つまり大学の研究室で何のためにこんなパズルのソフトを研究しているのか。学生用のVBAプログラミングの練習用への応用というのでは、如何にも説得力にかける。やはり、「（３８）難易度レベルと脳力シミュレーション」で書いたように、人間の思考と関連させた方がよさそうだと考えて、「人間の思考過程や能力をコンピューターでシミュレート、数独パズルに挑戦！」とした。

　コンピュータの計算結果の経過時間（Elapse　Time）を縦軸にプロットしたグラフを描いてみると、pleasant　や　comfort　の問題では、明らかにどの段階が問題の山場になっているのかが、グラフから読み取れた。学生に数独を解いてもらい、時間（Comsumed　Time)も同時にメモしてもらった。パソコンで解いた結果と比較してみると、やさしい問題　（Beginner)ではその傾向は一致した。パソコンの性能にもよるが、おおよそパソコンの　400倍くらいの時間を要している。ただし、easy　レベルからは、にわか仕込みの学生には無理であった。残念なことに数独のマニアはいなかったし、また、途中経過時間のデータも得られなかった。
　

(51) 難易度の判定

　ナンプレの探索法による難易度評価について試案を考えた。
まず使用する探索法のレベルを次のように大まかな分類をする。
　基本サーチ　　　　　B , L , C , M
　中級サーチ　　　　　V , G , Q , P, U
　上級サーチ　　　　　T , R , S , H , W , Y , X , K , D
　超上級サーチ　　　 A

　通常、数独本には、問題毎に難易度が示されている。例えば、「ニコリ数独名品100選」では、Easy , Medium , Hard , Super Hard の 4 段階で、「西尾徹也のナンプレ　Best Selection 100 」では、Beginner , Easy , Medium , Heavy , Super Heavy 」の 5 段階のごときである。

　本ソフトに於いても、問題を解くのに必要な探索法の種類によって難易度を分類する8段階の評価法を採用した。

　Beginner　　　　　　　B
　Very Easy 　　　　　　B , L , C
　Easy 　　　　　　　　　B , L , C , M

　Plesant 　　　　　　　+ V , G , Q , P , U
　Comfort 　　　　　　　+ T , R , S , H , W ,Y , X , K
　Hard 　　　　　　　　　+ A (1)
　Very Hard 　　　　　　+ A (2)
　Ultra Hard 　　　　　　+ A (3)

　A サーチの括弧は、仮定する数字の数である。

　数独本の難易度評価と本ソフトの評価の比較を次に示そう。

　　ニコリ数独名品100選　　　　　　　　　　　　　本ソフト　　　
　　　Easy　　　　　　　 28 　　　　　　　　Beginner 　　　　　30
　　　Medium 　　　　　27 　　　　　　　　Very Easy 　　　　16
　　　Hard 　　　　　　　32　　　　　　　　 Easy 　　　　　　　24
　　　Super Hard 　　　13 　　　　　　　　Pleasant　　　　　 8
　　　　　　　　　合計　100 題 　　　　　　Comfort 　　　　　15
　　　　　　　　　　　　　　　　　　　　　　　　Hard 　　　　　　　4
　　　　　　　　　　　　　　　　　　　　　　　 Very Hard　　　　 0
　　　　　　　　　　　　　　　　　　　　　　　　Ultra Hard 　　　3

　西尾徹也の Best Selection　100　　　　本ソフト
　　Beginner　　　　　　5　　　　　　　　　　Beginner　　　　　5
　　Easy　　　　　　　　15　　　　　　　　　　Very　Easy　　　8　
　　Medium　　　　　　30　　　　　　　　　Easy　　　　　 　　8
　　Heavy　　　　　　　30　　　　　　　　　Pleasant　　　　　21
　　Super　Heavy　　11　　　　　　　　　Comfort　　　　　41
　　　　　　　合計　101題　　　　　　　　　Hard　　　　　　　6　
　　　　　　　　　　　　　　　　　　　　　　　　Very　Hard　　　8
　　　　　　　　　　　　　　　　　　　　　　　　Ultra　Hard　　　4　　　

(50) ナンプレ探索法の開発

　２００６年８月下旬にかけて、can matrix , g matrix を使ったナンプレ探索法を一気に開発した。参考にした解法は当時の数独本に断片的に掲載されていたもので、下記に示す。
　探索法はすでに述べた4つの基本サーチに加えて15個の探索法よりなっている。一つひとつの説明は省略するが、その全体の概要は次の通りである。


探索記号　　　　マクロの名称　　　　　探索原理と公表されている解法
（文献は下記に示す）

　B　　　　　　　B_search　　　　　　　あるBlockの中で入るセルが一つしかない数
字を探す。
　　　　　　　　　　　　　　　　　　　　　　　　初級パターン①②③④
　　　　　　　　　　　　　　　　　　　　　　　　point　１
　　　　　　　　　　　　　　　　　　　　　　　　平行線、水平線、垂直線の常識
　　　　　　　　　　　　　　　　　　　　　　　　直交平行線の常識
　
　L　　　　　　　L_search　　　　　　　ある行の中で入るセルが一つしかない数字を
　　　　　　　　　　　　　　　　　　　　　　探す。
　　　　　　　　　　　　　　　　　　　　　　　　初級ショキュウパターン⑤
　　　　　　　　　　　　　　　　　　　　　　　　point　2
　
　C　　　　　　　C_search　　　　　　　ある列の中で入るセルが一つしかない数字
　　　　　　　　　　　　　　　　　　　　　　を探す。
　　　　　　　　　　　　　　　　　　　　　　　　point　3
　
　M　　　　　　　M_search　　　　　　一つしか候補をもたないセルを探す。
　　　　　　　　　　　　　　　　　　　　　　　　中級パターン④、⑤
　　　　　　　　　　　　　　　　　　　　　　　　上級パターン②
　　　　　　　　　　　　　　　　　　　　　　　　point　４
　　　　　　　　　　　　　　　　　　　　　　　　残り物の常識、別方向からの決定


V　　pair_number_search_process　　　あるBlock 2つだけの数字が水平ま
　　　　　　　　　　　　　　　　　　　　　　　　　たは垂直に並んでいるとき、同行ま
　　　　　　　　　　　　　　　　　　　　　　　　　たは同列にはその数字は入らない。
　　　　　　　　　　　　　　　　　　　　　　　　　　　中級パターン③
　　　　　　　　　　　　　　　　　　　　　　　　　　　ローカル系
　
G　　pair_block_cell_search_process　　
　　　pair_line_cell_search_process 　　　
　　pair_column_cell_search_process 　
　　　　同Block、同列、同行内で二つのセルが同じ数字の二つの候補だけを
　　　　もつとき、Block 内、同列、同行の他のセルはそれらの候補をもたない。 　　　　　　　　　　　　　　　　　　　　　　　　　

Q　　double_pair_cell_search 　　　　　　同Block,同行、同列で二つのセル
　　　line_column_double_pair_cell_search　　が二つの数字を専有する
　　　　　　　　　　　　　　　　　　　　　ときこれらのセルは他の候補を持たない。
　　　　　　　　　　　　　　　　　　　　　　　　　上級パターン①
　　　　　　　　　　　　　　　　　　　　　　　　　定員確定の法則
　　　　　　　　　　　　　　　　　　　　　　　　　コンビネーション系
　　　　　　　　　　　　　　　　　　　　　　　　　二重線の常識

T 　　triple_block_cell_search_process 　
　　　triple_column_cell_search_process　
　　　triple_line_cell_search_process
　　　　　同Block,同行、同列で三つセルが三つの数字を専有するとき
　　　　 これら以外のセルはその三つの数字の候補を持たない。
　　　　　　　　　　　　　　　　　　　　　　　　　三国同盟

P parallel_line_number_search_process
　 parallel_column_number_search_process
二つの行または列に同じ数字の入るセルが二つありその列
　　　　 または行が等しいとき他のセルにはその数字は入らない。
　　　　　　　　四角の対角線
　　　　　　　　マトリックス系
U 　triple_parallel_line_number_search_process
　　triple_parallel_column_number_search_process
三つの行または列にわたり二つの数字をもつ番地が交互に
　　　　配列されるとき同じ列または行の他のセルにはその数は入
　　　　りえない。
　　　　　　　　マトリックス系
R　triple_pair_block_search
　　triple_pair_line_column_search
　　　　同じBlock,行、列の中の三つのセルに三の同じ数字を持つ
　　　　セルがあればそのセルは三つの数字で専有され他の候補
　　　　を持たない。
　　　　　　　　コンビネーション系

S　cross_pair_block_search
cross_pair_line_column_search
あるBlockの二つの数字の行または列が等しく、他のBlock
の同じ数字の一つが同行または同列にあるとき残のセルが
その数字になる。
　　　　　　　　point 5
　　　　　　　　コンビネーション系
　
H　Hamada_line_search
　　Hamada_column_search
　　　同Blockの二つのセルと同行、同列にあるセルの同じ二つの
　　　候補より巧妙にこれらの数字を特定する。
　　　　　　　　浜田ロジック
　
W 　pair_number_line_search
　　　ある行の二つの数字の候補が、あるBlockにあるときBlock内
　　　のセルはその数字の候補を持たない。

A　output_two_candidate
　　new_class_search
　　　二つに候補をもつセルの一つの数字を仮定して探索を続ける。
　　　もし行き詰ると、もうひとつの他の数字が特定できる。
　　　　　　　矛盾の常識
　
Y　 pair_number_column_search
　　　　ある列の二つの数字の候補が、あるBlockにあるときBlock内
　　　　のセルはその数字の候補を持たない。
　
X 　triple_number_search_process
　　　同Block内の3つの候補が同行または同列に並ぶときその行、
　　　列の他のセルはその候補を持たない。
　　　　　　中級パターン②
　　　　　　ローカル系
　　　　　　空き直線の常識
　
K 　triple_parallel_line_search
　　triple_parallel_column_search
　　　　二つの行(列)に候補が矩形状に配置されるとき、同じ数字
　　　　をもつ他の行(列)の数字が特定される。
　　　　　　四角の対角線
　
D　rectangular_block_line_search
　　rectangular_block_column_search
　　　　二つの行(列)に候補が矩形状に配置されるとき、同行(列)
　　　　に同じ数字をもつBlockの数字が特定される。


公表されている解法は次の資料を参考にしました。
　（１）　　ニコリ｢数独｣名品100選：ニコリ編著　（文芸春秋）
　　　　　　初級パターン、中級パターン、上級パターン
　（２）　　ナンプレ超上級編11　西尾徹也　（世界文化社）
　　　　　　三国同盟、四角の対角線、浜田ロジック
　（３）　　難問ナンプレに挑戦　2　　稲葉直貴　(世界文化社）
　　　　　　ローカル系、コンビネーション系、マトリックス系
　（４）　　西尾徹也のナンプレBS　100　西尾徹也　（世界文化社）
　　　　　　point　1～point　５、point　６(定員確定の法)
　（５）　　ナンバープレイス解法教室　藤原
　　　　　　http://www.pro.or.jp/~fuji/java/puzzle/numplace/knowhow.1-1
　　　　　平行線、水平線、垂直線の常識
　　　　　直交平行線の常識,別方向からの決定
　　　　　二重線の常識、空き直線の常識
　　　　　残り物の常識、矛盾の常識

(49) B search , L search and C search

　g matrix を使うと、
　　B search : ブロック ( igrp ) に一つしかない数字 (numb ) をもつセルを探す。これは、gg matrix を使って、gg ( igrp , numb , 2 ) = 1 とあらわすことができる。
　同様にして、
L search : 行 ( ilin ) に一つしかない数字 (numb ) をもつセルを探す。これは、gl matrix を使って、gl ( ilin , numb , 2 ) = 1 とあらわすことができる。

C search : 列 ( icol ) に一つしかない数字 (numb ) をもつセルを探す。これは、gc matrix を使って、gc ( icol , numb , 2 ) = 1 とあらわすことができる。

　B search に対して、実際のプログラムを以下に示す。これらの探索法は SUDOKU_Ver33 から使われている。

Sub B_search()
For igrp = 1 To z
For numb = 1 To z
If gg(igrp, numb, 2) = 1 Then
cc = gg(igrp, numb, 3)
row_column_number
i1 = aa: i2 = bb
Else
GoTo contnumb
End If
If Sheets("Sheet1").Cells(ppp + i1, qqq + i2) <> "" Then GoTo contnumb
Sheets("Sheet1").Cells(ppp + i1, qqq + i2) = numb
numa = numa + 1
Sheets("Sheet6").Cells(numa + 17, 1) = numa - 1
Sheets("Sheet6").Cells(numa + 17, 2) = "(" & i1 & "," & i2 & ")"
Sheets("Sheet6").Cells(numa + 17, 3) = numb
Sheets("Sheet6").Cells(numa + 17, 4) = sch
Sheets("Sheet6").Cells(numa + 17, 21) = 0.01 * (Int(100 * (Timer - timer0)))
Sheets("Sheet6").Range("A18") = numa - 1
Sheets("Sheet1").Range("D6") = numa - 1
contnumb:
Next numb
Next igrp
End Sub

(48) g matrix を作るマクロ

　SUDOKU_Ver.33 において、初めて g matrix が作成され、使用された。g matrix は　gg_matrix , gl_matrix , gc_matrix よりなる。いずれも 1 から 9 までの任意の数字 ( numb ) が、あるブロック ( igrp ) あるいは、ある行 ( ilin ) あるいは、ある列 ( icol ) に存在する空白セルがいくつ、どこにあるかを表す三次元 matrix である。

gg_matrix を例にとり、その内容を示そう。

gg ( igrp , numb , 1 ) = igrp 数字の存在するブロック番号
gg ( igrp , numb , 2 ) = num 　digit が numb のそのブロックに存在する空白セルの数
gg ( igrp , numb , 3 ) = ( i1, j1 ) : num = 1 　候補 numb をもつ一番目の空白セルの位置
gg ( igrp , numb , 4 ) = ( i2 ,j2 ) : num = 2　 候補 numb をもつ二番目の空白セルの位置
・・・・・・・・・・・
gg ( igrp , numb , 2+num ) = ( inum , jnum ) 候補 numb をもつ num 番目の空白セルの位置

gg_matrix は、 can matrix よりつくられる。そのマクロ　block_number_table を次に示す。

Sub block_number_table ( )
　　ReDim gg(z, z, z + 2)
ReDim xi(z), yi(z), bz(z)
For i = 1 To z
For j = 1 To z
For k = 1 To z + 2
gg ( i , j , k ) = " "
Next k
Next j
Next i
empty_cell = Sheets("Sheet1").Range("K2")
For numb = 1 To z
For igrp = 1 To z
num = 0
For i = 1 To empty_cell
If can(i, 4) <> igrp Then GoTo conti
ikumi = can(i, 5)
For j = 1 To ikumi
If numb = can(i, 5 + j) Then
num = num + 1
xi(num) = can(i, 2): yi(num) = can(i, 3)
bz(num) = can(i, 1)
End If
Next j
conti:
Next i
gg(igrp, numb, 1) = igrp
gg(igrp, numb, 2) = num
For k = 1 To num
gg(igrp, numb, 2 + k) = bz(k)
Next k
Next igrp
Next numb
End Sub

(47) candy_matrix と M_search

　SUDOKU_Ver32 ( CTM ) は　Candy Table Matrix を使った最初のプログラムである。空白セル番号 j である candy matrix , can ( j , i ) は 5+k 個の要素を持つ二次元マトリックスである。

　can ( j , 1 ) =　空白セルの番地、例えば、　( 3 ,8 )
can ( j , 2 ) =　空白セルの行番号、　3　
can ( j , 3 ) =　空白セルの列番号、　8　　　　
can ( j , 4 ) =　空白セルの属するブロック番号、例えば、中央ブロックは 5
can ( j , 5 ) =　候補の個数、　k 個とする。 　
can ( j , 6 ) =　一番目の候補、　a1
can ( j , 7 ) =　二番目の候補、　a2
・・・・・・・・・・・

can ( j , 5+k ) =　k 番目の候補、　ak

can matrix に蓄えられる候補の digit は、1 から 9 までの digit の中で小さい数から順に k 個蓄えられるのがプログラム上のポイントである。

can matrix を使った M_search マクロの例を以下に示そう。

Sub M_search()
　empty_cell = Sheets("Sheet1").Range("K2")
For i = 1 To empty_cell
If can(i, 5) = 1 Then
　 　 ii = can(i, 2)
　　 jj = can(i, 3)
　　ak = can(i, 6)
　 If Sheets("Sheet1").Cells(ppp + ii, qqq + jj) <> "" Then GoTo contii
　　Sheets("Sheet1").Cells(ppp + ii, qqq + jj) = ak
　　numa = numa + 1
　　Sheets("Sheet6").Cells(numa + 17, 1) = numa - 1
　　Sheets("Sheet6").Cells(numa + 17, 2) = "(" & ii & "," & jj & ")"
　　Sheets("Sheet6").Cells(numa + 17, 3) = ak
　　Sheets("Sheet6").Cells(numa + 17, 4) = sch
　　Sheets("Sheet6").Cells(numa + 17, 21) = 0.01 * (Int(100 * (Timer - timer0)))
　　Sheets("Sheet6").Range("A18") = numa - 1
　　End If
contii:
　Next i
End Sub

M_search の「候補を一つしか持たないセル」は、 can ( j , 5 )= 1 と簡単にあらわすことができるので、マクロの中で四行目だけが重要である。あとは何番目に見つかったかや、その番地や数字、その探索法と時間を記録しているだけである。

(46) 感激の日に遭遇

　2006年8月15日（火）　数独を知ってから、初めての感激の日に遭遇した。これまでのプログラミングの長い経験から、構成が固まってからプログラミングに入るまで出来るだけ時間を取るように心がけている。この辛抱が結局、ミスを少なくする秘訣であると体得した。またプログラミングを書くのは、パソコンで一気にやるのだが、はやる気持ちを抑えて、ゆっくりと間違いがないように進めるようにしている。一度犯したミスは同じ人が何回見直しても見過ごしてしまうことが多い。長年の経験でわかっていることは、一字間違ったところを、その時なら一度見直すだけで済むものが、日をおくと、何時間いや何日も費やしてしまうことがある。とにかく、はやる気持ちを抑えて、順に、順に進めていくのがポイントである。

　朝から number_table のプログラミングを見直した。昨夜、やったのに、僅かにバグがあった。 pj のところが pi になっていたのだ。　また、 g-matrix を　gg と　gl　と gc の三つの三次元 matrix でやることにした。

number_table が完成すると　P サーチや S サーチは簡単にできあがった。（後述）　これで流して見ると、ニコリ名品100題が　4分53秒　またポケット数独上級編が　6分11秒　と驚くべき速さを記録した。まだ、この三つの探索法しか使っていないのにだ！

(45) ナンプレVBA解法に新展開

　定期試験の成績報告やオープン・キャンパスなどあわただしい日々が過ぎ、和歌山ソフトウエアコンテストの応募受付開始まであと20日ばかりを残すまでとなり、夏休みの日を迎えることになった。メモ（４４）に到達するまでの当時の経緯を日記から拾い出して見よう。

　2006年8月14日(月)　数独の手筋を整理しようといろいろ考えていると、candy table に対して、number table というのを作成した方が手筋を表しやすいのではないかと思いつき、それが、これまでやってきたことを基本から覆すような、どでかい発想であるのではないかと思えた。数独のVBA解法というマニアックな分野の中で、このようなモデル化で、ここまでたどり着いているのは、日本中で、いや世界中でも数少ないのではないかという気がしてきた。

　まず、 candy table を　Excel　画面上に作成するのではなく、matrix で表現することを考え、そのプログラムをかき成功した。おかげで画面がちらちらすることはなくなり、計算時間も画期的に早くなった。　

(44) ナンバープレースのモデル化

　数学的手法でもって、あるいはコンピュータを使ってある問題を解くとき、まず数式で取り扱えるように、問題の本質（特性）をかえることなく、考えやすいモデルであらわせないかどうかをかんがえる。そのように考えだされたものがモデル化ということが出来る。

　ナンバープレースにおいては、空白セルの中に数字をいれる。セルはユニット（ Block , Row , Column ) に属し、数字はユニットの unique digit である。したがって、セルで考えるか、数字で考えるかで、二つのモデルが存在する。正確には、それぞれ、三つのモデルを構成する。

　候補の数字を要素にもつセルは candidate matrix ( candy_table ) である。candidate を一つしか持たないセルはその数字が answer となる。(　M サーチ ) 　本来は candy_table は三つよりなる物だが、これはこれまでの成り行きでまとめて一つとしよう。

　ナンバープレースの解き方の基本は「候補の数字を一つしか持たないセル」を探すことと「数字のはいる場所が一つしかないセル」を見つけることである。この基本を一度の操作で見極められるサーチが基本サーチと呼ぶ。Block ,　Row , Column のそれぞれに対して、Bサーチ、Rサーチ、Cサーチが存在する。基本サーチはこの四つである。複数個の候補を持つセルから、その数字の配列特性を考慮して、如何にして候補の数を絞りこむかが探索法の鍵である。　　

(43) カラーナンプレ ( SUDOKU_Ver30 )

　カラー・ナンプレ、もしくはツートン・カラー・ナンプレは、ノーマルナンプレに、さらに色づけされた　9個のセルからなる　Block　が追加されている。通常この　Block に属するセルは縦横に連続した形状となっていて、これが二つの　Block　からなる場合には、ツートン・カラー・ナンプレと呼ばれる。

　2006年8月9日　SUDOKU_Ver27 （幾何学ナンプレ）より発展させて、専用の　SUDOKU_Ver30 を作成した。　幾何学ナンプレ用の block 分けの nx( i , j ) matrix　に加えて、さらに　color block ようの matrix である cx( i , j ) matrix を追加した。したがって、この方式では、ノーマルナンプレでなくても、任意の Block 割りのものにも対応することが出来る。

(42) 幾何学ナンプレ（SUDOKU_Ver27）

　幾何学ナンプレは、別名ジグザグ・ナンプレとかジグソー・ナンプレとか呼ばれている。ノーマル・ナンプレは　9×9　の　81個のセルが規則正しく整列した　3×3　の9個のセルからなる9個の正方形の　Block　により構成される。一方、幾何学ナンプレは、不規則な9個のセルからなる　9個の　Block　から構成される。

　2006年8月7日(月)　幾何学ナンプレに挑戦する。これは、あっけないぐらい簡単に成功した。もともと　candy_table で候補の一覧を書き出し、　Block number 毎に検索するこの方式は幾何学ナンプレに向いているのではないか？SUDOKU_Ver.21 より改変して、SUDOKU_Ver.27 とした。

　具体的には、group_search をやめにして、　transfer_problem で読み込んだ nx( ci, cj) matrix　を checkmate の中で group 判定を行う。　group 分けのインプットは Sheet 2 に givens のインプットと並べておこなう。group のnumbering はどの順番であってもかわらない。nx matrix を使って、ノーマル・ナンプレの検証を行うことができる。　 　　

(41) 対角線ナンプレ(SUDOKU_Ver.26)

対角線ナンプレはノーマル・ナンプレのルールに加えて、さらに二つの対角線上の　9個のセルにも 1 から 9 までの数字が一つずつ入るというルールが加わる。これに対応するマクロは check の中に数行のステートメントを追加するだけでよい。

　改正マクロは次のようになる。

if iii<>jjj then goto contd
for i=1 to 9
for j=1 to 9
if i=j then
ccc=Cells( 6+i, 1+j)
if aaa=ccc then goto contaaa
end if
next j
next i

contd:

if iii<>(10-jjj) then goto contd

for i=1 to 9

for j=1 to 9

if i=10-j then

ccc=Cells( 6+i, 1+j)

if aaa=ccc then goto contaaa

end if

next j

next i

contdj:

　ここに、 Sheet 1 の　( 7, 2) から ( 15, 10) に　A 画面があり、前半の部分が右下がりの対角線で、後半の部分が左下がりの対角線に相当する。

(40) 合体ナンプレ事始

　ナンプレファンに載っている最もやさしい2葉の合体ナンプレについてやってみた。（SUDOKU_Ver25）　2葉のうち、一つのナンプレだけを取り出し、スタンダード・ナンプレとして解いてみる。方法は原始的なもので、行き詰ったところを出発点として、共通部分の空白セルの候補をもう一つのナンプレとの関連から類推して、試行錯誤で求めていくやり方である。

当時の記録から合体ナンプレの取り組みを書き記そう。

2006年7月31日　合体ナンプレの専用ソフト　Ver.25 　を立ち上げた。簡単に解けるものもあったが、大体はうまくいかない。一つのナンプレだけ取り出して解いてみると、10種類もの多数解が求まるものもあった。

2006年8月4日　合体ナンプレに取り組んでいるが、どうも手強い。何かうまい法則を見つけないとてに終えない。
ニコリ別冊に載っていた数独作者たちの座談会で老人たちが語っていたことを思い出した。「表出数の個数の少ないのを作っていく。20個にしたときに解き方のパターンが決まってくる」
何のことだか分からない。どのように取り組んだらいいのか。共通部分をどのように活用するのか。何かよい方法はないだろうか。どうもわからないことばかりである。

2006年8月6日　合体ナンプレの道が少しばかり開けた。数独の世界にこんな法則があったのかという思いがした。馬鹿だなあ。ちゃんとした候補があるのに。

これ以後合体ナンプレへの取り組みを中断する。スタンダード・ナンプレの解法に画期的なVBAの解法を発見したからである。それと、和歌山ソフコンの申し込みが迫ってきているからである。

その後、合体ナンプレの取り組みは2007年11月まで続き、60種類の合体ナンプレ（最高59連ナンプレ）が自動的に解けるソフトを開発した。これも、長い長い苦労話があり、項を改めて書くことにしよう。

(39) アート・ナンプレの提唱

　SUDOKU_Ver20 では、16×16　(block 4×4）サイズ数独を作成した。このとき、さらに大規模な 25×25 (block 5×5)　の数独、更に大きな数独にも対応できるように、Sheet　の割り振りを考えていたので、SUDOKU_Ver23 (25×25　対応)は、マクロ group_search を変更するだけで、簡単に作成できた。



　さらに、変形block ナンプレ、12×12　（Block 3×4　）や28×28　（Block　4×7）もマクロを一つ変えるだけで難なく作成することができた。（SUDOKU_Ver24）

　大規模数独になると、問題を解く手順や解法を見つける楽しみにもまして、根気や忍耐力で問題に取り組み、やり遂げる達成感というより、苦しみと戦うマゾ的 要素が加わる。パソコンソフトでなら何でもないことが、人間が取り組むとなると莫大な時間と強靭な気力が必要になる。逆に、コンピュータで解くには多少の物足りなさを感じる。

　問題を作る方も大規模数独となると大変なのであろうと推察する。（作ったことがないからわからないが）　数独問題の唯一解の特性だけを考慮すれば、ある問題では、第一手から final answer に至るまでの各ステップが問題になりえる。また、一つの問題でも、数字交換（1から9までの数字を交換する方法、これだけでも 9! 通りの同じ問題ができる）、Block 毎の行交換、列交換、各行または各列の Block 内交換、さらには8種類の対称交換（後述）を行っても、問題の本質は変わらないから事実上無限個の同一種類の問題が存在する。

　このようなことを考えながら大規模数独の面白さを引き出すひとつの方法として、「アート・ナンプレ」というのがあったら面白いのではと思った。ニコリ社の数独では、数字の配列が対称であることというのを特徴にしているようだが、ナンプレの問題での数字の配置が何かの形をなぞらえていたり、final answer の状態での数字の配列が「お絵かきロジック」のように、アートになっているといった類のものである。数独の新しい分野として考えられるのではないかとおもった。詰将棋の分野でも、手順を楽しむのと別にその奇抜な形の不思議を楽しむのがあったように記憶している。

(38) 難易度レベルと脳力シミュレーション

　SUDOKU_Ver.21 はVer.18　の改変し、いくつかの新しい機能を追加した。
　まず、空白セルの数字が決定される毎に、計算時間（ elapse time ）をアウトプットするようにした。同時に使用した探索法も分かっているので、パソコンでの使用時間と関連づけて、数独を人間が解くに要する時間により脳力シミュレーションができないかと考えた。例えば、Pサーチは1.0、Mサーチは1.5、Gサーチは4という風に重みをつけ、人間の解く時間とそのプロセスを比較すれば、何らかの脳力検定ができるのではないかということである。

　このソフトでは、数独問題を途中人の手を介さず、自動連続計算することにしているので、計算結果の一覧表を　Sheet 3 　に表記するように、　arrangement_result_to_sheet3 のマクロを新設した。また、一問別の計算結果情報（計算過程の手順など）を一枚のシートに移す transfer_arranged_data マクロを追加した。

　数独解のプロセスとElapse time　を示すグラフを追加した。このグラフより、問題を解く過程における問題の特性（解き味？）が一目瞭然とわかる。

　数独問題のレベルと探索法との関係がわかるレベル評価の方法を模索した。今のところ使用できる探索法は限られているので（ P, S, G, Q, M, C, V, X ） 、Aサーチの回数を表わす　klevel　 の値により、例えば　klevel=0 の場合は、「Easy」とし、klevel<=2 の場合、「Medium」のように、6段階に分けた。

(37) 大型数独への展開 （16×16 数独）

　先に購入した雑誌「ナンプレ・ファン」には、9×9　の数独（ノーマルナンプレと呼ぼう）の他に拡張したナンプレ（16×16　や　25×25　）問題が掲載されている。SUDOKU_Ver19　では、16×16　ナンプレ専用のプログラムを考えてみた。

　コンピュータ・ソフトの特徴は、大規模化にもかかわらず、正確さと計算時間が人間の能力をはるかに上回るその馬鹿さ加減にある。アルゴリズムは同じなのだから、簡単に大規模化には対応できるものであると考えてやってみた。

　実際には、簡単に拡張ソフトにはすることができたが、そのソフト自体の設計およびアルゴリズムの特徴により細かいところで、いくつかの変更を必要とした。これは、最初からこういう事態を想定していなかったための問題に起因するもので、アルゴリズムが違えばもっと手数は掛からないのかもしれない。

　（１）　計算はSheet １ の A画面 とのやり取りから始まる。A画面の拡張により、candy_table の表示部分を移す必要があった。
　（２）　問題の入力（Sheet 3）におけるセルの調整。
　（３）　解答の表示場所を新たに確保すること。　などである。
　（４）　探索マクロは、1から9　を　1から　Z　に変更し、Z=16　をSheet 1　のインプットで与える。これで、Z=25　にも対応できる。今回の拡張では、さらに大規模のものまで対応できるように考慮した。
　（５）　特に、Aサーチの　new_class_search では変更箇所が多く面倒であった。
　（６）　当然、group_search や iblock_search なども範囲の拡大をおこなった。

　今回の拡張で、セルの番地　（ i , j ) の取り出しで新しいマクロ　row_column_number を作成した。このマクロを使えば、81×81　ナンプレまで対応できる。つまり、9×9　は一桁で済んだが、二桁になるとちょっと取り出すのに工夫がいるので、その簡単なマクロを下に示そう。

　Sub row_column_number()
If Len(cc) = 5 Then
aa = Int(Val(Mid(cc, 2, 1))) ： bb = Int(Val(Mid(cc, 4, 1)))
ElseIf Len(cc) = 6 Then
　　　If Mid(cc, 3, 1) = "," Then
　aa = Int(Val(Mid(cc, 2, 1))) ： bb = Int(Val(Mid(cc, 4, 2)))
　　　ElseIf Mid(cc, 4, 1) = "," Then
　aa = Int(Val(Mid(cc, 2, 2))) ： bb = Int(Val(Mid(cc, 5, 1)))
　End If ElseIf Len(cc) = 7 Then
　aa = Int(Val(Mid(cc, 2, 2)))： bb = Int(Val(Mid(cc, 5, 2)))
Else MsgBox ("Banchi is mismatching!")
End If
End Sub

　番地から、行・列番号が必要なときには、次のように使う。
　　row_column_number
i=aa : j=bb

100×100　ナンプレにも同じようなマクロが作れるが、まだ試してはいない。
49×49ナンプレはその後問題があったので、解いてみたがインプットに時間が掛かる割には簡単にとけた。一般に大規模ナンプレはPサーチだけで解ける簡単な（コンピュータには）問題が多いようだ。人間には手に負えないというか忍耐力だけを試すことになってしまうためなのか。

(36) Ver.18 で大改造する。

　SUDOKU_Ver18 でプログラムの構成方法とマクロの組み立てを大幅に改変した。大きくは、探索方法の種類が増えたこと、その役割が何となくはっきりしてきたからである。

まず、 part_search_table を廃止して、 candy_table のみとする。流れとしては、（A)　candy_table の後、P, M, S, Q, V, などのサーチをする。　（B) refine_candy_table の後の P, S, Mサーチ（PR,MRなど）　（C)　two_candidate_search (A サーチ ) といった流れとなる。

　数独の解法の過程を考えてみると、空白セルの数字を決定するのは、あくまでも基本サーチだけである。その他のサーチでは、「候補になる可能性がない」ことにより候補から外されるだけで、結果として、その影響により、他のセルの候補の数字が single candidate になり、基本サーチにより数字が決定される。つまり、基本サーチ以外の探索法では、candy_table を書き換えて、 refine_candy_table を作るだけのことである。このことは、マクロの書き方にも関係してくることである。今のやり方では、これまでに決定された数字を含めた　A画面より candy_table が作られる。もし、refine_candy_table のあとの基本サーチでA 画面が変わらなければ、折角のサーチが無駄になってしまうのだ。

　もう一つの大きな改変は、candy_table を作るとき、各blockのなかで、空白セルの数字の数（anum） を探すやり方で　candidate をさがしていた。新しいやり方では、数字（numb）を1から9まで回して candidate を決定する方法である。この方法の採用により、計算時間は大幅に短縮された。

(35) 探索法の表示方法

　数独を解くにあたって、どのセルから、どの数字が、どのような順番で満たされていくのか。またそれは、どのような探索法を使えばよいのかが分かればよい。数独のどの本にも、最終結果（以後 final answer と呼ぶ。）は示してあるものの、それにいたる途中経過が示されていないので、行き詰まったときどのような手順を使うのかがはっきりしない場合がある。そこで、VBAソフトでは、決定される順にその探索法をアウトプットできるようにした。

　数独の解法は山に登るのと同じで、いくつかのルートがある。人間が解くのと同じとは必ず一致するものではないが、ソフトで求めた一つの手順があれば、それを参考にして人間が解く段階で行き詰ったときには「次の一手」を示すことが出来る。その論理は、コンピュータの手順と人間のそれまでの決定セルを比較して、コンピュータの手順に初めて表れる未決定セルが「次の一手」となる。

　ソフトで手順を示すには、基本サーチを徹底的に検索する。しかる後、V,　G,　Q などのサーチを使うのだが、これらは基本サーチではないので、このサーチを行った後、また、基本サーチを繰り返せばよい。具体的には、基本サーチ　”B”　では、
　　　sch=""
　　　extra="B"
とおき、　　sch=sch & extra 　をループの中にいれる。　結果、”B"　は最初の　Bサーチで求まったもの、さらにその結果を使って、求まったものは、”BB"　をなる。

さらに、基本サーチ以外では、そのサーチ・マクロを通ったとき、　sch="V" のようにする。その結果、
基本サーチの　”L”　で求まると　”VL"　のように、表記される。これらの表示はその決定されたセルと数字とともに、決定順にカウントされ、アウトプットされる。

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

(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分を要した。

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

(13) N君ソフト会社に就職内定する

2006年5月15日（月）の卒業研究ゼミで、N君がNTTコミュニケーションシステムズに就職が内定した旨の報告があった。この時期すでに内定をもらっている学生もいたが、そうでない学生は就職活動で飛び回っていて、ゼミは週一回全員顔を合わせて、一週間の研究の進捗状況や活動報告をすることになっていた。

研究室の配属は3年生の初めにあり、3年の後期には卒業研究に必要な演習を行う。私の研究室のゼミでは3年の終わり（実質的には1月末頃）までに各人の卒業研究のテーマとその内容を決め、プレゼンテーションが出来るようにしていた。長年の会社時代の技術面接の経験では、話題は卒業研究テーマぐらいしかないことを知っていたから。

Ｎ君の卒業研究テーマは、私の大学でのメインテーマの「乗り物酔い」に関するものであったが、まだ幾許も進んではいなかった。その日のゼミで、数独ソフトのＶｅｒ４を披露したら皆は「すごい」といってくれた。Ｎ君はソフトの会社にいくから、卒研もソフトに関するものをやりたいというので、数独の問題を解けるようになるようにと話をした。その時、私の頭の中にあるアイディアが思い浮かんでいた。学科名は「生体機械工学科」といい、研究室名は「生体ダイナミクス」であったので、数独ソフトを研究室テーマにふさわしいものにする必要があったのだ。

(12) Ver.4でA サーチの自動化

SUDOKU_Ver4(May2006) では曲がりなりにも Hard の問題がクリック一発で自動的に解けるようになった。同時に問題のインプット方式も少しは改良された。問題入力は transfer_problem のマクロでsheet1の問題番号を入れるセルに入力した問題番号を読み取り、Sheet2に記載した問題をSheet1のA面に移す。Sheet2　にインプットした問題も Hard なものばかり　３２題になっていた。

自動化の方は、新しく auto_search というマクロをつくった。このマクロは ippatsu と　back_to_win を解が得られるまでnumk回繰り返す。ippatsu の中には search_single （BM サーチ）を含んでいるのでそれで行き詰ったときには、Ver.3　で手動でやっていた操作に切り替わる。仮定した数字でまた　search_single を行うが、一回ではうまくいかないので、行き詰ると仮定する前の段階に戻り、新しい仮定した数字で実行する。

Sheet1のA画面にはその様子は逐次表示されるので、どのように解析が進んでいるのかわかり、 Final answer に到達したときには感動的である。numkを10回まわすと打ち切るようにしているが、これは Hard な問題では、空回りをおこすからだ。仮定法ではルートがねずみ算的に増えていくので、うまく数字を仮定すると一発で解けるし、そうでない場合にはすごく複雑なルーチンになる。最終的には５階層つまり３２ルートを正確に自動的に解くのを　Aサーチとしたがこれが完成するのはもっとあとのことであった。

(11) 数独パズル世界を制す

２００６年５月１２日(金)の日記に次のような記載がある。
「文芸春秋６月号に数独パズルのニコリ社の社長鍛冶真起氏の話がのっていた。独は独身の人が楽しむ、single の数字と使ってするパズルだから数独というそうだ。上、中、下という三つのパズルが載っていて、これを正解するためには私の今のソフトに改良を加えなければならない。まだまだ解き方に工夫を凝らさねばならない。」とある。

この記事の中には、解き方の話やそのソフトについては何も書いてなかったが、コンピューターメイドの問題は解き味がハンドメイドのものに劣るようである。数独の作問にもいろいろ苦労があることが伺えた。このあたりが分かれば面白い、それにはまずこの三問が全自動で解けることは先決であると改めて興味をもった。

後になって、使用する解法の種類によって6つのレベルに分類する独自のランク付けを考案したが、この三つの問題（ニコリ数独名品100選の6番（Easy）、30番（Medium）、49番（Hard））は私の分類では、6番はBeginner,30番は Very Easy, 49番は Easy となった。これらはすべて基本サーチ（BLCM)で解くことができる。6番はBサーチだけで、30番はBLCサーチでMサーチは使わないでよい。49番はBLCMのサーチを使う。49番を解いてみると、Lサーチから始まる。出だしからして基本サーチとは言え見つけにくいのではないか。49番はLサーチの解説にはよい問題だろう。でも上級者にはEasyな問題なのだろうとこの作者も注記している。

(10) Ver.3 で A サーチの奔り

この時点(２００６年５月８日）でとにかく、どんなに難しい問題でも一回のクリックで Final Answer に到達するアルゴリズムがあるはずで、容易に考えつくのが解を仮定してしらみつぶしに調べていく方法である。数学的には、条件付連立方程式の重複のない整数解を解く問題に帰着できると考えていた。それも簡単なプログラムで。

この探索法は問題を解くという観点からいえば最強の方法である。後に、A search という名付けた方法は、「仮定法」とか「矛盾の常識」として紹介さあれている。

sudoku_Ver3(May 2006) ではその奔りとなるいくつかのマクロを開発した。search_cell_with_two_candidate というのは、候補が二つしかないセルとその値をリストアップするマクロである。back_to_win は行き詰ったとき、前の記録をないものにして仮定前の状態に戻すマクロである。あと known_number, input_added_cell, transfer_A_to_B, transfer_B_to_A とかいろいろある。Sheet 1 のなかで　A画面がもとのめいんの表で仮定するときにはいったんB画面に残しておくのである。

これらのマクロを順次使うことでこれまで解けなかった問題がいくらか解けるようになった。ただ仮定すつセルの数が増えるとものすごく複雑でそれこそ手に負えない。とりあえず、２階層ぐらいの問題を自動的に解けるように sodoku_Ver.4 の開発に取り掛かった。

Hard な問題でいきどまる

２００６年５月８日、数独のむづかしい問題を求めて、インターネットで調べてみた。これまでVer1で試みたのはすべて、読売新聞や文芸春秋にスポット的に掲載されているもので、読者のレベルをかんがえた　Easy　な問題ばかりであった。すると「晴耕数独 on WWW 」というサイトに、Easy, Medium, Hard にレベルわけされた多数の問題集があるのを見つけた。

早速、５題ばかり Hard の問題を取り出し、開発したばかりのVer.2にかけてみた。どれも解けなかった。いたずらに空回りするばかりで、新しい解法が必要なのはあきらかであった。ここで誰もが考えるのはコンピューターの馬鹿力を利用した方法で、西山先生のおっしゃるコンピュータに適した方法というものである。

つまり候補の数字を二つもつセルにおいて、どちらかが正解であるわけだから、そのひとつを仮定して進めるというものである。行き詰るともとに引き返してつぎの仮定の数字を実行する。ひとつのセルだけで Final Answer　にたどりつけばよいが大抵の場合はそうはいかない。これは「矛盾の常識」として知られる解法のひとつであるが、何段階も続くとねずみ算でルートが増えてきて、まさに「コンピューターに適した方法」いうことができる。

問題のインプットに一苦労

数独に限らずコンピュータで計算するときの入力データほど手数がかかるものはない。データが多いほど慎重に間違いの無いようにしなければならない。そのためのデータ入力方法の簡易化や効率化は数独の解法以上に重要とおもっている。

数独の場合、解けない問題や複数解になると入力ミスだとおもってまず間違いない。困るのは解ける場合であるが、これは数字を一箇所入れ忘れた時にしばしばおこる。数独では最終状態（Final answer）に到達するまでの唯一解を与える中間段階以降はすべて数独解なのだから。

Ver1では問題を matrix のelement　として module の中に書き込んだ面倒なものであった。そこで　Ver2では別の Sheet に　９×９ の問題を書き込む場所をいくつか作り、そこに書き込めるようにした。また、それに対応した Final Answer も別の Sheet に残す事に変更した。

数独の基本サーチは４つだけ。

数独の基本的な探索方法は４つだけです。それは　①ブロック、行、列に候補をひとつしか持たない数字をさがす。　②　候補をひとつしか持たないセルを探す。ことです。①が三つでそれぞれ B search, L search, C search と呼ぶことにします。また②は M search となずけました。

四つ合わせて BLCM search とよび、これが基本サーチです。初級問題は大体見落としさえしなければこれで解けます。例えば、「ポケット数独初級編」や「ナンプレ１６０問」（竹書房）は全問解けました。また、「ニコリ数独名品１００選」では７０問が解けます。数独の面白さはこれ以外の中級、上級の探索法を見つけることにあるようです。

私の作った最初のプログラムは B とM　サーチにだけ対応するもので、これでも「ナンプレ１６０問」では１４３問、、「ニコリ数独名品１００選」では５１問を解くことができました。　

sudoku_Ver1(May2006) が完成

２００６年５月６日（土）に記念すべき第１号の数独の解析ソフトが完成した。探索法は search_single というマクロで①ひとつしか数字の候補を持たないセルを探す。（A　判定）　② ブロックの中で一度しか現れない候補の数字を探す。（B判定）　の二つだけの方法を内臓する。それに ippatu という自動化のマクロをつくった。

問題を別に入力しておいて、ippatu を実行すると 全空白セルの候補がひとつになるまで mixy_part を繰り返す。mixy_part では候補を調べてその個数を count_kosuu で数えた後、search_single で候補を確定するという手順を繰り返す。

この程度のソフトで新聞や雑誌に掲載されているやさしい問題は大体解けることがわかった。いま改めて「ポケット数独初級編」（２００６年７月１７日に購入したもの）をA判定とB判定だけで解いてみると１０５問中１０４問が解ける。中でもB判定だけで８３問が解けることがわかった。７１番の一問だけがsearch_single では解けなかった。

この時点では、解き方の体系というか基本が全然わかっていなかったといえる。コンピュターでは解けてもまだ実際に自分で解いたことが無かったからだ。７１番の解けない理由が４つの基本サーチの内のひとつ L-search であると気づくのはもっと後のことで、興味の対象は西山先生も指摘されたコンピューターに適した解法に移っていった。

候補の一覧を作るマクロ

数独のプログラミングの最初は、空白セルに入る可能性のある数字の候補（candidate）の一覧表をつくることだった。いまでは candy_table とよび、洗練されたものになっているが、当初は mixy あるいは mixy_part と名付けたゴテゴテのマクロであった。

mixy のアルゴリズムは数独の表出数（以後 Givens とよぶ）以外の空白セル（Empty cell）を対象として、 check というマクロにて、そのセルと同じ列、同じ行、同じブロックにすでに Givens があるかどうかを順次1から９までチェックするものである。

とりわけ同じブロックにあるかどうかのチェックは checkmate というマクロを別につくり、Ｇｉｖｅｎｓ　があれば flag をたてて戻すようにした。この方法は後に、カラーナンプレとかジグザグナンプレとかに流用する場合このマクロだけを変更すれば容易に達成できた。

mixy_part は　group_search というマクロでブロックを限定して候補の数字を見つけだすものだ。mixy では最後に各空白セルの候補の数をカウントする count_kosuu というマクロがついている。候補の数がひとつだとそのセルの数字（digit と呼ぶ）が特定できる。これがプログラムでは一番簡単にわかる探索法（のちに M-search とよぶ）なのだが、実際には、探しにくいので中級あるいは上級にランクされている探索法である。

　

VBAは数独に適したプログラム環境

ナンバープレースのプログラミングにあたって、マイクロソフト社の Visual Basic for Application を使おう。EXCEL　はいまや最もポピュラーなソフト だし、数独には最も適したアプリケーションといえる。VBEを使えば簡単にプログラミングが可能である。

フォートランからはじまり、ベーシックを長くつかっていたが、ここ15年ばかりはVBAを使っている。容量も速さもパソコンの進化とともに全く不自由することはない状況だ。強いて不便さをあげるとすれば、Excel sheet の列の数の制限（IVまで）ぐらいだろうか。（Excel 2007　以降この制限もなくなった。）

数独のプログラム開発ではExcelの表計算がすごく役に立つ。だから、これから数独の要素の呼び方や利用形式もExcelに準じた名前で呼ぶことにする。例えば、マスはセル（cell）、ヨコ列、タテ列は行と列というように。セルの位置を表す方法をいろいろあるようだが、Matrix演算に準じることにする。つまり i 行目、 j 列目のセルの位置は ( i , j ) であらわす。

初めて数独に出会う。

三年前の連休の頃だった。正確には2006年5月4日に載った読売新聞の数独パズルを家内がやっているのを見かけた。ルールを教えてもらうと簡単にできるように見えた。こんなのはパソコンを使えば簡単に出来るとおもいそのアルゴリズムを考えはじめた。

もともとコンピューターでプログラミングするのが好きだった。これまで作ったいくつかのプログラム手法を思い出し、そのアルゴリズムを考えた。後で知ったことだが、西山豊先生が「数学を楽しむ」という記事を「理系の数学」に連載されていてその中の一章に「数独」について書かれている。先生の感想では「これはコンピューターに適したパズルである」ということだが、私も数独に対する最初の印象は同じものであった。多少でも数学を生業とし、プログラミングを自分では得意だと自負している人はコンピュータの持つ馬鹿正直な愚直さや偉大さを身をもって感じているからだろう。

その日はわずかに空白セルに入る候補をリストアップするマクロ（candy_table）を作成するにとどまった。

数林と呼ぼう。

Number　Place(俗称ナンプレ)はオイラー方陣に由来する。その後魔方陣から派生して、アメリカでNumber　Placeと呼ばれるパズルが誕生した。ニコリ社の鍛冶真起氏がこれに眼をつけ、「数独」と名付けて3年前にブレークした。

イギリスでも SUDOKU の名前で人気が高い。鍛冶氏の説明によれば「数独は独身に限る」というのから名付けたという。この謂れも語呂もあまり私にはなじめない。

私なら数林（スーリン）と呼びたい。語呂の上からスーリンというのなら美しい響きをもつ言葉とおもう。人形劇「三国志」に出てくる劉備の妻の名がたしかスーリン「淑玲」だったとおもう。意味の上からも｢数の林」というのでよろしいのでは？疎らな木を規則的に埋めることにより、美しい数の林にすることは環境上にもよい。

徒然なるままに

作：　松本亙平　

数独AI　アルゴリズム　　　　　　　　　　　　　　　　　



　つれづれなるままに、ひぐらしパソコンに向かい、新型インフルの恐怖におびえ、家の中にとじこもり、思い浮かぶよしなしごとを、あれやこれやとめぐらせて、古きこと新しきこと纏まりなきことかなしけり。



ふと思いつきしことあらば、むかし馴染んだ数独か、はたまたナンバープレースかと古い本をば取り出して、物思いにふけることあわれなり。