[4C2-GS-13] AI application: Entertainment

[4C2-GS-13-01] Searching for Sudoku puzzle problems with a small number hints using the Metropolis sampler.

〇Yu Furukawa¹, Osami Yamamoto² (1. Graduate School of Science and Technology, Meijo University, 2. Faculty of Science and Technology, Meijo University)

Keywords:game, search

Sudoku is a puzzle with $9\times9$ cells where some numbers are given as hints. Although the puzzles tend to be difficult when small number of hints are given, we can solve any Sudoku puzzles in a reasonable time using backtracking. Contrarily, it is difficult to make a Sudoku puzzle with small number of hints because each puzzle should have only one solution. This paper presents a greedy algorithm for generating Sudoku puzzles with small number of hints by adding hints one by one starting from the hint less pattern. Employing a Metropolis sampler, we chose the optimal hints which reduced the number of solutions faster. Using the algorithm, we were able to obtain a puzzle with nineteen hints in 65 minutes and 19 seconds using a PC with Intel(R) Xeon(R) E3-1225 V2 3.2 GHz. Repeating the method fifteen times, we were able to obtain two Sudoku puzzles with nineteen hints.