An approach to search the solution of a puzzle game by Particle Swarm Optimization

摘要

Recently, the researches that regard puzzle games as nonlinear optimization problems have been studied. The puzzles, which are N-Queen problem and Knapsack problem, are called NP-hard or NP-complete problem, hence the studies have been actively. On the other hand, there are a lot of puzzle game in the world, nevertheless many puzzle game have not been studied actively. In our research, we adopt "Sudoku(Number Place)" puzzle. Sudoku is one of the combination puzzles of numbers. There are many local minima in Sudoku, and the overall optimum solution has to be determined by combination among local minima. Moreover, the solution between the overall optimum and the quasi-optimum are very similar. We propose to solve Sudoku based on Particle Swarm Optimization(PSO). The results are that PSO is able to only solve up to 15 blank grids. To overcome this difficulty, we propose to modify the exploration process that re-explore from another initial state if the solution is quasi-optimum. The improved PSO succeeded in solving in case of 17 blank grids.