International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 5, No. 3, 8 Mar. 2013
Cover page and Table of Contents: PDF (size: 472KB)
Solution and Level Identification of Sudoku Using Harmony Search
Full Text (PDF, 472KB), PP.49-55
Views: 0 Downloads: 0
Author(s)
Index Terms
Sudoku, Harmony search, Time complexity, Level of Sudoku, Probability metric
Abstract
Different optimization techniques have been used to solve Sudoku. Zong Woo Geem have applied harmony search in Sudoku to get better result. He has taken a Sudoku and time complexity has been optimized by different values of parameters. But, he has not given way of solution in details. He has also not given any idea to recognize the level of Sudoku. In this paper, an algorithm has been proposed based on harmony search to solve and identify the Sudoku efficiently. It has been observed that time complexity i.e. the maximum number of iteration has been reduced by choosing appropriate parameter values. The level of Sudoku has also been identified using probability metric. Finally, the number of iterations has been calculated with different values of parameters and the level of different Sudoku has been identified.
Cite This Paper
Satyendra Nath Mandal, Saumi Sadhu, "Solution and Level Identification of Sudoku Using Harmony Search", International Journal of Modern Education and Computer Science (IJMECS), vol.5, no.3, pp.49-55, 2013. DOI:10.5815/ijmecs.2013.03.07
Reference
[1]Zong Woo Geem,”Harmony Search algorithm for solving sudoku” ,Proceedings of the 11th international conferences, KES 2007 and XVII Italian workshop on neural networks conferences on knowledge based intelligent information and engineering system.Part1,pp.371-378,2007.
[2]Faculty: du duo, fan ye, Zhu Jing,”Creating Sudoku, Creative Method”, 2008 MCM/ICM award , available at www.sx.nchu.edu.cn/niatweb/papers/ 20MCM/08b.pdf, date of access 12.11.2012.
[3]Greg Shalless,”-www.sudoku-help.com 2006. Obtain at http:// www.sudoku-help.com/Solving-Rules.htm, date of access 10.10.2012
[4]Bill & Woodcock,Jim Millennial, “Perspectives in Computer Science”, Proceedings of Oxford-Microsoft symposium in honor of sir Tony Hoare,Palgrave, pp. 187-214,1999 .
[5]Gordon Royle, “Minimum Sudoku”. http://people.csse.uwa.edu.au/gordon/sudokumin.php, date of access 10.10.2012
[6]Timo Mantere and Janne Koljonen, “Solving, Rating and Generating Sudoku Puzzle with GA. IEEE Congress on Evolutionary Computation, pp 1382-1389, 25-28 Sept. 2007.
[7]Alberto Moraglio, Julian Togelius and Simon Lucas, “Product Geometric Crossover for the Sudoku Puzzle”, Proceedings of the IEEE Congress on Evolutionary Computation, 2006, available at. http://privatewww.essex.ac.uk/~amoragn/sudoku.pdf
[8]Todd K. Moon and Jacob H. Gunther. Multiple Constraint Satisfaction by Belief Propagation: An Example Using Sudoku. Utah State University. Adaptive and Learning Systems, 2006 IEEE Mountain Workshop, pp. 122-126, 24-26 July 2006.
[9]Denis Berthier,” The Hidden Logic of Sudoku”, (Second Edition), available at http://www.carva.org/denis.berthier, date of access 10.10.2012
[10]STUART A., “The Logic of Sudoku”, Michael Mepham Publishing, 2007. date of access 10.10.2012
[11]RUSSELL E. and JARVIS F.,” There are 5472730538 essentially different Sudoku grids … and the Sudoku symmetry group”, available at http://www.afjarvis.staff.shef.ac.uk/sudoku/sud group.html, 2005, date of access 10.10.2012
[12]YATO T. and SETA T., “Complexity and completeness of finding another solution and its application to puzzles”, IPSG SIG Notes 2002-AL-87-2, available at http://www-imai.is.s.u-tokyo. ac.jp/~yato/data2/SIGAL87-2.pdf, 2002, date of access 10.10.2012
[13]Eppstein, D.” Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku”, ACMComputing Research Repository. Cs.DS/0507053,2005.
[14]Caine, A. and Cohen, R.” A Mixed-Initiative Intelligent Tutoring System for Sudoku”. In: Lamontagne,L., Marchand, M. (eds.) Canadian AI 2006. LNCS (LNAI), vol. 4013, pp. 550–561. Springer, Heidelberg, 2006
[15]Nicolau, M. and Ryan, C.,” Solving Sudoku with the GAuGE System”,. In: Collet, P., Tomassini,M., Ebner, M., Gustafson, S., Ekárt, A. (eds.) EuroGP 2006. LNCS, vol. 3905, pp. 213–224. Springer, Heidelberg,2006
[16]Satyendra Nath Mandal and Soumi Sadhu,” An Efficient Approach to Solve Sudoku Problem by Harmony Search Algorithm”, International Journal of Engineering Sciences, Vol 4, pp 312-323, 2011.