Content area
Full Text
Abstract-Sudoku is a popular puzzle utilizing 81 squares in a 9x9 grid consisting of nine 3x3 boxes. The digits 1-9 can each appear only once in a given row, column, or box. This paper describes the implementation of Particle Swarm Optimization (PSO) to solve sudoku puzzles using GPU processing. This PSO uses our opensource PSO framework that takes advantage of CUDAenabled GPUs. Although each row contains nine digits, permutations of nine digits can be represented as eight "picks". To find a solution each of the nine rows was treated as a permutation. This reduced the problem dimensionality from 81 to 72. With suitable parameters the algorithm was able to solve multiple sudoku puzzles. This paper describes the implementation of the algorithm , the fitness function used, and the effects of variation on PSO parameters. The original PSO framework and the Sudoku code described in this paper are available online.
I. INTRODUCTION
An open source framework for implementing Multiswarm Particle Swarm Optimization on GPUs using CUDA was developed and discussed in [1] . The framework was previously demonstrated on a problem to optimize the parameters of a PID controller. This was a relatively well behaved problem in a three dimensional space. It was shown that by utilizing GPU processing, the problem could be solved many times faster than was possible using the CPU.
In the previous paper it was claimed that the framework could easily be extended to other problems and higher dimensional spaces. In this paper we utilize the framework to find solutions to Sudoku puzzles. These represent a class of problems in a very high dimensional space . Furthermore, the space has large number of local minima that occur at large distances from the global minimum.
We believe that the solution of Sudoku puzzles represents a very significant optimization problem. In this paper we show that 1) the open source Multi-Swarm Particle Swarm Optimization Framework that we have previously developed is in deed general enough to extend to this problem, 2) that the dimensionality of the problem can be reduced using permutations, 3) that the use of GPUs is crucial for reducing run times from multiple days to hours, 4) that PSO can indeed solve Sudoku puzzles, and 5) that the choice...