モンテカルロ木探索による数独少数ヒント盤面の生成

• Item type: Symposium(1)
• 公開日: 2013-01-11
• タイトル: モンテカルロ木探索による数独少数ヒント盤面の生成
• タイトル / 言語: en
• タイトル: Generation of Less-Clue Sudoku Boards by Monte-Carlo Tree Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: セッション8
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 高知工科大学大学院 工学研究科 基盤工学専攻
• 著者所属: 高知工科大学 情報学群
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Kochi University of Tech-nology
• 著者所属(英): en
• 著者所属(英): School of Information, Kochi University of Technology
• 著者名: 那須, 律政; 松崎, 公紀
• 著者名(英): Norimasa, Nasu; Kiminori, Matsuzaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ペンシルパズルのうちでも，数独に対してさまざまな研究が行われている．そのうち，最少ヒント問題とは，唯一解を持つ盤面を構成できる最少のヒント数はいくつかという問題である．通常のサイズが9×9の数独については，2012年1月にMcGuireらによって，ヒント数16の盤面がない，すなわち，最少ヒントが17であることが示された．GPCCの2011年問題では，サイズが16×16の数独に対する最少ヒント問題がとりあげられ，そのなかで白川によってヒント数56の盤面が発見された．; 著者らもこの数独の少数ヒント問題に対して研究を行っている．数独の少数ヒント盤面を効率良く生成するには，広大な探索空間の中から適切に探索を行う必要がある．著者らは，ゲーム分野で近年活発に研究されているモンテカルロ木探索手法をこの問題に適用し，少数ヒント問題を効率良く生成することを目指している．本論文では，数独少数ヒント盤面生成にモンテカルロ木探索手法を適用するにあたり必要であった工夫と，得られた少数ヒント盤面について報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Among several pencil puzzles, Sudoku has been studied most intensively. A research problem on Sudoku is called the minimum number of clues problem: how many clues are necessary to construct a Sudoku board with a unique solution. For the usual 9 by 9 Sudoku, McGuire et al. showed on January 2012 that there is no 16-clue Sudoku board with a unique solution and the minimum number of clues is 17. In GPCC2011, it was a problem to find a board with a smaller number of clues for the 16 by 16 Sudoku, and Shirakawa found a 56-clue board. We also have studied on generation of these less-clue Sudoku boards. A challenge in the effective generation of less-clue Sudoku boards is to find those boards from a very broad search space. We have applied the monte-carlo tree search technique, which has been widely studied in game programming, to generate efficiently less-clue Sudoku boards. In this paper, we show how we apply the monte-carlo tree search technique to the generation of less-clue Sudoku boards. We also report the Sudoku boards that we have obtained in the experiments.
• 書誌情報: 第54回プログラミング･シンポジウム予稿集; 巻 2013, p. 173-180, 発行日 2013-01-11
• 出版者 / 言語: ja
• 出版者: 情報処理学会