長尾卓さん（理工学研究科　情報工学専攻　修士課程1年　山本研究室）

ゲームプログラミングワークショップ研究奨励賞

2022年11月16日

ビームサーチを用いたヒント数17の数独パズルの効率的な生成について

ゲームプログラミングワークショップは、情報処理学会ゲーム情報学研究会によって1994年から年１回行われているゲーム、パズルに関するワークショップです。ゲーム情報学に関する国内外の色々な研究発表が行われてきました。このワークショップの研究奨励賞は、ゲームプログラミングワークショップで発表した主に学生を対象として、優れた発表に対して贈呈される賞です。
本研究は数独パズルの問題生成に関する研究です。数独パズルの最小ヒント数は17であると証明されていることから、確率的にヒント数17の数独パズルを効率的に生成することを目的としています。先行研究が提案するシミュレーテッドアニーリングやバックトラックを用いたアルゴリズムをもとに様々な工夫を重ね、ヒント数17の生成確率を約5%から約83%まで向上させることができました。