@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00095546, author = {那須, 律政 and 松崎, 公紀 and Norimasa, Nasu and Kiminori, Matsuzaki}, book = {第54回プログラミング・シンポジウム予稿集}, month = {Jan}, note = {ペンシルパズルのうちでも,数独に対してさまざまな研究が行われている.そのうち,最少ヒント問題とは,唯一解を持つ盤面を構成できる最少のヒント数はいくつかという問題である.通常のサイズが9×9の数独については,2012年1月にMcGuireらによって,ヒント数16の盤面がない,すなわち,最少ヒントが17であることが示された.GPCCの2011年問題では,サイズが16×16の数独に対する最少ヒント問題がとりあげられ,そのなかで白川によってヒント数56の盤面が発見された. 著者らもこの数独の少数ヒント問題に対して研究を行っている.数独の少数ヒント盤面を効率良く生成するには,広大な探索空間の中から適切に探索を行う必要がある.著者らは,ゲーム分野で近年活発に研究されているモンテカルロ木探索手法をこの問題に適用し,少数ヒント問題を効率良く生成することを目指している.本論文では,数独少数ヒント盤面生成にモンテカルロ木探索手法を適用するにあたり必要であった工夫と,得られた少数ヒント盤面について報告する., 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.}, pages = {173--180}, publisher = {情報処理学会}, title = {モンテカルロ木探索による数独少数ヒント盤面の生成}, volume = {2013}, year = {2013} }