数独(スドク)の疑問

 

スドクを最近まで知らなかった人は、私以外にはいないかもしれないが、あるきっかけで最近その解を試みることになった。例題は図1に示してある。答えも見つけるためには、空いている枡に、ルールに従って1から9までもどれかの数字をいてれゆく。ルールに違反しないで全部の枡にに数字をいれたら答えである。枡は9X9の碁盤になっている。これを3X3の枡が3X3あると見ることができる。ルールとは、おのおのの横の行とおのおのの縦の列が1−9の数字が(重複なしに)入っており、また9個ある3X3の枡も1−9の数字が(重複なしに)入っていることである。

 

        図1

答えを見つけるためには、まずひとつの空白に注目し、ルールに違反しない数を1−9の中から選び出す。そのような数が一個なら、それを書き込めばよいが、1つ以上あるときには、すぐには決まらない。候補として記録しておく。このようにして、空白の各枡の候補を全部書き出す。もし、候補が一個しかなくすでに書き込んだ場合は、ほかの位置の候補が影響を受け、複数あった候補が一個にへるばあいがある。そのときは、その唯一の候補をその枡の答として書きこむ。

 

作業は簡単であるが、非常に手間がかかる。そのため、私は中途で白旗をあげ、そのかわりコンピュータプログラムを作ることにした。プログラムはほぼ1日で完成し、あっという間に答えを出してくれる。当地の新聞にも毎日スドクの問題はのっているので、数個の答えをだして、正解とくらべたが、みな正解であった。

 

しかし答えの唯一性の疑問が残る。つまり、出題者が、答えの唯一性をどうやってチェックしているかである。

 

答えの唯一でない問題が存在することは容易に証明できる。極端な例であるが、たとえば図に示したような9X9枡の問題で、全部が空白であれば、9X9でこれまでに世界中で出題されたすべてのスドク問題の答えが、答えである。

 

2個目の例とし次のようなのがある。9X9よりも複雑なもので、9X9を5個組み合わせた図2のようなのがある。このなかの9X9の部分だけ取り出して、私のプログラムで答えを見つけようをすると、かなり多数の答えがみつかる。

           図2

 

3個めの例として、図1の問題を少し変更して、幾つかの数字の入っているところを空白にしてゆくと、必ず一個以上の答えがみつかるようになる。

 

ところが、ここで一つの困難に突き当たる。それは。複数の答えがあることは分かっても、プログラムで可能な答をすべて見つけることが困難であるためである。これが出来ないと、答えが一個見つかっても、それの唯一性が証明できない。

 

困難の理由を少しくわしく説明しよう。スドクの問題の空白に入れてもよい候補数を調べることはすでに説明したが、おのおのの空白に対して一個から数個、あるいは5〜6個みつかる。一個の候補数しかない空白があれば、空白を埋めてゆくのはその空白から始めると答えがみつけやすい。一つ入れるとまた次に一個の候補数しかない空白が見つかり、たいてい連鎖的に空白がうまってゆく。しかし一個しか候補数のない枡が皆無の場合は、二個の空白に候補数を入れて見なければならない。しかしその組み合わせは、空白の数がNこあればNx(N−1)あり、そのすべてをテストすることになる。そのテスト中に空白が一個の場合がでてくれば、これは突破口で、たいていは答えがみつかる。

 

もしNx(N−1)個の組み合わせをテストしても答えが見つからない場合は、つぎは3個の空白の組み合わせをテストしなければならない。その組み合わせはNx(N−1)x(N−2)個。もしN=50とすれば、くみあわせは50x49x48=117600個、その回数だけプログラムを走らせなければならない。このあたりまではまだ可能である。しかし、一個の答えを見つければよいのではなく、すべての可能な答えを見つけるとすれば、仮に各空白がK個の候補数を持つとして、テストしなければ成らない組み合わせはNx(N−1)x(N−2)x..(N−K+1)ことなる。これは莫大な数で、しかもおのおのの組み合わせに答えがあるのかないのか、また答えまだ見つからなくても、そこまでに矛盾を起こしていないかどうかをすべて記録しておかなければならない。この仕事は、コンピューターでなら不可能ではないが、かなりのプログラムの労力を要する。

 

これが私の職業ならいくら時間をかけてもやり尽くしたであろうが、遊びであり他にもやらなければならないことがあるので、ここで中断した。

 

すでに記した9x9を5個組み合わせたスドクの答えは、私のプログラムの機能を拡張することによって、見つかるだろうと考えている。単独の9x9の場合と同じ原理ではあるが、形状が異なるのでプログラムをかなり書き換えないとならない。しかし、この次に暇がで来るときまで延期することにした。

 

5−26−2015

中村省一郎