A parallel algorithm for solving the n-queens problem based on inspired computational model. (May 2015)

• Record Type: Journal Article
• Authors: Wang, Zhaocai; Huang, Dongmei; Tan, Jian; Liu, Taigang; Zhao, Kai; Li, Lei
• Is Part Of: Bio systems. Volume 131(2015:May)
• Page Start: 22
• Page End: 29
• Publication Date: 2015-05
• Subjects: DNA computation -- The n-queens problem -- Adleman–Lipton model -- NP-complete problem; Biological systems -- Periodicals; Biology -- Periodicals; Biology -- Periodicals; Evolution -- Periodicals; Biologie -- Périodiques; Évolution -- Périodiques; 570
• DOI: 10.1016/j.biosystems.2015.03.004
• Languages: English
• ISSNs: 0303-2647

Abstract

Abstract: DNA computing provides a promising method to solve the computationally intractable problems. The n -queens problem is a well-known NP-hard problem, which arranges n queens on an n × n board in different rows, columns and diagonals in order to avoid queens attack each other. In this paper, we present a novel parallel DNA algorithm for solving the n -queens problem using DNA molecular operations based on a biologically inspired computational model. For the n -queens problem, we reasonably design flexible length DNA strands representing elements of the allocation matrix, take appropriate biologic manipulations and get the solutions of the n -queens problem in proper length and O ( n 2 ) time complexity. We extend the application of DNA molecular operations, simultaneity simplify the complexity of the computation and simulate to verify the feasibility of the DNA algorithm.