Nothing Special   »   [go: up one dir, main page]

Skip to main content

Solving Sudoku Puzzles Using Evolutionary Techniques—A Systematic Survey

  • Conference paper
  • First Online:
Soft Computing: Theories and Applications

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 583))

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Das, K.N., Bhatia, S., Puri, S., Deep, K.: A retrievable GA for solving Sudoku puzzles. Technical report (2012)

    Google Scholar 

  2. 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)

    Google Scholar 

  3. 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)

    Google Scholar 

  4. 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)

    Google Scholar 

  5. 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)

    Google Scholar 

  6. 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)

    Google Scholar 

  7. 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)

    Google Scholar 

  8. 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)

    Article  Google Scholar 

  9. Schiff, K.: An ant algorithm for the Sudoku problem. J. Autom. Mob. Robot. Intell. Syst. 9 (2015)

    Google Scholar 

  10. 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)

    Google Scholar 

  11. 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)

    Google Scholar 

  12. Kaur, A., Goyal, S.: A survey on the applications of bee colony optimization techniques. Int. J. Comput. Sci. Eng. 3(8), 3037 (2011)

    Google Scholar 

  13. 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)

    Google Scholar 

  14. 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)

    Google Scholar 

  15. Mantere, T., Koljonen, J.: Solving, rating and generating Sudoku puzzles with GA. In: 2007 IEEE Congress on Evolutionary Computation, pp. 1382–1389. IEEE (2007)

    Google Scholar 

  16. 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)

    Google Scholar 

  17. 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)

    Google Scholar 

  18. Li, Y., Deng, X.: Solving Sudoku puzzles based on improved genetic algorithm. Jisuanji Yingyong yu Ruanjian 28(3), 68–70 (2011)

    Google Scholar 

  19. Deng, X.Q., Da Li, Y.: A novel hybrid genetic algorithm for solving Sudoku puzzles. Optim. Lett. 7(2), 241–257 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  20. 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)

    Google Scholar 

  21. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Deepti Bala Mishra .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics