A Retrievable Genetic Algorithm for Efficient Solving of Sudoku Puzzles

Authors: Seyed Mehran Kazemi, Bahare Fatemi

Abstract:

Sudoku is a logic-based combinatorial puzzle game which is popular among people of different ages. Due to this popularity, computer softwares are being developed to generate and solve Sudoku puzzles with different levels of difficulty. Several methods and algorithms have been proposed and used in different softwares to efficiently solve Sudoku puzzles. Various search methods such as stochastic local search have been applied to this problem. Genetic Algorithm (GA) is one of the algorithms which have been applied to this problem in different forms and in several works in the literature. In these works, chromosomes with little or no information were considered and obtained results were not promising. In this paper, we propose a new way of applying GA to this problem which uses more-informed chromosomes than other works in the literature. We optimize the parameters of our GA using puzzles with different levels of difficulty. Then we use the optimized values of the parameters to solve various puzzles and compare our results to another GA-based method for solving Sudoku puzzles.

Keywords: Genetic algorithm, optimization, solving Sudoku puzzles, stochastic local search.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1092323

References:

[1] T. Mantere and J. Koljonen, "Solving and rating sudoku puzzles with genetic algorithms,” in New Developments in Artificial Intelligence and the Semantic Web, Proceedings of the 12th Finnish Artificial Intelligence Conference STeP, pp. 86–92, 2006.
[2] Y. Takayuki and S. Takahiro, "Complexity and completeness of finding another solution and its application to puzzles,” IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 86, no. 5, pp. 1052–1060, 2003.
[3] M. R. Garey and D. S. Johnson, Computers and intractability, vol. 174. Freeman New York, 1979.
[4] R. Lewis, "Metaheuristics can solve sudoku puzzles,” Journal of heuristics, vol. 13, no. 4, pp. 387–401, 2007.
[5] J. F. Crook, "A pencil-and-paper algorithm for solving Sudoku puzzles,” Notices of the AMS, vol. 56, no. 4, pp. 460–468, 2009.
[6] M. Perez and T. Marwala, "Stochastic optimization approaches for solving Sudoku,” arXiv preprint arXiv:0805.0697, 2008.
[7] J. H. Holland, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press, 1975.
[8] C. Darwin and J. W. Burrow, The origin of species by means of natural selection: Or, The preservation of favoured races in the struggle for life. Collier Books Nueva York^ eN. YNY, 1962.
[9] J. Heitkoetter and D. Beasley, "The hitchhiker’s guide to evolutionary computing: A list of Frequently Asked Questions (FAQ),” USENET: comp. ai. genetic, 1996. Available via anonymous FTP from rtfm. mit. edu:/pub/usenet/news. answers/aifaq/genetic.
[10] E. K. Prebys, "The genetic algorithm in computer science,” MIT Undergrad. J. Math, vol. 2007, pp. 165–170, 2007.
[11] J. Li and Z. Zhang, "A learning tool of genetic algorithm,” in Education Technology and Computer Science (ETCS), 2010 Second International Workshop on, 2010, vol. 1, pp. 443–446.
[12] K. N. Das, S. Bhatia, S. Puri, and K. Deep, "A retrievable GA for solving Sudoku puzzles,” Citeseer, 2012.