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

本論文は最小個数17 個の要素で構成される数独パズルのヒントを効率的に見つけ出すアルゴリズムを提案する．本アルゴリズムでは空集合から出発して1 つずつ「最適」なヒント要素をヒント集合に添加しながら，なるべく個数の少ない数独のヒント集合を構成する．ここで「最適」なヒント要素とは，ヒント集合に添加することによって解集合のサイズがなるべく小さくなるようなヒント要素のことである．このような「最適」なヒント要素を探索するためにヒント集合のサイズが小さいときは，メトロポリス法に基づくマルコフ連鎖を構成し，それを用いて解を等確率にサンプリングし，ヒント集合が大きくなるとバックトラック法により解をすべて列挙してヒント要素を見つける．このような方法では必ず最小のヒント数17 のヒント集合が得られるとは限らず，本アルゴリズムでは[2] の方法を拡張しビームサーチを用いることで17 個の要素で構成されるヒントが生成される確率を[2] の6%や[7] の52%から83%まで向上させた．

The present paper describes an algorithm for generating a hint set of the Sudoku puzzle efficiently which consists of seventeen hint elements, where seventeen is known to be the least number of hint elements for the puzzle. Starting with the empty set, the algorithm constructs hint sets with small number of elements adding ‘optimal’ hint elements one by one, where an ‘optimal’ hint element is defined as an element that reduces number of solutions of the puzzle a lot adding the element. In order to find such an ‘optimal‘ solution, when the hint set is small, the algorithm constructs a Markov chain based on the Metroporis method and samples solutions of the puzzle with equal probabilities. On the other hand, when the hint set gets large, the algorithm enumerates the solutions of the puzzle and find an optimal hint element. The algorithm finds a hint set of size 17, which is known as the least number of Sudoku hints, probabilistically. Expanding [2] with the beam search algorithm, our algorithm improved the generation ratio of Sudoku hints of size 17 to 83%, where the ratios of [2] and [7] were 6% and 52% respectively.