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

基于使用二元决策图和自动问题生成方法的完整解表示的数独问题难度级别定义

• 批准号: 19650030
• 负责人: 奥乃 博
• 金额: $ 2.11万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19650030/
• 关键词: 組合せ型パズル; 全解探索; 二分決定グラフ; 数独; パズルの難易度; ナンバープレイス; 数独解インデックス; 制約充足問題

本年度は(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回全国大会大会奨励賞が授与された.公開中の本システムは,「人が解く様子を再現できる点でこれに勝るソフトはない」という評価を得ている.

This year, we will focus on (1) improvement of difficulty,(2) exploration of 16-dimensional problems,(3) identification of essential differences in solution space, and selection of groups. The results of the study were recorded. (1)The solution explores the improvement of the solution, the improvement of the difficulty of each solution, and the improvement of the difficulty of the solution. (2)The number of items in the table is set to the number of items in the table. The number of items in the table is set to the number of items in the Specifically, the solution to the problem is to explore the solution to the problem,BDD system, BEM-II system, BEM-II system, BDD system, BDD system, BDD The quality of the situation is 30 seconds to explore the final. All questions are answered in the following ways: (3)The number of unzipped plates is 6670903752021072936960 6.7×10^<21>, We have a total of 5472730538 and 5.4×10^9 pairs of special purpose vehicles. The answer is no. 16. The answer is no. The 70th National Conference of the Society for Information Processing was held in Beijing, China, and was awarded the award for "Sudoku Problem Creation Support System Design and Development"(Maeda Okunai). In the open, the text of the article says,"People's solution is to reproduce the five points of the article, and the article is to evaluate the article."