| Peer-Reviewed

A Comparative Evolutionary Models for Solving Sudoku

Received: 8 July 2013     Published: 10 November 2013
Views:       Downloads:
Abstract

Evolutionary algorithms have become robust tool in data processing and modeling of dynamic, complex and non-linear processes due to their flexible mathematical structure to yield optimal results even with imprecise, ambiguity and noise at its input. The study investigates evolutionary algorithms for solving Sudoku task. Various hybrids are presented here as veritable algorithm for computing dynamic and discrete states in multipoint search in CSPs optimization with application areas to include image and video analysis, communication and network design/reconstruction, control, OS resource allocation and scheduling, multiprocessor load balancing, parallel processing, medicine, finance, security and military, fault diagnosis/recovery, cloud and clustering computing to mention a few. Solution space representation and fitness functions (as common to all algorithms) were discussed. For support and confidence model adopted 1=0.2 and 2=0.8 respectively yields better convergence rates – as other suggested value combinations led to either a slower or non-convergence. CGA found an optimal solution in 32 seconds after 188 iterations in 25runs; while GSAGA found its optimal solution in 18seconds after 402 iterations with a fitness progression achieved in 25runs and consequently, GASA found an optimal solution 2.112seconds after 391 iterations with fitness progression after 25runs respectively.

Published in Automation, Control and Intelligent Systems (Volume 1, Issue 5)
DOI 10.11648/j.acis.20130105.13
Page(s) 113-120
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2013. Published by Science Publishing Group

Keywords

Swarms, Agents, Elitist, Evolutionary Algorithms, Constraints, Fitness Function

