Paper Info
Title
A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku.
Abstract
Membrane algorithmDisplay Omitted This paper proposes a new membrane algorithm based on rules of PSO defined within the framework of cell-like P-systems to solve Sudoku.A novel way is introduced to define the search space for solving the problem of Sudoku.Using the proposed algorithm the success rate for Sudoku puzzles of order 3 of \"easy\", \"medium\" and \"hard\" level is 100%.For \"Evil\" puzzles the success rate is however only 93% but it is the best ever recorded by any algorithm using PSO rules, as per the knowledge of the authors.Also, Sudoku of higher order is solved for which the success rate is about 87%. Sudoku, of order n, is a combinatorial puzzle having partially filled n2×n2 grid consisting of sub-grids of n×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.
Year
DOI
Venue
2016
10.1016/j.asoc.2016.03.020
Appl. Soft Comput.
Keywords
Field
DocType
Sudoku,Membrane algorithm,P-system,Particle Swarm Optimization
Particle swarm optimization,Mathematical optimization,Algorithm,Artificial intelligence,Grid,Machine learning,Mathematics,Mutation operator,P system
Journal
Volume
Issue
ISSN
45
C
1568-4946
Citations 
PageRank 
References 
5
0.41
7
Authors
2
Name
Order
Citations
PageRank
Garima Singh1161.74
Kusum Deep287682.14