無料ブログはココログ

おすすめ


« 第4問 | トップページ | 第5問 »

2006年11月28日 (火)

Unavoidable Set

ナンプレのルールの一つに複数解を持たないというものがあります。

これはルールでは無いという人もいますが、ミシチャンはルールだと思っています。なぜなら、

Unavoこのルールをなくした途端、ナンプレは何でもありになってしまうからです。複数解をOKにすると、例えば表出数字が0個の問題も作れます。

この複数解を持たないというルールから問題作成の際に制限がでてきます。一つは表出文字の種類です。9x9のナンプレの場合は表出数字は8種類以上必ず必要です。(バラエティナンプレは別)

その他の制限の一つにUnavoidable Setというものがあります。図は第1問の正解図です。ピンクの4マスに注目すると、この4マスは4と3のununique rectangleの配置になっています。つまりこの正解配置を使って問題をつくる場合、この4マスのうちの1つを必ずヒントとして表出しなければいけないということになります。

Unavoidable Setはもっと複雑な構成も取ることが可能です。

リンク先はこのUnavoidable Set(US)を利用して最小表出ヒント数を探索するプログラムです。例えばお互いに重なり合わないUSが17個ある正解配置図からはヒント数16の問題は作成不可能です。

逆にUSが16個の正解配置図ではそれぞれのUSから一つずつヒント数字を選んで、その問題が唯一解を持つかどうかを調べて行くことで、表出文字16個の問題が存在するか否かを調べる事ができます。なおかつ、この方法は場当たり的に調べていく手法に比較すればはるかに短い時間でチェック可能です。

世の中には頭のいい人がいるもんだなーとつくづく思います。

Sudoku Checker and the Minimum Number of Clues Problem

« 第4問 | トップページ | 第5問 »

コメント

コメントを書く

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

トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/183459/4348515

この記事へのトラックバック一覧です: Unavoidable Set:

« 第4問 | トップページ | 第5問 »