情報処理学会 第83回全国大会 会期:2021年3月18日~20日 会場:オンライン開催 情報処理学会 第83回全国大会 会期:2021年3月18日~20日 会場:オンライン開催

6K-06
MCMC法によるヒントの少ない数独問題の生成
○古川 湧,山本修身(名城大)
数独は9×9マスのペンシルパズルの一種である.ルールの簡単さから新聞やパズル雑誌など世界中で幅広く遊ばれている.数独は最初に与えられたヒントの集合に対して解が唯一でなければならないと決められている.ヒント数が少ないほど解が複数になりやすく,数独を作ることは難しくなる.本稿ではメトロポリス法によって生成したある程度ヒントの少ない数独問題の中から,マルコフチェインモンテカルロ法(MCMC)によって冗長なヒントの組を見つけ出し,それらのヒントを削減して新たにヒントを添加することでより少ないヒント数の数独を作ることを試みた.その結果,ヒント数21の数独をヒント数18に削減することができた.