The week's pick
Reseach Article
A Novel Double Backtracking Approach to the N-Queens Problem in Three Dimensions
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 169 - Number 5 |
| Year of Publication: 2017 |
| Authors: Abhijith Chakiat, Akhil Sudhakaran, Abhinav A. Nair, Pallavi Venkatesh |
10.5120/ijca2017914749
|
Abhijith Chakiat, Akhil Sudhakaran, Abhinav A. Nair, Pallavi Venkatesh . A Novel Double Backtracking Approach to the N-Queens Problem in Three Dimensions. International Journal of Computer Applications. 169, 5 ( Jul 2017), 1-5. DOI=10.5120/ijca2017914749
Abstract
A well-known classic chessboard problem is that of placing N Queens on an N X N chessboard such that no two queens are able to attack each other (A Queen can attack in any direction, either in the same row, column or even diagonal). This is further generalized to three dimensions (N X N X N cube). An implementation of double backtracking algorithm to generate solutions for a certain value of N in a three dimensional space is discussed in this paper. The approach finds all the two dimensional solutions for a given N and records these. These two dimensional solutions are then stacked on top of one another such that no queen is present vertically on the same line as another queen. This builds up the three dimensional solution from the entire two dimensional solution set, picking one by one, using the general back tracking algorithm, with the constraint that no queen can attack another queen in the same plane, i.e same row, column or even diagonal, and no queen can attack another queen vertically on the same line across the planes of the cube constructed.
References
- F.W.M. Bezzel. Proposal of eight queens problem. Berliner Schachzeitung, 1848.
- W.W.Rouse Ball. The eight queens problem. Mathematical Recreations and Essays, pages 165–171, 1960.
- C.F.Gauss und H.C.Schumacher. 6, 1865. CF editor. J W L. the problem of the eight queens. Philosophical Magazine, (4):457–467, November 1874.
- S.P.Nudelman. The modular n-queens problem in higher dimensions. Discrete Math., 146:159–167, 1995.
- C.Erbas and M.M. Tanik S. Sarkeshik. Different perspectives of the n-queens problem. Proceedings of the 1992 ACM Annual Conference on Communications, ACM Press, page 99108, 1992.
- J. Barr and S. Rao. Some observations about the n-queens problem in higher dimensions. Midwest Instructions and Computing Symposium, 2004.
- M. Sharif S. Khan, M. Bilal, M.Sajid, and R.Baig. Solution of n-queen problem using aco. International Multitopic Conference, IEEE, 2009.
- M.Dorigo. Optimization, learning and natural algorithms. In PhD thesis, 1992.
- H.Talbi A.Draa, S.Meshoul and Batouche. A quantum-inspired differential evolution algorithm for solving the N-queens problem, page 2127. 2010.
Index Terms
Keywords