Jun Zhang; Zili Zhang

An Algebraic Method for the N-Queens Problem Based on Permutation Operation Group

Full Text (PDF, 143KB), PP.19-25

Views: 0 Downloads: 0

Author(s)

1. State Key Laboratory of Digital Manufacturing Equipment and Technology of China, Huazhong University of Science and Technology, Wuhan 430074, PR China

2. Hubei Province Key Laboratory of Intelligent Robot, Wuhan Institute of Technology, Wuhan 430073, PR China

3. Shenzhen Graduate School, Harbin Institute of Technology, Shenzhen, 518055, PR China

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2011.03.03

Received: 2 Nov. 2010 / Revised: 17 Jan. 2011 / Accepted: 25 Feb. 2011 / Published: 8 Apr. 2011

Index Terms

N-Queens problem, Permutation operations, Orbit operations, Orbit signature, Search algorithm

Abstract

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 in orbit space. A search algorithm based on orbit signature is presented, and finally the effectiveness of the algorithm is illustrated by an example.

Cite This Paper

Jun Zhang, Zili Zhang, "An Algebraic Method for the N-Queens Problem Based on Permutation Operation Group", International Journal of Computer Network and Information Security(IJCNIS), vol.3, no.3, pp.19-25, 2011. DOI:10.5815/ijcnis.2011.03.03

Reference

[1]I. Rivin, I. Vardi, P. Zimmermann. The n-queens problem, Amer. Math. Monthly 101 (1994)629-639.
[2]J.S. Rohl, A faster lexicographical n-queens algorithm. Inform. Process. Lett. 17(1983)231-233.
[3]Rok Sosic, Jun Gu. A polynomial time algorithm for the NQueens problem. SIGART Bulletin, 1(3)(1990)7-11.
[4]Sosich R., Gu J. Fast search algorithms for the N-queens problem. IEEE Transactions on System, Man, and Cybernetics 21(6)(1991)1572-1576.
[5]K. Kise, T. Katagiri, H. Honda, T. Yuba. Solving the 24-queens problem using MPI on a PC cluster. Technical Report UEC-IS-2004-6, Graduate School of Information Systems, The University of Electro-Communication, June 2004.
[6]Jordan Bell, Brett Stevens. A survey of known results and research areas for n-queens. Discrete Mathematics 309(2009) 1-31.
[7]S.P. Nudelman. The modular n-queens problem in higher dimensions. Discrete Math. 146(1-3) (1995)159-167.
[8]M. Vasquez. New result on the queens n2 graph coloring problem. J. Heuristics, 10(2004)407-413.
[9]Zhang Dakun. One eighth rule in N-queens problem based on group theory and morphological gene combinations. International Forum on Information Technology and Applications (2009) 651-654.
[10]P. Cull, R. Pandey. Isomorphism and the n-queens problem. SIGCSE Bull. 26(3)(1994) 29-36.
[11]A.P. Burger, C.M. Mynhardt. An upper bound for the minimum number of queens covering the n×n chessboard. Discrete Applied Math. 121(2002)51-60.
[12]A.P. Burger, C.M. Mynhardt. An improved upper bound for queens domination numbers. Discrete Math. 266(2003)119-131.
[13]Matthias R. Engelhardt. A group-based search for solutions of the n-queens problem. Discrete Mathmematics 307(2007) 2535-2551.
[14]Zsuzsanna Szaniszlo, Maggy Tomova, Cindy Wyels. The N-queens problem on a symmetric Toeplitz matrix. Discrete Math. 309(2009)969-974.
[15]C. Erbas, S. Sarkeshik, M.M. Tanik. Different perspectives of the n-queens problem. in: Proceedings of the 1992 ACM Annual Conference on Communication, ACM Press, 1992, pp.99-108.
[16]A. Panayotopoulos. Generating stable permutations. Discrete Math. 62(2) (1986) 219-221.
[17]M.A. Armstrong. Groups and symmetry. Springer-Verlag New York Inc., 1988.

International Journal of Computer Network and Information Security (IJCNIS)