ナンプレについて卒業論文を書く

　長い間、ナンプレ（数独）の問題を解いてきた。

　その間、常に念頭にあったのは、３×３ブロック、同一行または同一列に適用するアルゴリズムだけですべてのパズルが完結するのか、あるいは問題によっては二者択一の選択を介して試行錯誤するプロセスが必要になるのか、という問題である。

　そのため、特に難問とされている問題を選んで取り組んできたが、それほど多くの問題を試す機会もなかったので、この懸案が容易に解決するようにも思えなかった。

　最近、参考文献のようなナンプレの「超難問」と称する問題集があることを知ったので、そのうちの一冊を購入し、その中の１００問をやってみた。

　１００問の挑戦が終了した時点では、アルゴリズムだけで完結したものが８５件、途中で二者択一の選択を一回だけ行い、失敗した場合にはもう一方の選択肢を介して完結したものが１５件あった。

　その途中経過をみると、６２件目が最後の試行錯誤となり、その後の問題については、アルゴリズムだけで完結したので、試行錯誤した問題については、アルゴリズムの適用が不完全であったと考えた。

　そこで、試行錯誤の１５件をもう一度やってみた。その結果、１００問すべてがアルゴリズムだけで完結できることを知った。

　この結果から、ナンプレはアルゴリズムの適用だけで１００％完結できるのではないかと思うようになった。

　ここで、適用したアルゴリズムについて記しておきたい。

　まず準備段階として、問題の行列欄を拡大するために別の用紙にパズルを転写した後、各空欄に可能な数字列の候補を書き込んでいく。これら候補は、１～９の数字全体の部分集合になっている。

　適用したアルゴリズムは、次の通りである。

　（１）３×３ブロック、同一行または同一列の各々について、すべての部分集合の合併から外れた孤立した数字をもつ欄があれば、その欄はその数字に確定する。これによって、関連する各欄の部分集合からその確定した数字を消し込むことができる。
　（２）いずれかの３×３ブロック、同一行または同一列に、（１，４）；（１，４）のように２つの要素だけが残った部分集合のペアに注目する。この２つの欄には、いずれにしても背反的に１か４しか入らないから、同３×３ブロック、同一行または同一列に存在する他の部分集合に含まれる１と４を排除することができる。
　（３）３×３ブロック内の同一行または同一列だけに、（３，４）；（１，３，７）のように同一数字３が並んでいる場合には、いずれかの欄が３でなければならないから、問題全体の同一行または同一列中の３を排除できる。
　（４）３×３ブロックなどに、（４，７，８）；（４，７，８）；（４，８）のような組があるときは、（４，７，８）ペアの１つが７でないと矛盾するから、同３×３ブロック、同一行または同一列中の他の７を排除できる。また、（２）により、他の４と８も排除できる。同様に、（４，７，８）；（７，８）；（４，７）の組で、（４，７，８）；（７，８）のいずれかが８でないと矛盾するので、他の８を排除できる。また、いずれが８であっても、４と７はこの組の中にあるので、他の４と７を排除できる。（７，８）の代わりに（４，８）があっても、同様である。
　（５）３×３ブロックなどに、（３，５，８）；（３，５，８）；（４，５，８）；（４，５，８）の組があるときには、（３，５，８）ペアのいずれかが３でなければ矛盾が生じる。同様に、（４，５，８）ペアのいずれかが４でなければ矛盾が生じる。これから、関連する欄の３と４を排除できる。また、（２）により、他の５と８も排除できる。
　（６）３×３ブロック内の同行または同列に同じ数字が並び、その行または列を含む同一行または同一列に同数字がないとき、その行または列で同数字が確定するから、同３×３ブロック内の他の同数字を排除できる。
　（７）まれにしか生じないが、（４，５，７）；（４，５，７）；（４，５，７）のように３つの要素が残った同一部分集合のトリオについても、同３×３ブロックなどに存在する他の部分集合に含まれるこれらの数字を排除できる。同様に、（４，５，７，８）；（４，５，７）；（４，５，７，８）；（４，５，７）のような（４，５，７，８）ペアの１つが８でなければならないことは明白である。

　次に、以上の結果の真偽を確かめるために、過去に遭遇した他の難問の記録をもう一度検討し直してみることにした。

　その結果、多くの問題を収録した問題集には、アルゴリズム偏向と言えるような偏りがあることを知った。それとともに、局所的なアルゴリズムの適用には限界があることも分かった。

　過去の難問の中で、局所的なアルゴリズムの適用だけではパズルが完結しなかったものが９件あった。

　そのうちの１件は、２０１３年８月１日付のブログで紹介した問題である。この問題に関しては、数字の１を含む部分集合がチェインを介して全体への波及効果が大きいことに注目し、１を含む部分集合のマップをつくり、二者択一の一方の１についてチェインの体系をたどると、１と１’（ｎｏｔ　１）との組合せに矛盾が生じる。これから、選択した１は１’であることが導かれ、パズルが完結する。

　他の１件も二者択一であって波及効果の大きい数字４の部分集合を基点としてチェインの体系をつくるものである。ここでは、二者択一のいずれの４を基点としてもチェインの全体は矛盾なくつながる。しかし、両者の試みから複数個の４’が４の不動点となる。これから、これらの４’が確定する。４自身が不動点として確定する場合もあるだろう。

　残りの７件については、チェイン体系を利用することによって数字を確定させることが難しいので、波及効果の大きそうな数字を選び、二者択一の試行錯誤をして、成功か失敗かの結果を得た。この種の難問については、二者択一の選択と試行錯誤が最良の方法のようにみえる。もちろん、試行の途中でチェイン体系の利用に切り替えることもあり得る。

　ナンプレの問題で提示される数字の配列パターンには、局所的なアルゴリズムの適用が可能なものと、そうでなく、二者択一の試行錯誤が必要なものがあることが分かった。数字パターンのゆらぎの状態によって、いずれかのコースをたどることになるのであろう。

　参考文献
　川崎光徳著「超難問　ナンプレ　Ｅｍｐｅｒｏｒ１４５選」（永岡書店）