メトロポリスサンプラーを用いたヒント数の少ない数独問題の探索

DOI

書誌事項

タイトル別名
  • Searching for Sudoku puzzle problems with a small number hints using the Metropolis sampler.

抄録

<p>数独は，9×9マスにいくつかの数字のヒントが与えられるパズルの一種である．数独の難易度はヒントが少ないほど難しい傾向にある．数独の問題をコンピュータに解かせる場合，バックトラックを用いることで難易度を問わず短時間で解くことができるが，ヒント数の少ない問題を生成することは簡単ではない．本研究ではメトロポリスサンプラーと貪欲法を用いて，ヒントが0の状態からヒントを順次添加していくことでヒント数の少ない数独問題を生成することを提案する．この方法を用いることで数独の問題を65分19秒かけて1個生成することができた．これを繰り返し，15個の問題を生成した内，ヒント19の問題を2個生成することができた．この計算にはIntel(R) Xeon(R) CPU E3-1225 V2 @ 3.20GHzを使用した．</p>

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390848250119719168
  • NII論文ID
    130007857214
  • DOI
    10.11517/pjsai.jsai2020.0_4c2gs1301
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • CiNii Articles
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