二分決定グラフによる全解表現に基づく数独問題の難易度の定義と問題自動生成法

点击翻译按钮获取中文摘要

本年度は(1)難易度付けの改良,(2)16ヒント問題の探索,(3)本質的に異なる解空間の番号付,に取り組んだ.得られた成果は下記の通りである.(1)解探索ヒューリスティクスの改良,各ヒューリスティクスの難易度重みの改良,及び,バックトラック型解法しかない場合の難易度の改良により,難易度のより適切な付与が可能となった.(2)ある盤目に数を置くと,それ以降いかなる数を置いても一意解が存在しない最大の配置を「一意解制約」と名づけ,問題探索の枝刈を行う.具体的には,解盤面が与えられると,一意解制約を探索し,BDDシステムBEM-IIへのスクリプトに変換し,BEM-IIで解き,その出力を問題に変換し,一意解しか持たないかのチェックを行い,パスした場合が所望の問題となる.17ヒント問題に対して,Dancing Linkを応用した後戻り型探索プログラムを実装し,質の悪い場合でも30秒程度探索が終えるようになった.しかし,これでも16ヒント問題の全探索にはまだまだ不十分である.(3)解盤面の個数は6670903752021072936960≒6.7×10^<21>個であり,戸神・渡辺氏はそのような解盤面の一意に番号付けている.我々は,本質的に異なる解盤面5472730538≒5.4×10^9個に対して,一意に番号付を行うシステムを開発した.これを通じて,16ヒント問題探索空間を大幅に減らすことが可能となった.また,昨年度発表した「数独の問題作成支援システムの設計と開発」(前田・奥乃)に対して,情報処理学会第70回全国大会大会奨励賞が授与された.公開中の本システムは,「人が解く様子を再現できる点でこれに勝るソフトはない」という評価を得ている.