(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）用にも容易に変更可能です。また変形ナンプレ
（対角線ナンプレ、幾何学ナンプレ、合体ナンプレなど）にも簡単に改良できます。