数独パズルの難易度判定～解法ロジックを用いた数値化の提案～大阪工業大学情報科学部コンピュータ科学科土出智也目的  近年日本では脳トレやパズルが人気  中でも数独はその手軽さから注目されている  難易度は「★」、「Hard」など大雑把なものが多い  そこで解法によって難易度を数値化する →実際に解くことによって、より詳しく数値化できる数独とは？  ルール 1.ヨコ列のどの列にも1~9の数字が1つずつ入る 2.タテ列のどの列にも1~9の数字が1つずつ入る 3.太線で囲まれた3×3のどのブロックにも1~9の数字が1つずつ入る 6 2 8 1 4 3 5 3 7 6 1 9 3 2 4 9 7 6 8 1 5 7 3 8 5 9 5 6 2 8 1 7 9 4 3 1 3 9 6 5 4 8 7 2 8 4 7 2 3 9 6 5 1 6 1 3 5 2 8 7 9 4 9 7 8 3 4 1 2 6 5 2 5 4 7 9 6 3 1 8 3 9 1 4 6 2 5 8 7 7 2 6 1 8 5 4 3 9 4 8 5 9 7 3 1 2 6 難易度判定の現状  解法ではなく既存の情報から難易度を判定  公称難易度と空きマス数の関係 →空きマスが多いほど難しい？  公称難易度と候補数の関係 →候補数が多いほど難しい？空きマス数：数字を埋める場所（白マス）の合計値のこと候補数：各マスに入る可能性のある数字（候補）の数のこと公称難易度と空きマス数の関係 70 60 50 40 問題数 30 20 10 39 0 43 47 51 空きマス数 VeryHard MediumHard 55 59 Easy UltraEasy 公称難易度難易度が高いほど、空きマス数のピークが右側にある UltraEasy VeryEasy Easy Medium MediumHard Hard VeryHard Spicy 公称難易度と候補数の関係 Zhe Chenの数独エントロピー H G   1 1 log  v 81 ij ij 表１ Chen氏の論文記載の問題（10000問）最小値最大値平均値 Easy Intermediate 0.5362 1.2246 0.9046 1.3965 0.7439 1.3049 Hard 1.6946 1.8189 1.7526 表２世界基準ナンプレでの数独エントロピー（600問）最小値最大値平均値 UltraEasy VeryEasy 0.1983 0.3581 0.4324 0.6397 0.3509 0.5179 Easy Medium MediumPlus 0.652 0.7199 0.8252 0.8363 0.9793 1.0466 0.7304 0.8379 0.9241 Hard VeryHard 0.8165 0.8387 1.0244 1.0326 0.9175 0.9156 難易度の高いものほど、数独エントロピーは高くなっている Spicy 0.8956 0.984 0.9398 問題点    以上の２つは、どちらも解く以前の盤面の状態から難易度を示している計算は簡単であるが、解いてみないとわからない部分の数値化には至っていない本研究では実際に数独を解くことで、数字の埋まりやすさや思考の難しさを難易度の指標に取り込む使用する解法   雑誌・書籍に記載されているものをベースに、独自に７つに分類した解法は使用順にCRBE法(column,row,block,elimination)、単一候補法、単一マス法、双子法、共有候補法、三つ子法、対角線法とした CRBE法とは？右上ブロックで８がどこに入るかを考える１行目と２行目には既に８がある →一箇所に決定する数値化の方法   数値化は、問題を解く際の時間を用いる “時間”はそれぞれの解法の中でのループや探索の回数を用いる（例えば「１が埋まる場所を探す→６が埋まる場所を探す→ ４が埋まる場所を探す」なら、時間は３）   このようにすることで、一度に埋まる数字が少ないような難解な問題ほど数値が大きくなる算出した数値を“スコア”と呼ぶ結果：スコアと空きマス数 10000 スコア 1000 CRBE法候補使用双子法共有候補法三つ子法対角線法未完成 100 10 1 30 35 40 45 50 55 60 65 空きマス数同じような空きマス数でも、スコアを用いると難易度に違いがでる結果：スコアと数独エントロピー 10000 スコア 1000 CRBE法候補使用双子法共有候補法三つ子法対角線法未完成 100 10 1 0 0.2 0.4 0.6 0.8 1 1.2 数独エントロピー数独エントロピーが同じような値でも、スコアを用いると難易度に違いがでるまとめ    解法を元に難易度を数値化した解法の実行時間を元に数値化したので、空きマス数や候補数より詳細に難易度を知ることができた同じ解法の中でもばらつきがあるため、比較ができるようになったこのスコア計算法を元に、ソフトウエアを制作：『SudokuAnalyzer』