References
[1] Abarghouei, A., Ghanizadeh, A and Shamsuddin, S., (2009): Advances in soft computing methods in edge detection, J. Advance Soft Comp. Applications, ISSN: 2074-8523, 1(2).
[2] Cantu-Paz, E and Goldberg, D.E., (2000): Efficient parallel genetic algorithms: theory and practices, Computer methods in applied mechanics and engineering, 186(2-4), pp 221-238.
[3] Coello, C. A., Pulido, G. T and Lechuga, M.S., (2002): Handling multiple objectives with particle swarm optimization, Evo. Comp., Vol. 8, pp 256–279.
[4] Hassan, R and Crosswley, W., (2004): Variable population-based sampling for probabilistic design optimization and with a genetic algorithm, AIAA-2004-0452), 42nd Aerospace Science meeting, Reno, NV.
[5] Hassan, R., Cohanin, B., De Wec and Venter, G., (2006): Comparism of PSO and GA, American Institute of Aeronautic and Astronautics (AIAA-2006), 44th Aerospace Science meeting, Washington–DC.
[6] Heppner, H and Grenander, U (1990): A stochastic non-linear model for coordinated bird flocks, In Krasner, S (Ed.), The ubiquity of chaos, (pp. 233–238). Washington: AAAS.
[7] History of Sudoku, Conceptis Editoria, [online]: www.conceptispuzzle.com/articles/sudoku, last accessed 17-01-2013.
[8] Kilic, A. and Kaya, M.A (2001): A new local search algorithm based on genetic algorithms for the n-queens problem, Proc. Genetic and Evo. Comp. conf. (GECCO-2001), 158 – 161
[9] Lewis, R., (2007): Metaheuristics can solve Sudoku, J. Heuristics Archive, 13(8), pp 387 – 401
[10] Mantere, T and Koljonen, J., (2007): Solving and rating Sudoku puzzles via genetic algorithm, Proc. Congress on Evol. Comp.,1382-1389.
[11] Moraglio, A and Togelius, J., (2007): Geometric particles swarm optimization for Sudoku puzzle, http://julian.togelius.com/Moraglio2007Geomet-ric.pdf, last accessed 16-January-2013.
[12] Ojugo, A., Eboka, A., Yoro, E., Okonta, E and Aghware, F.O., (2012): Genetic algorithm rule-based intrusion detection system, J. Emerging Trends in Comp. Info. Syst., ISSN: 2079-8407, 3(8), pp 1182-1194
[13] Ojugo, A.A., (2012): Gravitational search neural network algorithm for rainfall runoff modeling, Unpublished PhD thesis, Abakiliki: Ebonyi State University, Nigeria.
[14] Perez, M and Marwala, T., (2011): Stochastic optimization approaches for solving Sudoku, Proc. IEEE Congress on Evo. Comp., pp 256–279, Vancouver: Piscataway.
[15] Poli, R., Wright A., McPhee, N and Langdon, W., (2006b): Emergent behaviour, population based search and low-pass filtering, Proc. on Comp. Intelligence and Evo.Comp., pp395-402, Vancouver: Piscataway
[16] Reynolds, R., (1994): An introduction to cultural algorithms, Proc. of 3rd Annual Conf. on Evo. Programming, River Edge: New Jersey, World Scientific, pp 131-139.
[17] Santos-Garcia, G and Palomino, M., (2007): Solving the Sudoku puzzle with rewriting rules, Notes on Theo. Computer Sci., 17(4), pp79-93
Cite This Article
  • APA Style

    A. A. Ojugo., D. Oyemade., R. E. Yoro., A. O. Eboka., M. O. Yerokun, et al. (2013). A Comparative Evolutionary Models for Solving Sudoku. Automation, Control and Intelligent Systems, 1(5), 113-120. https://doi.org/10.11648/j.acis.20130105.13

    Copy | Download

    ACS Style

    A. A. Ojugo.; D. Oyemade.; R. E. Yoro.; A. O. Eboka.; M. O. Yerokun, et al. A Comparative Evolutionary Models for Solving Sudoku. Autom. Control Intell. Syst. 2013, 1(5), 113-120. doi: 10.11648/j.acis.20130105.13

    Copy | Download

    AMA Style

    A. A. Ojugo., D. Oyemade., R. E. Yoro., A. O. Eboka., M. O. Yerokun, et al. A Comparative Evolutionary Models for Solving Sudoku. Autom Control Intell Syst. 2013;1(5):113-120. doi: 10.11648/j.acis.20130105.13

    Copy | Download

  • @article{10.11648/j.acis.20130105.13,
      author = {A. A. Ojugo. and D. Oyemade. and R. E. Yoro. and A. O. Eboka. and M. O. Yerokun and E. Ugboh},
      title = {A Comparative Evolutionary Models for Solving Sudoku},
      journal = {Automation, Control and Intelligent Systems},
      volume = {1},
      number = {5},
      pages = {113-120},
      doi = {10.11648/j.acis.20130105.13},
      url = {https://doi.org/10.11648/j.acis.20130105.13},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acis.20130105.13},
      abstract = {Evolutionary algorithms have become robust tool in data processing and modeling of dynamic, complex and non-linear processes due to their flexible mathematical structure to yield optimal results even with imprecise, ambiguity and noise at its input. The study investigates evolutionary algorithms for solving Sudoku task. Various hybrids are presented here as veritable algorithm for computing dynamic and discrete states in multipoint search in CSPs optimization with application areas to include image and video analysis, communication and network design/reconstruction, control, OS resource allocation and scheduling, multiprocessor load balancing, parallel processing, medicine, finance, security and military, fault diagnosis/recovery, cloud and clustering computing to mention a few. Solution space representation and fitness functions (as common to all algorithms) were discussed. For support and confidence model adopted 1=0.2 and 2=0.8 respectively yields better convergence rates – as other suggested value combinations led to either a slower or non-convergence. CGA found an optimal solution in 32 seconds after 188 iterations in 25runs; while GSAGA found its optimal solution in 18seconds after 402 iterations with a fitness progression achieved in 25runs and consequently, GASA found an optimal solution 2.112seconds after 391 iterations with fitness progression after 25runs respectively.},
     year = {2013}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - A Comparative Evolutionary Models for Solving Sudoku
    AU  - A. A. Ojugo.
    AU  - D. Oyemade.
    AU  - R. E. Yoro.
    AU  - A. O. Eboka.
    AU  - M. O. Yerokun
    AU  - E. Ugboh
    Y1  - 2013/11/10
    PY  - 2013
    N1  - https://doi.org/10.11648/j.acis.20130105.13
    DO  - 10.11648/j.acis.20130105.13
    T2  - Automation, Control and Intelligent Systems
    JF  - Automation, Control and Intelligent Systems
    JO  - Automation, Control and Intelligent Systems
    SP  - 113
    EP  - 120
    PB  - Science Publishing Group
    SN  - 2328-5591
    UR  - https://doi.org/10.11648/j.acis.20130105.13
    AB  - Evolutionary algorithms have become robust tool in data processing and modeling of dynamic, complex and non-linear processes due to their flexible mathematical structure to yield optimal results even with imprecise, ambiguity and noise at its input. The study investigates evolutionary algorithms for solving Sudoku task. Various hybrids are presented here as veritable algorithm for computing dynamic and discrete states in multipoint search in CSPs optimization with application areas to include image and video analysis, communication and network design/reconstruction, control, OS resource allocation and scheduling, multiprocessor load balancing, parallel processing, medicine, finance, security and military, fault diagnosis/recovery, cloud and clustering computing to mention a few. Solution space representation and fitness functions (as common to all algorithms) were discussed. For support and confidence model adopted 1=0.2 and 2=0.8 respectively yields better convergence rates – as other suggested value combinations led to either a slower or non-convergence. CGA found an optimal solution in 32 seconds after 188 iterations in 25runs; while GSAGA found its optimal solution in 18seconds after 402 iterations with a fitness progression achieved in 25runs and consequently, GASA found an optimal solution 2.112seconds after 391 iterations with fitness progression after 25runs respectively.
    VL  - 1
    IS  - 5
    ER  - 

    Copy | Download

Author Information
  • Department of Mathematics/Computer Sci, Federal University of Petroleum Resources Effurun, Delta State

  • Department of Mathematics/Computer Sci, Federal University of Petroleum Resources Effurun, Delta State

  • Department of Computer Science, Delta State Polytechnic Ogwashi-Uku, Delta State, Nigeria

  • Department of Computer Sci. Education, Federal College of Education (Technical), Asaba, Delta State

  • Department of Computer Sci. Education, Federal College of Education (Technical), Asaba, Delta State

  • Department of Computer Sci. Education, Federal College of Education (Technical), Asaba, Delta State

  • Sections