Solution and Level Identification of Sudoku Using Harmony Search
Автор: Satyendra Nath Mandal, Saumi Sadhu
Журнал: International Journal of Modern Education and Computer Science (IJMECS) @ijmecs
Статья в выпуске: 3 vol.5, 2013 года.
Бесплатный доступ
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.
Sudoku, Harmony search, Time complexity, Level of Sudoku, Probability metric
Короткий адрес: https://sciup.org/15014532
IDR: 15014532
Текст научной статьи Solution and Level Identification of Sudoku Using Harmony Search
Published Online April 2013 in MECS DOI: 10.5815/ijmecs.2013.03.07
Harmony Search.(HS) algorithm is popularly known as music –inspired Harmony Search algorithm because it was first improvised by the jazz musicians to promote better solution in musical instrument rather than the existing ones([1],[16]). Basically, the aim of musicians was to search for a perfect state of harmony. Here, musicians tried to polish their pitches in order to obtain a better harmony. As the pitches played by ensemble instruments determine the aesthetic beauty, the set of values assigned for decision variables determines the evaluation function. The objective function is improved by using more and more iterations as more and more practices improve the sound quality.
The harmony Search algorithm is the improvisation process of musicians, there is an analogy between them. Each musicians playing different instruments corresponds to each decision variable (x1,x2…) and the range of each music instrument corresponds to the range of each decision variable. Musicians improvise three possible ways-1. Playing some tune from memory.2. Playing some similar tunes from memory by adjusting slightly the pitches.3. Playing random note. In this way, they improvise the harmony of instrument. If the present harmony is better than the existing one then new one is kept in memory and repeats the entire process for obtaining better harmony.
The Probability Metric is the decimal number within the section (0, 1) and is used to describe the required probability to solve the level of Sudoku problem[2]. Thus 0 indicates Level1 and 1 represents Level 5.The varying ranges of probability within range (0, 1) is used for defining varying level of Sudoku. Thus we can define quickly and adequately any grade of difficulty of any given Sudoku problem to us using probability metric approach with the help of Harmony search algorithm.
The paper is divided into the following sections. In third section, the Sudoku puzzle, difficulty level and concept of Probability metric are defined. The proposed algorithm is given in section 3.The algorithm is implemented in section 4.The result and conclusion are furnished at section 5 and 6.Finally, the related references are given at last section.
-
II. THEORY
-
A. Sudoku Puzzle
Sudoku puzzle ( [1]-[3],[[5]-[7],[15]-[16]) consists of 9*9 grid and 3*3 blocks for all 81 cells. Each puzzle, which has unique solution, has some cells that have already been filled in. The objective of the puzzle is to fill the remaining blank cells with the value 1 through 9 by maintaining the following 3 constraints.1).Each horizontal row should contain value within 1 through 9 without repeating any.2).Each vertical column should contain value within 1 through 9 without repeating any.3).Each block should contain value from 1 to 9 without any repetition.
In other words, the problem can be formulated as an optimization problem as follows:
9 9 9 9 9
Minimize z= ∑ | ∑ x(i, j)-45|+ ∑ | ∑ x(i, j)-45| + ∑ | ∑ x(l, m) - 45| (1)
i=1i=1 j=1 i=1 k=1 (l, m)ЄB(k)
where xij = cell at row i and column j , which has integer value from 1 to 9; and
Bk = set of coordinates for block k .
-
B. Sudoku and Solution
The Sudoku and corresponding its solution are furnished in Fig 1 and Fig 2.
|
5 |
3 |
6 |
7 |
|||||
|
8 |
5 |
2 |
4 |
|||||
|
9 |
8 |
4 |
2 |
6 |
3 |
|||
|
9 |
1 |
3 |
2 |
6 |
||||
|
3 |
||||||||
|
5 |
7 |
2 |
6 |
9 |
8 |
|||
|
4 |
5 |
9 |
3 |
8 |
||||
|
1 |
5 |
7 |
2 |
|||||
|
8 |
1 |
4 |
7 |
Figure 1. Sudoku
|
2 |
5 |
4 |
3 |
1 |
6 |
8 |
9 |
7 |
|
7 |
6 |
3 |
9 |
8 |
5 |
1 |
2 |
4 |
|
1 |
9 |
8 |
4 |
2 |
7 |
6 |
5 |
3 |
|
9 |
8 |
1 |
7 |
5 |
3 |
2 |
4 |
6 |
|
6 |
3 |
2 |
8 |
4 |
9 |
7 |
1 |
5 |
|
5 |
4 |
7 |
2 |
6 |
1 |
9 |
3 |
8 |
|
4 |
7 |
5 |
6 |
9 |
2 |
3 |
8 |
1 |
|
3 |
1 |
9 |
5 |
7 |
8 |
4 |
6 |
2 |
|
8 |
2 |
6 |
1 |
3 |
4 |
5 |
7 |
9 |
Figure 2. Sudoku Solution
-
C. Harmony Search Parameters
In harmony search algorithm, many parameters have been used. They have been defined as follows
-
1) HMS ( Harmony memory Size)- It defines the size of the harmony memory. It is generally varies from 1 to 100. (typical value = 30)
-
2) HMCR ( Harmony memory considering rate) - It defines the rate of choosing a value from the harmony memory. It generally varies from 0.7 to 0.99. (typical value = 0.9)
-
3) PAR ( Pitch Adjustment Rate)- It shows the rate of choosing a neighboring value. It is generally varies from 0.1 to 0.5. (Typical value = 0.3)
-
4) Memory Initialization - The harmony memory matrix is initially filled with randomly generated solution vectors within the defined range.
-
D. Difficulty level of Sudoku
Difficulty level of Sudoku has been determined by its time complexity i.e. the more computational time is required to solve the Sudoku. Basically, depending upon difficulty and as per research, there are five difficulty level in Sudoku. The five difficulty levels have been defined as
Level 1- Ultra Easy
Level 2- Easy
Level 3- Medium
Level 4- Hard
Level 5- Evil.
-
E. Terminologies of Probability Metric
The different terminology in probability metrics are as follows
-
1) Valid Node (V) – The attempt to solve the Sudoku is represented as tree. The nodes through which incomplete Sudoku puzzle is solved are known as valid node (V). In this paper, the harmony search algorithm has been used to solve Sudoku, the number of valid node of Sudoku is counted from the maximum iteration which is needed to solve of a given Sudoku.
-
2) Invalid Node (IV) – The nodes though which incomplete puzzle cannot be solved is known as invalid node (IV). In this paper, the harmony search algorithm has been used to solve Sudoku; the number of invalid node (IV) of Sudoku is counted from the wrong entry after applying the equation 1 and equation 2 in proposed algorithm to fill up the Sudoku. The summation of wrong entries is known as Invalid node.
-
3) Success Rating (SR):
∑Value (V) ∕ ﴾∑Value (V) +∑Value (IV) ﴿
-
4) Difficulty Coefficient (DC) - Difficulty Coefficient is used to define the range of probability value for different difficulties levels. It is defined as
DC=(1-SC).The different probabilities ranges are furnished in Table I.
TABLE I. THE LEVEL OF SUDOKU AND ITS DIFFICULTY COEFFICIENT VALUE
|
Level |
Level1 |
Level2 |
Level3 |
Level4 |
Level5 |
|
DC Value |
0 |
0-0.5 |
0.5 0.75 |
0.750.9 |
0.9-1 |
-
III. PROPOSED ALGORITHM
Name -Solution and Level Identification of Sudoku (SLIS)
Input – Sudoku Problem
Output - Sudoku solution with level of Sudoku
Method:
Step 1: a) To divide Sudoku into 9 , 3X3 blocks starting from upper left corner.
-
b) To choose a cell randomly from incomplete Sudoku.
Step 2: To put any number from 1 to 9 which is not present in the corresponding row, Column or block.
Step 3: If more than one number is available, then the value of the cell will be calculated by the equation no 1.
x’(ij) <- x(lower) + (HMCR).(x(upper)-x(lo wer)). (1)
Step 4: To repeat step 2 and step 3 until all value of the corresponding cells will be filled up.
Step 5: If any number is repeated after step 4 in same row, same column or the same block, the new value is calculated by 2(a) and 2(b)
X”(i.j) + x'(ij) + HMCR*PAR*0.5 (2a)
X”(ij) ^ x'(ij) - HMCR*PAR*0.5 (2b)
Step 6 : To repeat step 5 until ,the selected cell will get the suitable value.
Step 7 : To repeat step 5 and step 6 to replace all duplications in each cell.
Step 8 : To find the maximum number of iterations to solve the Sudoku and assign it as valid node of a given Sudoku.
Step9 . To find the invalid node by summing up the invalid entry after the equation 1 and 2.
Step10 . To calculate Success Rating (SR) by following equation.
SR = ∑Value(V) ∕ ﴾∑Value(V)+∑Value(IV) (3)
Step11 . To calculate Difficulty Co-efficient by following equation
DC = 1-SR (4)
Step12 . To determine the level of Sudoku by using the given conditions.
If DC is 0, Then Level1
Else If DC is within range(0 to 0.5),Then Level2
Else If DC is within range(0.5 to 0.75),Then Level3
Else If DC is within range(0.75 to 0.9),Then Level4
Else DC is within range(0.9 to 1),Then Level5
Step13 : End.
-
IV. IMPLEMENTATION
The algorithm has been implemented using a Sudoku. The steps have been taken to solve Sudoku as follows
Step 1. One Sudoku has been taken and is furnished in Fig 3.
|
5 |
3 |
6 |
7 |
|||||
|
8 |
5 |
2 |
4 |
|||||
|
9 |
8 |
4 |
2 |
6 |
3 |
|||
|
9 |
1 |
3 |
2 |
6 |
||||
|
3 |
||||||||
|
5 |
7 |
2 |
6 |
9 |
8 |
|
4 |
5 |
9 |
3 |
8 |
||||
|
1 |
5 |
7 |
2 |
|||||
|
8 |
1 |
4 |
7 |
Figure 3. Sudoku
Step 2.
The parameters of harmony algorithm have been assigned as HMS = 40, HMCR = 0.8, and PAR = 0.5.
Step 3. The vacant cells of Sudoku have been filled up by equation 1. .
1=x(lower),7=x(upper).In this way , the 40 remaining cells have been filled up and they have been furnished in Fig. 4.
|
1.8 |
5 |
3.6 |
3 |
1 |
6 |
6.6 |
9 |
7 |
|
5.8 |
6.8 |
5.4 |
8.6 |
8 |
5 |
5.8 |
2 |
4 |
|
5.8 |
9 |
8 |
4 |
2 |
5.8 |
6 |
4.2 |
3 |
|
9 |
7.2 |
1 |
7.8 |
4.8 |
3 |
2 |
4.8 |
6 |
|
5.2 |
3 |
5.2 |
8.4 |
4.8 |
7.4 |
7.2 |
1 |
5 |
|
5 |
4 |
7 |
2 |
6 |
1 |
9 |
3.8 |
8 |
|
4 |
6 |
5 |
6.8 |
9 |
1.8 |
3 |
8 |
1 |
|
5.8 |
1 |
7.8 |
5 |
7 |
8 |
7.2 |
8.4 |
2 |
|
8 |
5.2 |
7.6 |
1 |
3 |
4 |
5 |
7 |
8.2 |
Figure 4. Fill up vacant cell
Step 4.
The value of all vacant cells of Fig 4 should be changed in integer value. The value of the cells that have been changed by equation 2 is shown in Fig 5.
Suppose, the value of cell(2,1) has been considered. The floating value of cell (2,1) should be replaced by any available value of the corresponding cell i.e 1,3,6,7. As per the Fig 3, value 1 is to be calculated by using equation 2. The required number of iterations to compute 1 from 5.8 is (5.8-1)/(0.8*0.5*0.5)=24 .The pink color shows that the respective cell value has been appeared either in the same row or same column or same block.. Green color cell shows the value is fixed and final for that cell after the iteration.
|
2 |
5 |
4 |
3 |
1 |
6 |
8 |
9 |
7 |
|
1 |
7 |
3 |
7 |
8 |
5 |
1 |
2 |
4 |
|
1 |
9 |
8 |
4 |
2 |
7 |
6 |
5 |
3 |
|
9 |
8 |
1 |
7 |
4 |
3 |
2 |
4 |
6 |
|
2 |
3 |
2 |
7 |
4 |
7 |
4 |
1 |
5 |
|
5 |
4 |
7 |
2 |
6 |
1 |
9 |
3 |
8 |
|
4 |
6 |
5 |
6 |
9 |
2 |
3 |
8 |
1 |
|
3 |
1 |
3 |
5 |
7 |
8 |
4 |
6 |
2 |
|
8 |
2 |
2 |
1 |
3 |
4 |
5 |
7 |
9 |
Figure 5. The updated cell value by equation 2.
Step 5.
The value in cell x(2,1) has been repeated in cell x(3,1).so generate 3 from 1 using equation 2 is shown in Fig.6 . The required number of iterations is=(3-1)/(0.8*0.5*0.5)=10 .
|
2 |
5 |
4 |
3 |
1 |
6 |
8 |
9 |
7 |
|
3 |
6 |
6 |
9 |
8 |
5 |
1 |
2 |
4 |
|
1 |
9 |
8 |
4 |
2 |
7 |
6 |
5 |
3 |
|
9 |
8 |
1 |
7 |
5 |
3 |
2 |
4 |
6 |
|
6 |
3 |
6 |
8 |
4 |
9 |
7 |
1 |
5 |
|
5 |
4 |
7 |
2 |
6 |
1 |
9 |
3 |
8 |
|
4 |
7 |
5 |
6 |
9 |
2 |
3 |
8 |
1 |
|
3 |
1 |
9 |
5 |
7 |
8 |
4 |
6 |
2 |
|
8 |
6 |
6 |
1 |
3 |
4 |
5 |
7 |
9 |
Figure 6. The updated cell value using equation 2
Step 6.
To change the value of cell (2,1) from 3 to 7 by using equation 2 as 3 has been repeated in cell (8,1) is shown in Fig 7. The required number of iterations is 20.
|
2 |
5 |
4 |
3 |
1 |
6 |
8 |
9 |
7 |
|
7 |
6 |
3 |
9 |
8 |
5 |
1 |
2 |
4 |
|
1 |
9 |
8 |
4 |
2 |
7 |
6 |
5 |
3 |
|
9 |
8 |
1 |
7 |
5 |
3 |
2 |
4 |
6 |
|
6 |
3 |
2 |
8 |
4 |
9 |
7 |
1 |
5 |
|
5 |
4 |
7 |
2 |
6 |
1 |
9 |
3 |
8 |
|
4 |
7 |
5 |
6 |
9 |
2 |
3 |
8 |
1 |
|
3 |
1 |
9 |
5 |
7 |
8 |
4 |
6 |
2 |
|
8 |
2 |
6 |
1 |
3 |
4 |
5 |
7 |
9 |
Figure 7. Solution
So for cell x (2, 1) total no of iteration is=54
iterations
Step 7. Step 4 to step 7 have been repeated for all remaining cell.
Step 8. Computation of valid node
Here, number of iterations has been computed to solve the given Sudoku is given in Table II. From Table II, it has been observed that the maximum number of iteration is 57. As per proposed algorithm the value of valid node (V) is 57.
TABLE II. NUMBER OF ITERATIONS
|
X(1,1) |
2 |
X(1,3) |
3 |
X(1,5) |
1 |
X(1,7) |
8 |
|
X(5,5) |
5 |
X(2,2) |
7 |
X(2,3) |
43 |
X(2,4) |
19 |
|
X(3,1) |
26 |
X(3,6) |
2 |
X(3,8) |
5 |
X(4,2) |
5 |
|
X(4,4) |
6 |
X(4,5) |
10 |
X(4,8) |
5 |
X(5,1) |
37 |
|
X(5,3) |
57 |
X(5,4) |
13 |
X(5,5) |
5 |
X(5,6) |
13 |
|
X(5,7) |
32 |
X(5,9) |
1 |
X(6,2) |
1 |
X(6,6) |
1 |
|
X(6,8) |
5 |
X(7,2) |
44 |
X(7,4) |
5 |
X(7,9) |
2 |
|
X(8,1) |
1 |
X(8,7) |
17 |
X(8,8) |
13 |
X(9,2) |
57 |
|
X(9,3) |
50 |
X(9,5) |
1 |
X(9,7) |
1 |
X(9,9) |
5 |
Step 9. Computation of invalid node (IV), Success Rating (SR) and Difficulty Coefficient (DC)
In Fig 3 and Fig 4, the numbers in purple color cells have been taken as invalid node as they are not valid cells. The cells have been removed by equation 1 and 2. To solve the Sudoku, the control must be returned from invalid node. For this reason, the value of invalid node has been multiplied by 2.
The success rating has been calculated as
SR=(57*1)/((57*1)+(23*2))=0.55
Finally, the difficulty parameter has been calculated below
DC=1-SR=1-0.55=0.45.
From the Table 1, it has been observed that the given Sudoku is in level 2.
-
V. RESULT
Form Table 2, it has been observed that the maximum number of iteration to solve the Sudoku is 57. The same Sudoku has been solved by Zong Woo Geem[1], he has used maximum iteration is 285. The maximum number if iteration has been computed with different values of parameters of harmony search is furnished in Table III.
TABLE III. MAXIMUM NUMBER OF ITERATIONS WITH DIFFERENT HMCR AND PAR
|
HMCR |
PAR |
No. Of Iteration |
|
0.9 |
0.5 |
50 |
|
0.8 |
0.5 |
57 |
|
0.7 |
0.5 |
62 |
|
0.6 |
0.5 |
70 |
|
0.5 |
0.5 |
80 |
|
0.4 |
0.5 |
96 |
|
0.3 |
0.5 |
122 |
|
0.2 |
0.5 |
176 |
The different Sudoku, valid node, in valid node, success rate, difficulty parameter and finally, level of Sudoku have been furnished in Table 4. The different types of Sudoku have been furnished from Fig 8 to Fig
TABLE 4. LEVEL OF SUDOKU
|
Sudoku No |
Valid Node |
Invalid Node |
Success Rating |
Diffi culty Para meter |
Level of Sudoku |
|
1 |
14 |
0 |
1 |
0 |
1 |
|
2 |
97 |
90 |
0.35 |
0,65 |
3 |
|
3 |
250 |
708 |
0.15 |
0.85 |
4 |
|
4 |
370 |
1710 |
0.1 |
0.91 |
5 |
-
VII. CONCLUSION AND FUTURE WORK
In this paper, the better result i.e. minimum numbers of iterations have been computed as compare with paper [1] in same Sudoku. The level of Sudoku has been identified by calculating the value of valid node, invalid node, and success rate and difficulty parameters. These terms have been redefined based on harmony search. The proposed algorithm has been provided the better and clear way to find the all difficulty level of any given Sudoku. The number of iterations to solve Sudoku will be reduced in future and other optimization techniques will be used to solve Sudoku.
Список литературы Solution and Level Identification of Sudoku Using Harmony Search
- 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.
- 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.
- Greg Shalless,"-www.sudoku-help.com 2006. Obtain at http:// www.sudoku-help.com/Solving-Rules.htm, date of access 10.10.2012
- Bill & Woodcock,Jim Millennial, "Perspectives in Computer Science", Proceedings of Oxford-Microsoft symposium in honor of sir Tony Hoare,Palgrave, pp. 187-214,1999 .
- Gordon Royle, "Minimum Sudoku". http://people.csse.uwa.edu.au/gordon/sudokumin.php, date of access 10.10.2012
- 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.
- 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
- 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.
- Denis Berthier," The Hidden Logic of Sudoku", (Second Edition), available at http://www.carva.org/denis.berthier, date of access 10.10.2012
- STUART A., "The Logic of Sudoku", Michael Mepham Publishing, 2007. date of access 10.10.2012
- 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
- 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
- Eppstein, D." Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku", ACMComputing Research Repository. Cs.DS/0507053,2005.
- 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
- 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
- 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.
