「数独」の「最小問題」
さきほど、はてなリサーチ、とかいうサービスのアイデアを出したのは、僕自身、そのサービスで解決したい問題を今ひとつ思いだしたから。
それは、最近微妙に話題になっている「数独*1」というパズルに関する問題。数独がどういうパズルなのか、詳細はキーワードリンクを辿ってもらうとして、簡単にいうと「魔法陣」をルールにしたがって埋めていくもの。最初はいくつかが空欄になった魔法陣が問題として提示されて、空欄になっているところををルールに反しないように数字で埋めていく。そんなパズル。
そこで僕が気になっている問題は、最初に提示する魔法陣の中で、あらかじめ埋めてある数字の数を極力すくなくしようとすると、何個まで少なくできるのか？という問題。最初に埋まっている数字がその後の数字の埋め方を決めるので、最初に埋まっている数字が多ければ多いほどパズルとしては簡単になるし、少なければ少ないほどパズルとしては難しくなる。さらに少ないと重解がでやすくなるので、問題を作ることが難しくなる。いいかえると、「問題作成の難しさに負けずに、ヒントとなる数字の数を一番少なくするとそれは何個になるのか？」、「解く人にとって一番難しい(はずの)、数字が最小個数しかない問題はいったいどんな問題か？」というもの。
僕は、学生の時に、http://www2.tokai.or.jp/deepgreen/shortnotes/numberplace/ のサイトでこの問題を知って、たまーに思い出しては何回か考えてはみたりはしてるのだけど、さっぱり解けない。アプローチさえよくわからない。ちなみに、リンク先のサイトでは、確認された問題では19個が最小、と書かれていますが、その後、17個の問題が存在した、という情報を見ました。僕自身が確認している最小はこの17個です。
どなたかイッショに考えませんカ？あるいは答えしってる人がいたら教えてください。コメント求む。あと、多分、この問題の考察の副産物として、全てのありうる数独の問題の自動生成手法とかできる気がします。
