A parallel algorithm for solving the n-queens problem based on inspired computational model. (May 2015) - Wang, Zhaocai; Huang, Dongmei; Tan, Jian; Liu, Taigang; Zhao, Kai; Li, Lei
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.