Abstract
Sudoku puzzle is a game which takes the form of an N × N matrix. It requires the players to organize the number sequences from 1 to N in the submatrices of the original matrix in such a way that no numbers are reused in each sub matrices and also the numbers are not reused in each column and rows. It is mainly based on the number replacement game and is a combinatorial puzzle. Several evolutionary techniques such as Genetic algorithm, Particle Swarm Optimization, Ant Colony Optimization, and Artificial Bee Colony Optimization are used for solving, rating, and generating Sudoku Puzzles. This research paper presents a survey of solving Sudoku Puzzles using different evolutionary technique-based hybridized algorithms and analyze the results, i.e., success rates found in solving the puzzles of different levels such as Easy, Medium, Challenging, Hard, Evil, and Super Hard.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Das, K.N., Bhatia, S., Puri, S., Deep, K.: A retrievable GA for solving Sudoku puzzles. Technical report (2012)
Sabuncu, I.: Work-in-progress: solving Sudoku puzzles using hybrid ant colony optimization algorithm. In: 2015 1st International Conference on Industrial Networks and Intelligent Systems (INISCom), pp. 181–184. IEEE (2015)
Wang, Z., Yasuda, T., Ohkura, K.: An evolutionary approach to Sudoku puzzles with filtered mutations. In: 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 1732–1737. IEEE (2015)
Sato, Y., Inoue, H.: Solving Sudoku with genetic operations that preserve building blocks. In: Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games, pp. 23–29. IEEE (2010)
Sato, Y., Hasegawa, N., Sato, M.: GPU acceleration for Sudoku solution with genetic operations. In: 2011 IEEE Congress of Evolutionary Computation (CEC), pp. 296–303. IEEE (2011)
Hereford, J.M., Gerlach, H.: Integer-valued Particle Swarm Optimization applied to Sudoku puzzles. In: Swarm Intelligence Symposium (SIS 2008), pp. 1–7. IEEE (2008)
Kamei, K., Nakano, M. An approach to search the solution of a puzzle game by Particle Swarm Optimization. In: 2014 Joint 7th International Conference on and Advanced Intelligent Systems (ISIS), 15th International Symposium on Soft Computing and Intelligent Systems (SCIS), pp. 75–80. IEEE (2014)
Singh, G., Deep, K.: A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku. Appl. Soft Comput. 45, 27–39 (2016)
Schiff, K.: An ant algorithm for the Sudoku problem. J. Autom. Mob. Robot. Intell. Syst. 9 (2015)
Asif, M., Baig, R.: Solving NP-complete problem using ACO algorithm. In: International Conference on Emerging Technologies (ICET 2009), pp. 13–16. IEEE (October 2009)
Pacurib, J.A., Seno, G.M.M., Yusiong, J.P.T.: Solving Sudoku puzzles using improved artificial bee colony algorithm. In: 2009 Fourth International Conference on Innovative Computing, Information and Control (ICICIC), pp. 885–888. IEEE (2009)
Kaur, A., Goyal, S.: A survey on the applications of bee colony optimization techniques. Int. J. Comput. Sci. Eng. 3(8), 3037 (2011)
Moraglio, A., Togelius, J., Lucas, S.: Product geometric crossover for the Sudoku puzzle. In: 2006 IEEE International Conference on Evolutionary Computation, pp. 470–476. IEEE (2006)
Mantere, T., Koljonen, J.: 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)
Mantere, T., Koljonen, J.: Solving, rating and generating Sudoku puzzles with GA. In: 2007 IEEE Congress on Evolutionary Computation, pp. 1382–1389. IEEE (2007)
Mantere, T., Koljonen, J.: Solving and analyzing Sudokus with cultural algorithms. In: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 4053–4060. IEEE (2008)
Mantere, T.: Improved ant colony genetic algorithm hybrid for Sudoku solving. In: 2013 Third World Congress on Information and Communication Technologies (WICT), pp. 274–279. IEEE (2013)
Li, Y., Deng, X.: Solving Sudoku puzzles based on improved genetic algorithm. Jisuanji Yingyong yu Ruanjian 28(3), 68–70 (2011)
Deng, X.Q., Da Li, Y.: A novel hybrid genetic algorithm for solving Sudoku puzzles. Optim. Lett. 7(2), 241–257 (2013)
Waiyapara, K., Wattanapornprom, W., Chongstitvatana, P.: Solving Sudoku puzzles with node based Coincidence algorithm. In: 2013 10th International Joint Conference on Computer Science and Software Engineering (JCSSE), pp. 11–16. IEEE (2013)
Redding, J., Schreiver, J., Shrum, C., Lauf, A., Yampolskiy, R.: Solving NP-hard number matrix games with Wisdom of Artificial Crowds. In: Computer Games: AI, Animation, Mobile, Multimedia, Educational and Serious Games (CGAMES), pp. 38–43. IEEE (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Mishra, D.B., Mishra, R., Das, K.N., Acharya, A.A. (2018). Solving Sudoku Puzzles Using Evolutionary Techniques—A Systematic Survey. In: Pant, M., Ray, K., Sharma, T., Rawat, S., Bandyopadhyay, A. (eds) Soft Computing: Theories and Applications. Advances in Intelligent Systems and Computing, vol 583. Springer, Singapore. https://doi.org/10.1007/978-981-10-5687-1_71
Download citation
DOI: https://doi.org/10.1007/978-981-10-5687-1_71
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-5686-4
Online ISBN: 978-981-10-5687-1
eBook Packages: EngineeringEngineering (R0)