ナンプレ(数独)問題作成プログラム　その１

数独の難易度を決めるのは難易度が高い

少し数独をやると、易しい問題では物足りなくなって難しい問題を解きたくなる。また、プログラマーの場合は、自分が解くのではなく、数独を解くプログラムを作りたくなってくる。そうすると、数独の解き方のページを探して解き方の勉強をする訳だ。そして、Locked Candidate や Naked Pair(二国同盟) などの解説にたどり着く。
そうして、さあ解き方が分かったぞ、解いてみようと思って、激辛数独13などを買って解いてみるわけである。

そうすると、アレ？　あんまり辛くないぞ*1、なんて思うわけだ。数独のパズルプログラムでも、Easy, Normal, Hard, Insane などという分類があったりするが、これがInsane(無茶)か？　と思ったりもする。まあ、ペンシルマークが使えないような数独アプリでは仕方がないにしても、もう少し難しい問題はないだろうか？

そうは言っても、数独の愛好家のレベルは幅が広いのであるから、あまり難しいのを易しいというと、初心者がびっくりしてしまう。カレーだって、こんなの辛くないという人がいるからと言ってそこそこ辛いカレーを中辛などと表示したら、悲惨な目に会うひとが出てくるだろう。だから、激辛数独は激辛でいいのだ。

じゃあ、難しい問題を欲している人にはどうやって難しい問題だということを伝えたら良いのか？　それはやはりどの解法を必要とするかを示すしかない。しかし、これも問題があって、複数の解法が使用できる場合がある。まあ、そこはあまり気にしないことにする。例えば、Naked Pair (二国同盟)はX-Wing(四角の対角)よりも一般には簡単である。ところが、プログラムで解くときには、Naked Pair(二国同盟)もNaked Triple(三国同盟)も(Hidden Pair)裏二国同盟も同じアルゴリズムで解け、X-Wing, Sword Fish などの系統はまた一つのアルゴリズムで解けるのである。そうすると、裏三国同盟とX-Wing はどちらが難しいかというと、これがなんとも言えないのだ。同盟系統は、並んでいるとすぐに分かるが、離れていると分かりにくいということもあり難易度の設定は本当に難しい。

ナンプレ(数独)の問題を作るのは、問題を解くより難しい

数独 - Wikipediaによると、

世界的な流行は、1997年に59歳のニュージーランド人ウェイン・グールド（英語版））が日本の書店で数独の本を手にとったことに始まる。グールドは6年後、数独をコンピュータで自動生成するプログラムを作る事に成功。

ということだが、このときのアルゴリズムはdigging holes と言われるものであったようだ。そんなに難しいパズルは出来ない。（出来るとしても非常に確率が低いはずである）

実は難しいパズルを生成するアプリは既に存在していたのだが、そんなこととは知らずに作り始めてしまったのである。まあ、車輪の再発見なんて、プログラマーにはよくあることなのである。もっとも、存在していても、公開されていないようなのでここのブログで取り上げる価値はあるだろう。

方針を決める

難易度の定義は難しいと書いた。既存の難易度には最初に数字が見えている場所の数が少ない程難しいという考えがあったようだ。ヒントになる情報が少なければ、それだけ難しいという考えである。しかし、何問も解いた結果、そうとは限らないという結論を得た。なので、そこは気にしないことにする。

対称性は少し崩れてもよいことにする。一般にナンプレの問題は点対称に作られている。これは見た目の美しさを求めたものである。しかし、すこし崩れてもいいことにする。自然界には美しい対称性があふれているというが、実際に自然界にある対称性は厳密な対称性ばかりではなく、対称性が崩れていることも多いのである。それでも私たちは美しいと感じる。それが、わびさびというものである。

問題作成プログラムとパズル出題プログラムを分ける。問題作成と、出題は別のことだから、プログラム作成の原則から言えば、結合度を低くする必要がある。別の実行ファイルというのが最も結合度が低いのである*2。というように最初に考えたわけではなく、最初は愚かにも、パズル出題プログラムの別スレッドで問題を作成すればいいと考えていたのである。しかし、実際には別スレッド実行は望ましくない。それは、無駄にＣＰＵを使うだけである。パズル利用者それぞれのパソコンで問題作成プログラムが動作する必要はまったくない。エネルギーの無駄である。それに、タブレットにしろスマホにしろ、バッテリ消費は重要である。うちのMac Book もちょっと重い処理を走らせるとファン音がうるさくなる。というわけで、問題作成は別プログラムが正解なのである。そうなると、問題作成に数時間、数十時間かけても構わないということになる。これも実は望ましい性質である。なぜならば、問題を売るという可能性が出てくるからだ。こういうことを、失敗をしてから気づくのではなく、最初から考えたかのように書くと頭がいいアピールが出来る。ブログを書くならぜひそうするべきだ。