研究室トップページへ / 卒業研究一覧へ

大阪工業大学 情報科学部 宇宙物理・数理科学研究室　2014年度　卒業研究

部分的に重なった数独の効率良い解き方
- 数独の盤面を解く順番の比較 -

情報ネットワーク学科　安藤恭史

2015/2/10 作成
概要 / 目次 /

概要


図1　部分的に重なった数独

　近年，ペンシルパズルである数独は世界的に人気である．一般的な数独は3×3のマスを1ブロックとして9ブロックで構成した9×9のマスであるが，本研究では図1のような部分的に重なった数独に注目し，どのような手順で解けば効率が良いのか（すなわち，盤面の注目すべき順は何か），プログラムを独自に開発して自動で解かせることにより比較した．

　数独の解き方は単独候補数字法，及び単独候補マス法の2つのロジックを使用した．比較方法はそれぞれのマスに何回注目したかの回数（「探索回数」と呼ぶ）を用いた．盤面の注目する順番は図2のA，B，Cを用いて次の3種類を考慮した．
　　　　　方針1：交互法（探索方法：『ACCB』の繰り返し）
　　　　　方針2：重なり部分重視法（探索方法：『AC…C BC…C』の繰り返し）
　　　　　方針3：片側法（探索方法：『ACAC…AC CBCB…CB』の繰り返し）


図2　盤面の呼び方

　C部分が空白の30個の問題について試みた結果，最も探索回数が少なかったのは片側法で23個（76.7％の割合）だった．交互法は6個（20.0％の割合）で，重なり部分重視法は1個（3.3％の割合）だった．

　図3は問題ごとの探索回数を上記3方針の平均値順にプロットしたものであり，易しい（探索回数が少ない）問題は3方針で探索回数に差があまり生じなかったが，難しい問題になるほど有意な差が見られた．難しい問題の上位10問では，1問が交互法，もう1問が重なり部分重視法が優れていたが，他の8問は片側法が優れていた．片側法はこの10問では，交互法より平均15.1％（65.7回）探索回数が少なかった．


図3　盤面の切り替えによる探索回数の比較

　以上より，このタイプの数独では，片方の盤面に注目して解きあげる方法が能率的であると結論できる．

目次

  1. 序論
    1. 背景
    2. 研究の目的
    3. 本論文の構成
  2. 数独
    1. ルール
    2. 本論文で取り扱う用語
      1. マス，行，列，ブロック
      2. 候補数字，ペンシルマーク
  3. 数独の解き方
    1. 単独候補数字法
    2. 単独候補マス法
    3. その他の解き方
      1. 双子法，三つ子法
      2. Xウイング法
  4. 部分的に重なった数独
    1. 盤面の呼び方
    2. 9×9の数独1面との違い
    3. 本研究での比較方法
    4. 効率
      1. 切り替えのタイミング
      2. 具体例
  5. 探索回数・評価の決め方
    1. プログラム上での計測方法
    2. 探索の仕方
      1. 例外処理
    3. 評価方法
  6. 解析
    1. 用意した数独
    2. 実行結果1 - 探索順序と探索開始位置の考慮 -
    3. 実行結果2 - 部分的に重なった箇所を考慮 -
    4. 結論
  7. まとめ
    1. 本研究について
    2. 考慮
    3. 展望
安藤恭史