Open Access Open Access  Restricted Access Subscription or Fee Access

GA with Modifications for Efficiently Solving Number Puzzles

Anagha P. Khedkar

Abstract


The previous research on the genetic algorithm (GA) applications especially for puzzle solving focuses on the GA capability for solving the puzzles of differing difficulty levels viz. magic square, jigsaw, sliding tile, crossword, path finding and of similar type. But this work attempts to solve logical number puzzles of exponential and factorial complexity using conventional GA with some important modifications depending on the puzzle type. The overall modifications done in GA are the advanced twin operator, order crossover and use of only mutation without crossover. GA is designed and applied with these modifications considering one at a time to solve the three number puzzles. The experimental results reflect the performance improvement in GA in terms of best and average convergence generation. The advanced twin operator enhances the overall performance of modified GA by 40% over the conventional GA. The modified GA is also tested for variation in population size which shows the faster convergence with sufficiently increased population size. Further to extend the current work, it is needed to find out the optimal population size depending on the puzzle problem.

Cite this Article
Khedkar Anagha P. GA with modifications for efficiently solving number puzzles. Journal of Artificial Intelligence Research & Advances. 2016; 3(1): 1–7p.


Keywords


GA, number puzzles, population size

Full Text:

PDF

References


Pillay N. Finding Solutions to Sudoku Puzzles Using Human Intuitive Heuristics. SACJ. 2012; (49): 25–34p.

Aid T. Evolutionary Sudoku Solver. 2011. http://www.scienceandatheism.com/wpcontent

Deng XQ, Li YD. A Novel Hybrid Genetic Algorithm for Solving Sudoku Puzzles. Optim Lett. 2011; 1–17p.

Hamnes DO, Julstrom BA. Iterated Mutation in an Evolutionary Algorithm for Sudoku. Proceedings of 26th IASTED International Conference on Artificial Intelligence and Applications. CA, USA: ACTA Press Anaheim; 2008; 272–7p.

Mantere T, Koljonen J. Solving and Rating Sudoku Puzzles with Genetic Algorithms. Proceedings of the 12th Finnish Artificial Intelligence Conference STeP. 2006; 86–92p.

Mantere T, Koljonen J. Solving, Rating and Generating Sudoku Puzzles with GA. Proceedings of the 2007 IEEE Congress on Evolutionary Computation. 2007; 1382–9p.

Mantere T, Koljonen, J. Solving and Analyzing Sudokus with Cultural Learning. Proceedings of the 2008 IEEE Congress on Evolutionary Computation; 1–6 Jun 2008; Hong Kong. 2008; 4053–60p.

Nicolau M, Ryan C. Solving Sudoku with the GAuGE System. Proceedings of 9th European Conference on Genetic Programming; 2006. 213-24p.

Moraglio A, Togelius J, Lucas S. Product Geometric Crossover for the Sudoku Puzzle. Proceedings of the IEEE Congress on Evolutionary Computing (CEC 2006). 2006; 476–83p.

Sato Y. Solving Sudoku with Genetic Operations that Preserve Building Blocks. Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games (CIG ’10). 2010; 23–9p.

Sato Y, Hasegawa N, Sato M. GPU Acceleration for Sudoku Solution with Genetic Operations. Proceedings of the IEEE Congress on Evolutionary Computation (CEC). Jun 2011; 296–303p.

SatoY, Hasegawa N, Sato M. Acceleration of Genetic Algorithms for Sudoku Solution on Many-Core Processors. Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. ACM Press; 2011; 407–14p.

Ardel DH. Genetic Algorithms and Genetic Programming at Stanford 1994. TOPE and Magic Squares, a Simple GA Approach to Combinatorial Optimization. In: Koza JR, editors. Genetic Algorithms in Stanford. Stanford, CA: Stanford Bookstore; 1994.

Alander JT, Mantere T, Pyylampi T. Digital Halftoning Optimization via Genetic Algorithms for Ink Jet Machine. In: Topping BHV, editors. DCMHPC; 1999; 211–6p.

Fonseca Jose B. The Magic Square as a Benchmark: Comparing MIP to improved GA and to a High Performance Minimax AI Algorithm.

Sandip B. MSc. Second Year Project. Dept. of Mathematics. IIT Bombay. (Technical Report).

Toyama F, Fujiki Y, Shoji K, et al. Assembly of Puzzles Using a Genetic Algorithm. IEEE International Conference on Pattern Recognition. 2002; 389–92p.

Dror S, Omid D, Nathan S. A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles. IEEE Conference on Computer Vision and Pattern Recognition. 2013; 1767–74p.

Khedkar AP, Subbaraman S. Novel Twin Operator for Genetic Algorithm. Proceedings of 3rd International Conference on Data Management and Advances in Computer Science and Engineering. 2010; 111–17p.

Khedkar AP, Subbaraman S. Effect of Advanced Twin Operator on the performance of Genetic Algorithm. IJERT. 2010; 3: 721–31p.

Khedkar AP, Subbaraman S. The Novel Approach of Adaptive Twin Probability for Genetic Algorithm. IJASCSE. 2013; 2(2): 31–7p.

Khedkar AP, Subbaraman S. Effectiveness of Novel GA with Advanced Twin Operator for Solving the Number Puzzles. IJARCET. 2014; 3(8): 2752–5p.

Kazemi SM, Fatemi B. A Retrievable Genetic Algorithm for Efficient Solving of Sudoku Puzzles. IJCISE. 2014; 8(5): 681–5p.

http://gpuzzles.com/quiz/hard-math-puzzles-with-answers/4




DOI: http://dx.doi.org/10.37591%2Fjoaira.v3i1.605

Refbacks

  • There are currently no refbacks.