An Algebraic Method for the N-Queens Problem Based on Permutation Operation Group
Автор: Jun Zhang, Zili Zhang
Журнал: International Journal of Computer Network and Information Security(IJCNIS) @ijcnis
Статья в выпуске: 3 vol.3, 2011 года.
Бесплатный доступ
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.
N-Queens problem, Permutation operations, Orbit operations, Orbit signature, Search algorithm
Короткий адрес: https://sciup.org/15011018
IDR: 15011018
Список литературы An Algebraic Method for the N-Queens Problem Based on Permutation Operation Group
- I. Rivin, I. Vardi, P. Zimmermann. The n-queens problem, Amer. Math. Monthly 101 (1994)629-639.
- J.S. Rohl, A faster lexicographical n-queens algorithm. Inform. Process. Lett. 17(1983)231-233.
- Rok Sosic, Jun Gu. A polynomial time algorithm for the NQueens problem. SIGART Bulletin, 1(3)(1990)7-11.
- Sosich R., Gu J. Fast search algorithms for the N-queens problem. IEEE Transactions on System, Man, and Cybernetics 21(6)(1991)1572-1576.
- 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.
- Jordan Bell, Brett Stevens. A survey of known results and research areas for n-queens. Discrete Mathematics 309(2009) 1-31.
- S.P. Nudelman. The modular n-queens problem in higher dimensions. Discrete Math. 146(1-3) (1995)159-167.
- M. Vasquez. New result on the queens n2 graph coloring problem. J. Heuristics, 10(2004)407-413.
- 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.
- P. Cull, R. Pandey. Isomorphism and the n-queens problem. SIGCSE Bull. 26(3)(1994) 29-36.
- 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.
- A.P. Burger, C.M. Mynhardt. An improved upper bound for queens domination numbers. Discrete Math. 266(2003)119-131.
- Matthias R. Engelhardt. A group-based search for solutions of the n-queens problem. Discrete Mathmematics 307(2007) 2535-2551.
- Zsuzsanna Szaniszlo, Maggy Tomova, Cindy Wyels. The N-queens problem on a symmetric Toeplitz matrix. Discrete Math. 309(2009)969-974.
- 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.
- A. Panayotopoulos. Generating stable permutations. Discrete Math. 62(2) (1986) 219-221.
- M.A. Armstrong. Groups and symmetry. Springer-Verlag New York Inc., 1988.
