A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku

摘要

Sudoku, of order n, is a combinatorial puzzle having partially filled n(2) x n(2) grid consisting of sub-grids of n x n dimension. In this paper, a new membrane algorithm, namely MA_PSO_M, is presented. It uses the modified rules of Particle Swarm Optimization coupled with a carefully designed mutation operator within the framework of cell-like P-systems. Another significant contribution of this paper is the novel way in which the search space for solving the Sudoku problem is defined. Initially, the proposed algorithm is used to solve Sudoku puzzles of order 3 available in literature. On the basis of experiments performed on sample Sudoku puzzles of 'easy' and 'medium' difficulty levels it is concluded that the proposed membrane algorithm, MA_PSO_M, is very efficient and reliable. For the 'hard' and 'evil' difficultly levels, too the algorithm performs very well after incorporating an additional deterministic phase. The performance of the algorithm is further enhanced with an increased population size in a very small computational time. To further demonstrate efficiency of algorithm it is applied to Sudoku puzzles of order 4. The obtained results prove that the proposed membrane algorithm clearly dominates any of the PSO based membrane algorithm existing in the literature. (C) 2016 Elsevier B.V. All rights reserved.