CloSAS Clonal selection algorithm with simulated annealing for sudoku puzzles. - Auza, Joshua Joseph G.; Garapan, Jaydee A. (Joshua Joseph G. Auza, 2009)
Sudoku puzzles are puzzles known for its simple instructions yet really tricky solutions. It is a very popular brain exercise but central to its clever structure is the fact that it is an NP-complete problem. Fast Sudoku solvers existing today are well-crafted using logic-based techniques. However, for those puzzles that requires "guessing", these logic-based techniques fail to provide shorter execution times. An alternative way to Solve Sudoku puzzles is to use metaheuristics. In this paper, the Clonal Selection Algorithm (CLONALG) coupled with Simulated Annealing is applied to solve Sudoku puzzles. The fast learning capability of CLONALG stimulates good explorations or new local optima in the affinity landscape while the flexibility of the Simulated Annealing prevents the explorations from getting trapped to some local optima and eventually land at the global optimum. In essence, the hybrid algorithm embodies a robust solver due to the fact that it harnesses both of these critical assets of the two algorithms. Various experiments were conducted and results show that the hybrid algorithm could effectively solve all sampled 6x6, 9x9, and 12x12 standard Sudoku puzzles.