« 豆カンナで悩む | トップページ | 粉末茶で悩む »

2012年8月24日 (金)

数独の問題作りに悩む

Sudokufail数独の問題を解くプログラムはそれほど難しくなかったが、問題を作るのはむつかしそうだ。

数独の問題を作るのに、端から順番にルールに合致できる数字を乱数で選びながら埋めて行ったりしてみたのだが、そうやってみるとおしまいの方になってつじつまを合わせられなくなり、ルールに合う数字を入れられなくなる、という事態になってしまう。

左に掲げたのがその例で、左上から順番に数値を決めていくのだが、途中でルールに合う数字を見つけられなくなる。例では「#」で表されているのがその状況で、右下へ行くに従って苦しくなってきているのが分かると思う。

まぁ力技としては、そんな方法であってもルールに合った(以降、「正則である」ということにする)組み合わせだけを取り出すこともできるが、どれだけ時間がかかるかわからないし、全ての正則な組み合わせを網羅できるかどうかもわからない。試しにやってみたら10000回の試行で30個ほどしか満足な問題が作れないので、そんなのやってられないな、と。

なので、ある正則な組み合わせを変形させていくことを考える。例えば正則な組み合わせの縦の列を別の列と入れ替えると、縦と横のルールは保つことができる。でもそれだと3×3のボックスのルールを保つことができない。

Sudokugenなので、この図に示すように例えば上段の3つの3×3ボックス間で縦3個の数字を他のボックスの同じ位置にある縦3個と入れ替える。図中では赤、緑、青で示した3個ずつの数字を同じ色同士で入れ替えることになる。

赤で示された3つの3数字を並べ替える組み合わせは6通りなので、上段で三色のそれぞれを入れ替える組み合わせは216通りになる。中段でも下段でも同様に216通りのバリエーションを作ることができ、このように短い縦の列の入れ替えで216の3乗:10,077,696通りの組み合わせを作ることができる。

さらに同様の操作を短い横の行に対しても行うことができるので、組み合わせは更に大きくなって、216の6乗:101,559,956,668,416通りになるが、とりあえず割り当ててある1~9の数字の割り当ては自由に変えられる(例えば4を2に、2を4にとか)ので、9の階乗:362,880をさらに掛けないといけない。すると36,854,077,075,834,798,080
とかいう、なんと読んでいいのやらわからない数字になってしまう。

ただし、問題の盤面を回転させたり、裏返したりしたものを同じと数えないという事にすると、8で割って4,606,759,634,479,349,760ということになる。

一方Wikiでは9×9の数独に関して約54億通りという計算結果が出ているのだそうで(コンピュータで数え上げたらしい)、上記の値とは大きな隔たりがある。数字を3つずつ入れ替えるだけで全てのパターンを生成できるのかどうか、今ひとつ確信が持てないが、まぁそんなもんじゃないかな。

だいたい考えて見ると、数字の配列というのは問題の難易度にそれほど関係してこないと思うのだ。問題の難易度というのは、問題を解き始める時点で自明な解がどれくらい露出しているか、ということが問題になるのだろう。

自明な解というのは、数独を解くプログラムの時に示した、赤く表示されるパターンのことを言っている。例に引いたDELTAでもらった問題では、最初に私が取り付いたマスが自明な解を持っていなかったのだったが、問題を見てぱっと自明解を見つけることが出来れば、その問題はとっつきやすい問題ということになるだろう。

問題の面白さ、ということを考えるとするならば、問題を解き進むに連れて自明解の数がどんなふうに変化するか、ということが大きなファクターになってくるのだと思う。

Sudokuans

ここで、左端のパターンは最初から自明解がたくさん露出していて、解き進むに従って自明解が減っていくというもの。とっつきやすいから初心者向けといえるのではないだろうか。

真ん中のパターンは最初の自明解が少なく、解き進むに従って自明解がどんどん増えていくという、上級者向けのパターン。右端は上級者向けと同じように解き進むについて自明解が増えてくるが、また減ってきてもう一度頭をひねることになる、というパターン。

だから、数字の並びは正則でありさえすればどうでもいいので、その数字たちのどの部分を隠すか、というのが考えどころ、ということなんだと思う。じゃぁそれをどうすればいいのか?というのは、まだ考え中。

翌日追記:

一般に流布されている問題を解かせてみたら、一般の問題ってのは「自明な解」のマスが最初から無い、というのが多いようで。私がたまたま入手したDELTAの数独が特別に簡単なもんだったということなのか。そりゃ解くプログラムも簡単なはずだわ。

自明な解が予め存在しないような問題だと、脈のありそうなマスの関連性をたどって試行錯誤しないといけない。それならよくあるゲーム解法のプログラミングになってしまうんだろうなぁ。それはなんだかあんまり面白くないなぁ。

|

« 豆カンナで悩む | トップページ | 粉末茶で悩む »

プログラミング」カテゴリの記事

コメント

>その数字たちのどの部分を隠すか、というのが考えどころ、ということなんだと思う。

そんな様な事を,ゲーム業界では「ゲームバランス」などといいますね。

投稿: ををつか(をたくな講師) | 2012年8月25日 (土) 07時01分

出来上がったゲームを評価する言葉としての「ゲームバランス」は、この投稿で扱っている事項を表すにはちょっと荒すぎると思います。

私の誤解もあって、ゲームのストーリーをより深く理解するにつれてストーリーのバリエーションにも、より幅が出せるようになってきたと思います。

自明な解をたどっていけるステージと、ヒューリスティックな手法が必要なステージを組み合わせると、難しさをいろいろな形にデザインできますね。

投稿: Picks Clicks | 2012年8月25日 (土) 11時29分

コメントを書く



(ウェブ上には掲載しません)




« 豆カンナで悩む | トップページ | 粉末茶で悩む »