D.O. Hamnes and B.A. Julstrom (USA)
Evolutionary algorithm, local search, Sudoku
A Sudoku puzzle specifies symbols from the set S = {1, 2,..., 9} for some cells in a 9 x 9 grid, with no duplicate symbols in any of the grid’s rows, columns, or nonoverlapping 3 x 3 regions. The challenge is to fill the grid's remaining cells with symbols from S in such a way that the non-duplicate condition is preserved. An evolutionary algorithm to solve Sudoku puzzles encodes candidate solutions as 9×9 arrays. To these chromosomes, the EA applies operators based on the significant sub-structures of a puzzle: its rows, columns, and non-overlapping 3×3 regions. These operations include crossover, mutation, and an iterated mutation that we call wandering. Repeated trials of the EA on 100 published Sudoku puzzles all quickly found solutions.
Important Links:
Go Back
