図1 数独問題例
数独(別名：ナンバープレイス、ナンプレ、etc…)とはペンシルパズルと呼ばれるパズルゲームの一種である。この数独はパズル制作会社「ニコリ」が商標登録したもので、海外でもsudokuなどと呼ばれ、広く親しまれている。もともとの由来は「数字は独身に限る」。というところから来ている。
数独の原型は18世紀にスイスの数学者レオンハルト・オイラーが考案した、ラテン方陣あるいはオイラー方陣と呼ばれるものである。これに新たな制限を付け加えて生まれたのが数独である。日本で初めて紹介されたのは1980年頃だが、近年再燃し、一躍大ブームとなったのでこのパズルを知っている、もしくは解いたことがあるという方も多いだろう。
下図は基本的な数独の問題例となっている。この空欄を全て埋めることができればゲームクリアとなる。
図1 数独問題例
詳しくは次項で説明するが、行、列、３×３のブロックに注目したときそれぞれ１〜９の数字が被らないように埋められていればいい。
また、問題を解く上では気にすることはないが、穴に埋めることができる数字は１つでなくてはならず、そうでないと解が複数存在することになってしまい、問題としては不適切となる。本研究では問題の生成が目標となるため、この点はまず念頭に置いておかねばならないだろう。
本研究ではこの数独の問題を自動生成するプログラムを開発することを目標とし、研究開発を行った。
数独の基本は、３×３のブロックに区切られた９×９の正方形の枠内にそれぞれ１〜９までの数字を空欄に埋めていく。
下図左は基本的な数独問題例である。図の左に対し、右のように全ての空欄を条件に沿うよう埋めることができればゲームクリアとなる。条件は行、列、３×３のブロックに注目したときそれぞれ１〜９の数字が被らないように埋めていけばいい。見事全ての空欄を埋めることが出来ればゲームクリアとなる。
図2 数独問題
基本的な問題の解き方について説明する。
初めに特定の数字に着目して解く方法を説明する。下図の左上AXの部分に注目してほしい。
図3 基本的な問題の解き方(数字)
図で左上の３×３の四角AXの中で１が入る場所を考える。左上の四角のなかにはまだ１が使われていないので９マスの中のどこかに１が入るわけだが、横を見るとBX２行目とBX３行目に１が使われている。そのためAXの２，３行目には１を入れる事ができない。同様に下を見るとAYの２列目、AZの３列目にも１が使われているため、１が入れられるのは左上のマスのみとなる。従ってAXは左上のマス以外には１を入れることができない。
次に特定の場所に注目して解いてみる。下図のAX１行、１列目に入る数字を考える。すると使われていない数字１，７，８，９のいずれかが入ることがわかる。しかし、右のCXを見てみると、１が既に使われているため、CX１行目の右の３つの空欄には１を入れることができない。従ってAXの左上の空欄には１が入る。
図4 基本的な問題の解き方(場所)
先に説明した２つの手法を用いることで初級レベルの問題ならば十分解くことができる。しかし、中級、上級レベルの難しい問題となると、この２つだけでは少々心許無い。高難易度問題を解くための手法は数多く存在する。ここでは１例を紹介する。
図5 問題の解き方(応用編)
図でAXの左下のマスに入る候補はXの下の行から３、５、６以外、Aの右の列から７、８、９以外なので１、２、４のいずれかとなる。しかし、Aの上の行に注目すると、３〜９はすでに使われているので、AXの上の行には必ず１か２が入る。そのためAXの左下のマスには１と２は使用することができない。よってのこりの４が入ることがわかる。
このように解を求める際の推理のしかたとしては様々な方法があり、これらを組み合わせて各マスの数字を決定していく。
この組み合わせの数が多ければ高度な推理であり、少なければ容易となる。
数独問題の難易度はある程度の経験者の平均回答時間など、あくまでも人間の主観によるものであるが、解く上で必要となる推理の深さや、埋めなければならないマスの個数などにより決められると考えられる。
前章により、人間が数独を解く場合、深い推理が必要となることがあり、パズルとして楽しめるものであることを示した。しかし、コンピュータによる解法はこれとは異なる。
ここで、check関数(ソース参照)を説明する。
このプログラムは左上から順に数をいれていくだけのバックトラックのアルゴリズムを使用している。数をいれてはcanBePlaced関数でその数を入れたことが正当かどうかをチェックする。この関数は単純に行、列、３×３のマスにダブりがないかをチェックするだけの関数である。
通常のパズルでは単純な全探索を行うと組み合わせ論的爆発を伴うが、この数独の場合、ゲームの制約が効率的に働いてゲーム木が先細りになるようで、このような単純な全探索で十分効率的解を得ることができる。
基本方針としては全てのマスが埋まった完成形を作成し、そこに穴を開けていくことで問題を作成する事を考えた。任意に選択したマスに仮に穴を開け、そこに入る数字が１つのみならば問題として成立している。そしてそれを繰り返すことで問題を作成した。
この穴を開けるプログラムはmaker1関数(ソース参照)となる。これは完全にランダム順に穴を開けていくプログラムで、まず、ランダムに指定した場所を仮に0で置き換える。そこに１〜９の数字を入れていき、canBePlaced関数を用いてそこに入れることができるかを調べ、その結果そこに入る数字が元々入っていた数字のみならばそこは０で置き換えたままで、そうでない場合は元の数字に戻す。これを全ての穴に対し試みる。
その他の関数は次のことを行う。
問題を作成するうえで、当然考慮しなくてはならないのが、問題の難易度である。しかし、ここでネックとなるのが、数独の難易度は必ずしも空欄の数ではないという事である。もちろん極端に穴の数が違う場合などには難易度に差がでる傾向はあるが、少数の差では必ずしも穴が多いほうが難しいとは限らない。これは数独をはじめとする一般的なパズルゲームの難易度は、その問題を解くために用いる手法の複雑さによるためである。
手作業で問題を作成する場合には、比較的容易に問題を難しくすることもできるのだが、今回はプログラムで問題を自動生成するため、プログラムでも簡単に問題を難しくすることができる方法がないか模索した。
作成したプログラムに難易度を与えるための手段としてはおおまかに以下の３つの手法が考えられる
今回はこの中の(2)穴を開ける順序により、難易度に変化を与えることができないかを試みた。
これを行うのがmaker2関数(ソース参照)となる。これは穴を開ける順所を完全に指定し、真ん中→上→左→右→下→四隅の順に穴を開けるようにしたもので、81個の要素をもつ配列を全て手入力で入力することで順番の指定を行った。その他の動作はランダム順と全く同じで、canBePlacedで穴を空けられるなら空けるということを全ての穴に対し行う。
その結果、次項で紹介する通り、一定の難易度の付与することができた。
作成したプログラムにより、以下の２つの問題を生成し、難易度の評価を行った。
なお、これらの生成時間は
CPU:Intel Core i7 980(3.33Ghz)
OS: Windows7 Professional 64bit
使用ソフト：Visual Studio 2010 Professional
環境において、ランダム生成が410ms、順番指定が400msほどであった。
図6 作成した問題
図6の左はmaker1を使用して作成した問題で、完全にランダム順で穴を開けていったものとなる。それに対し右は、maker2を使用して作成したもので、穴を開ける順所を指定し、中央→上→左→右→下→四隅の順に穴を開けるようにした。それをランダム、順番指定共に各1000問ずつ問題を生成し、その中で最も穴の数が多かったものをピックアップしたのが上図となる。
この問題を実際に研究室の数名の有志の方に解いて頂いたところ、右の問題のほうが明らかに難易度が高いと感じる人のほうが多く、順序を指定することで問題にある程度の難易度を持たせることができることがわかった。
ところが、この問題を解くために用いる手法を調べてみたところ、実は両者とも前述の基本的な解き方二つだけで全ての穴を埋める事ができた。一方、最初に埋まっている数字だけで埋められる箇所を数えたところ、ランダムが８個あるのに対し、順番指定のほうは４個だった。更に、この穴を埋めた状態から埋められる箇所を数える…という動作を全てのマスが埋まるまで行ったところ、ランダムが８→７→１０→８→７→５→２→２、順番指定が４→８→１１→１０→１０→３→４→２でクリアまでに必要な回数は共に８回となり、両者にあまり差異は発生しなかった。
以上のことから両者に難易度の差が感じられたのは、初期状態で埋められる箇所が少なかったことが原因の一つとしては考えられるが、そのほかにも難易度を難しくしている要因があるように思われる。これは今後の課題としたい。
本研究では数独問題を自動で簡単に生成するプログラムを開発することを目標として研究を行った。結果、簡単な問題生成プログラムの開発並びに、生成の際に難易度を付与することに成功した。
今後の展望としては、他に難易度を変化させる手法が無いか、また、作成した問題の難易度を客観的に評価する方法がないかを模索していきたい。