著者

那須 律政 松崎 公紀

雑誌

第54回プログラミング・シンポジウム予稿集

巻号頁・発行日

vol.2013, pp.173-180, 2013-01-11

---

ペンシルパズルのうちでも,数独に対してさまざまな研究が行われている.そのうち,最少ヒント問題とは,唯一解を持つ盤面を構成できる最少のヒント数はいくつかという問題である.通常のサイズが9×9の数独については,2012年1月にMcGuireらによって,ヒント数16の盤面がない,すなわち,最少ヒントが17であることが示された.GPCCの2011年問題では,サイズが16×16の数独に対する最少ヒント問題がとりあげられ,そのなかで白川によってヒント数56の盤面が発見された.著者らもこの数独の少数ヒント問題に対して研究を行っている.数独の少数ヒント盤面を効率良く生成するには,広大な探索空間の中から適切に探索を行う必要がある.著者らは,ゲーム分野で近年活発に研究されているモンテカルロ木探索手法をこの問題に適用し,少数ヒント問題を効率良く生成することを目指している.本論文では,数独少数ヒント盤面生成にモンテカルロ木探索手法を適用するにあたり必要であった工夫と,得られた少数ヒント盤面について報告する.