title: A parallel algorithm for solving the n-queens problem based on inspired computational model.
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.
authors: College of Information, Shanghai Ocean University, Shanghai 201306, PR China.
authors: Zhaocai
authors: Z
authors: Wang
authors: College of Information, Shanghai Ocean University, Shanghai 201306, PR China. Electronic address: dmhuang@shou.edu.cn.
authors: Dongmei
authors: D
authors: Huang
authors: China Key Laboratory of Digital Earth, Center for Earth Observation and Digital Earth, Chinese Academy of Sciences, Beijing 100094, PR China. Electronic address: jtan1979@163.com.
authors: Jian
authors: J
authors: Tan
authors: College of Information, Shanghai Ocean University, Shanghai 201306, PR China.
authors: Taigang
authors: T
authors: Liu
authors: Academic Affair Office, Pingdingshan University, Pingdingshan 467000, PR China.
authors: Kai
authors: K
authors: Zhao
authors: Department of Civil Engineering, Xi'an University of Architecture & Technology, Xi'an 710055, PR China.
authors: Lei
authors: L
authors: Li
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D039301:Computers, Molecular; D005717:Games, Experimental
keywords: Adleman–Lipton model; DNA computation; NP-complete problem; The n-queens problem