A Novel Hybrid Flower Pollination Algorithm with Chaotic Harmony Search for Solving Sudoku Puzzles

Published Online March 2014 in MECS DOI: 10.5815/ijmecs.2014.03.05

min

Z = ZZ x4-45 'll x4-45| +Z i-1 j=1                j=1 i=1                k=1

Z X m ( l , m ) e B k

- ⁴⁵

Where x_i j is a cell at row i and column j , which has an integer value from 1 to 9; and B_k set of coordinates for block k . The first term in Equation 1 represents the penalty function for each horizontal row; the second term for each vertical column; and the third term for each block [2]. It should be noted that, although the sum of each row, each column, or each block equals 45, it does not guarantee that the numbers 1 through 9 are used exactly once. However, any violation of the uniqueness affects other row, column, or block which contains the wrong value jointly [2].

Harmony Search (HS) is an evolutionary algorithm, which mimics musicians’ behaviors, such as random play, memory-based play, and pitch-adjusted play when they perform. HS has proved to be a powerful tool for solving several optimization problems [22-32]. It does not need any mathematical calculations to obtain the optimal solutions. In recent years, HS was been applied to many optimization problems, demonstrating its efficiency compared to other heuristic algorithms and other Meta mathematical optimization techniques. Continuous development improvements to the algorithm and various applications to new types of problems (operations research, economy, computer science , civil engineering and electrical engineering), indicate that HS is a preferred choice. As a result of this, many studies have been proposed to increase its efficiency.

Sudoku puzzles in this research were formulated as an optimization problem with number-uniqueness penalties. In order to compare the performance of proposed algorithm and standard HS, proposed algorithm was applied to solving the Sudoku puzzles taken from Fig.1 (easy level) and Fig. 3 (hard level) of Geem [2] and it was found that the proposed algorithm in example1 takes time less than standard HS, it takes3 second after 76 function evaluations, but The standard HS takes 285 function evaluations, taking 9 seconds. In example 2 the proposed algorithm takes 6 second after 237 function evaluations with the penalty of 0 but standard harmony search entrapped in one of local optima with the penalty of 14 after 1,064 function evaluations.

This paper is organized as follows: after introduction, Literature review of Sudoku is shortly displayed. In section 3, the Flower Pollination Algorithm briefly introduced. In section 4, the harmony search is briefly introduced. In section 5, the proposed algorithm is described, while the results are discussed in section 6. Finally, conclusions and future work are presented in section 7.

• II.    Literature review of solution techniques for