Skip navigation
Please use this identifier to cite or link to this item: http://repository.iitr.ac.in/handle/123456789/9860
Title: A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku
Authors: Singh G.
Deep, K.
Published in: Applied Soft Computing Journal
Abstract: 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. © 2016 Elsevier B.V. All rights reserved.
Citation: Applied Soft Computing Journal (2016), 45(): 27-39
URI: https://doi.org/10.1016/j.asoc.2016.03.020
http://repository.iitr.ac.in/handle/123456789/9860
Issue Date: 2016
Publisher: Elsevier Ltd
Keywords: Membrane algorithm
P-system
Particle Swarm Optimization
Sudoku
ISSN: 15684946
Author Scopus IDs: 57209060608
8561208900
Author Affiliations: Singh, G., Department of Mathematics, Indian Institute of Technology Roorkee, Roorkee, 247667, India
Deep, K., Department of Mathematics, Indian Institute of Technology Roorkee, Roorkee, 247667, India
Funding Details: The first author would like to express her appreciation to Ministry of Human Resource Development, Government of India for funding this research work under Grant No. MHRD02-23-200-304 . The authors are thankful to reviewers for their valuable comments.
Corresponding Author: Singh, G.; Department of Mathematics, Indian Institute of Technology RoorkeeIndia; email: garimachauhan.iitr@gmail.com
Appears in Collections:Journal Publications [MA]

Files in This Item:
There are no files associated with this item.
Show full item record


Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.