An Orbit-Based Search Algorithm to Solve N-Queens Problem
Jun Zhang, Zi Li Zhang · Applied Mechanics and Materials · 2012
To analyze N-Queens problem in permutation space, this paper defines isomorphic operations of permutation to dihedral group D4. With these operations to find elements within an orbit, two operations on orbits are also defined to generate new orbit from existing ones. Orbit signature is proposed to uniquely identify different orbits on orbit space. A search algorithm based on orbit signature is presented, and finally the effectiveness of the algorithm is illustrated by an example.