gooブログはじめました!

写真付きで日記や趣味を書くならgooブログ

ナンプレの難問を求めて

2014-03-25 13:38:14 | ブログ

 ナンプレ(数独)を解くときに使えるアルゴリズムを追求してきた。ナンプレは、3×3行列、1×9の行および1×9の列の各々に、1~9の異なる数字が埋まったとき、パズルが完成する。まず準備段階として、問題の行列欄の各空欄に可能な数字列の候補を書き込んでいく。これら候補は、1~9の数字全体の部分集合になっている。

 これまでに分かったアルゴリズムを以下にまとめる。3×3行列、1×9の行および1×9の列の各々について、次のルールが適用される。

 (1)すべての部分集合の合併から外れた孤立した数字をもつ欄があれば、その欄はその数字に確定する。このルールにより、準備段階で、一意に数字が決まるような欄が生じることもある。

 (2)(1,4);(1,4)のように2つの要素だけが残った部分集合のペアに注目する。この2つの欄には、いずれにしても背反的に1か4しか入らないから、同3×3行列、同一行または同一列に存在する他の部分集合に含まれる1と4を排除することができ、他の部分集合中のこれらの数字を消し込むことができる。

 (3)(4,5,7);(4,5,7);(4,5)のように、3つの要素が残った部分集合のペアと、そのうちの2つの要素だけを共通の要素とする1つの部分集合とから成る3つの部分集合の組に注目する。もし、(4,5,7);(4,5,7)のペアの数字7が消し込まれるようなことがあると、(4,5)の部分集合が3個できることになり、明らかに矛盾が生じる。従って、(4,5,7)のペアのうちのいずれか一方が数字7でなければならない。この事実は、同3×3行列、同一行または同一列に存在する他の部分集合に含まれる7を排除できることを意味する。同様のロジックによって、(4,5,7);(4,5);(4,5)のような部分集合の組が残ったとき、(4,5,7)は数字7が確定するから、他の部分集合に含まれる7を排除することができる。

 (4)まれにしか生じないが、(4,5,7);(4,5,7);(4,5,7)のように3つの要素が残った同一部分集合のトリオについても、同3×3行列、同一行または同一列に存在する他の部分集合に含まれるこれらの数字を排除することができる。

 上記のアルゴリズムを適用すれば、ほとんどのナンプレの問題について、これらアルゴリズムだけで完結できることが分かった。上記アルゴリズムだけでは完結しない問題は、わずか2件であった。

 上記のアルゴリズムだけでは完結しない問題に対しては、チェインの規則を適用する。チェインの規則とは、例えば、数字の1を候補として含む1つの欄が仮に1とすれば、同じ3×3行列、同一行および同一列の1を含む部分集合は、(not1とする)でなければならない、というものである。つまり、最初の1と他のはチェインをつくり、このチェインはその他の3×3行列、他の行および他の列にも波及し、全体としてチェインの体系をつくる。もし、このチェインの規則に反する矛盾するような1との割当てを仮定したとすれば、その仮定は誤りであるから、矛盾が生じないような一意の割当てから1とが確定することがある。

 1との割当てを行ってチェインの体系をつくり、矛盾のない体系ができた場合、1をに、を1に反転させても矛盾が生じるとは限らない。しかし、未解決の1とについて、チェインの体系を一巡するように1とを選んで割当てとその反転を矛盾なく行うことができたとき、このチェインとつながっているにもかかわらず、このような操作と無関係にいくつかのが成立する欄が生じることがある。このような欄は、反転という変換操作に対して不動点を構成しているから、が確定する欄と考えてよく、以下、上記アルゴリズムの適用につなげることができる。

 こう見てくると、さらなるアルゴリズムの追求には興味が薄れていき、むしろアルゴリズムを適用できず、チェインの規則に基づいたロジックについての興味が深まっていく(上記以外のタイプのロジックが可能だろうか)。つまり、ナンプレの他の難問を求めたくなる。

 新たにナンプレの問題をつくるのは、難しそうなので、既存の問題を改造して新しい問題をつくれないか、検討することにした。

 例えば、朝日新聞の土曜版に載った次の問題を例題として挙げることにします。