Testing the JGAP Sudoku Solver

by Alexis Dekle

The JGAP sudoku solver attempts to solve sudoku puzzles using a genetic algorithm approach. The solver fills in the blank spaces in a puzzle with random numbers between 1-9. It then calculates a "fitness" value according to how many unique numbers are in each row, column, and square. A total of 216 points are possible, and a score of 216 means that the puzzle has been solved.   Part One: Deciding on Running Values   The JGAP sudoku solver improves the fitness values of the original set of puzzles by crossing and mutating them over a set number of generations. Both the population size and the number of generations can be specified and will affect the runtime and success of the solver.   My first task was to find population and generation values that would minimize runtime and maximize success. I chose a single puzzle, rated "easy", and ran it with several different population and generation values.   As the number of generations increased, the fitness value actually went down, due to the fact that:   The population size was being varied (in the opposite direction) at the same time.   The population size had a greater affect on the success of the solver, but it also had a greater affect on runtime. I settled on a population size of 30 and a generation number of 60. (N.B. The solver did not solve any of the puzzles. The longest runtime was 7:05, and it reached a fitness value of 198. In order to solve a puzzle it would have to run for days).   Part Two: Difficulty Levels   Generally, sudoku puzzles are divided into four difficulty levels: "easy", "medium", "hard", and "evil". However, the solver does not use the logic rules that a person would to solve the puzzle. Instead, it uses pure trial and error. Based on this fact, I decided to recategorize the puzzles. I felt that the number of initial values in the puzzle would be a better indicator of difficulty level (the more numbers specified to begin with, the fewer the solver has to fill in).   The puzzles graphed are across all "difficulty" levels, and are graphed by the number of initial values. As you can see, for purposes of this solver, the number of values present intially is a better indicator of difficulty.   Part Three: Suggestions   The JGAP sudoku solver never solved any of the puzzles I ran it on. It would probably have to run for days to solve even an easy puzzle, and even then would not be guaranteed to solve it (it sometimes levels off). This solver should either be rewritten to work differently, or puzzles should just be solved by hand.