数独パズルの難易度判定 ～解法ロジックを用いた数値化の提案～

Presentation on theme: "数独パズルの難易度判定 ～解法ロジックを用いた数値化の提案～"— Presentation transcript:

1 数独パズルの難易度判定 ～解法ロジックを用いた数値化の提案～
大阪工業大学 情報科学部コンピュータ科学科 土出　智也

2 目的 近年日本では脳トレやパズルが人気 中でも数独はその手軽さから注目されている 難易度は「★」、「Hard」など大雑把なものが多い
そこで解法によって難易度を数値化する →実際に解くことによって、より詳しく数値化できる

3 数独とは？ ルール 1.ヨコ列のどの列にも1~9の数字が1つずつ入る 2.タテ列のどの列にも1~9の数字が1つずつ入る
3.太線で囲まれた3×3のどのブロックにも1~9の数字が1つずつ入る

4 難易度判定の現状 解法ではなく既存の情報から難易度を判定 →空きマスが多いほど難しい？ →候補数が多いほど難しい？
公称難易度と空きマス数の関係 →空きマスが多いほど難しい？ 公称難易度と候補数の関係 →候補数が多いほど難しい？ 空きマス数：数字を埋める場所（白マス）の合計値のこと 候補数：各マスに入る可能性のある数字（候補）の数のこと

5 公称難易度と空きマス数の関係 難易度が高いほど、空きマス数のピークが右側にある

6 公称難易度と候補数の関係 Zhe Chenの数独エントロピー 難易度の高いものほど、数独エントロピーは高くなっている
表２ 世界基準ナンプレでの数独エントロピー（600問） 難易度の高いものほど、数独エントロピーは高くなっている

7 問題点 以上の２つは、どちらも解く以前の盤面の状態から難易度を示している
計算は簡単であるが、解いてみないとわからない部分の数値化には至っていない 本研究では実際に数独を解くことで、数字の埋まりやすさや思考の難しさを難易度の指標に取り込む

8 使用する解法 雑誌・書籍に記載されているものをベースに、独自に７つに分類した
解法は使用順にCRBE法(column,row,block,elimination)、単一候補法、単一マス法、双子法、共有候補法、三つ子法、対角線法とした

9 CRBE法とは？ 右上ブロックで８がどこに入るかを考える １行目と２行目には既に８がある →一箇所に決定する

10 数値化の方法 数値化は、問題を解く際の時間を用いる “時間”はそれぞれの解法の中でのループや探索の回数を用いる
（例えば「１が埋まる場所を探す→６が埋まる場所を探す→ ４が埋まる場所を探す」なら、時間は３） このようにすることで、一度に埋まる数字が少ないような難解な問題ほど数値が大きくなる 算出した数値を“スコア”と呼ぶ

11 結果：スコアと空きマス数 同じような空きマス数でも、スコアを用いると難易度に違いがでる

12 結果：スコアと数独エントロピー 数独エントロピーが同じような値でも、スコアを用いると難易度に違いがでる

13 まとめ 解法を元に難易度を数値化した 解法の実行時間を元に数値化したので、空きマス数や候補数より詳細に難易度を知ることができた
同じ解法の中でもばらつきがあるため、比較ができるようになった このスコア計算法を元に、ソフトウエアを制作：『SudokuAnalyzer』