My partner and I recently presented our semester project in ECE 577 Fuzzy Logic:

A particle swarm optimization sudoku solver.

Sounds nasty right? Let’s break it down into a few parts:

1. Sudoku
   • A sudoku is made up of a 9 row by 9 column grid of cells
   • Each cell holds a number between 1 and 9
   • Each unique sudoku will have some of its cells already filled
   • The puzzle is solved when:
     • Each row contains the numbers 1 through 9
     • Each column contains the numbers 1 through 9
     • Each of the 9 little 3×3 squares contains the numbers 1 through 9
2. Sudoku Solver
   A sudoku solver is something that can fill every cell in a way that solves the sudoku. This can usually be done quickly and efficiently by viewing sudoku as a Constraint Satisfaction Problem. We decided to try to solve the same problem using a particle swarm optimization.
3. Particle Swarm Optimization (PSO)
   Particle swarm optimization is a stochastic search method that uses communication between particles to move toward a solution. Like other stochastic search methods, PSO is used to find a solution when there are too many possibilities to check one-by-one. Think needle in a really, really big haystack. A particle swarm optimization consists of a swarm containing some (usually large) number of particles. Each particle has a position in the search space, and a velocity that moves it toward a solution in the search space. Particles work together, telling each other about how well they’re doing. An analogy is vultures flying around, spread out over a desert, eventually all showing up at some dead animal.

The next step is to figure out how to massage the concept of a sudoku into a particle swarm optimization. There are two tasks here:

1. Figure out how to represent a sudoku as a particle
   We decided to let each particle contain a filled out sudoku puzzle, representing a position in the 81 dimensional (9 rows by 9 columns = 81 cells) search space. Each particle contains another 9 by 9 matrix of velocity values, as well as some bookkeeping stuff for the PSO.
2. Come up with a fitness function to evaluate our particles
   We eventually settled on a fitness function that scores:
   • 10 points per correct 3 by 3 square
   • 9 points per correct row
   • 9 points per correct column
   • 1 extra point for each cell that satisfies an extra constraint (intersection of: row and square, column and square, column and row, or all three)

We whipped up an implementation in python, and used the PyQt4 bindings to build a Qt4 Graphical User Interface (GUI) so we could watch what was going on in the simulation.

Unfortunately, we saw very limited success as far as actually solving sudokus. In almost every puzzle we attempted, our swarm would work well for a while, but eventually get clumped up on one partial solution, and stop improving.

On the bright side, I got to get even more familiar with python (<3), and also got my hands dirty with the model-view architecture of Qt4.