Call for Paper - January 2019 Edition
IJCA solicits original research papers for the January 2019 Edition. Last date of manuscript submission is December 20, 2018. Read More

A Novel Double Backtracking Approach to the N-Queens Problem in Three Dimensions

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Abhijith Chakiat, Akhil Sudhakaran, Abhinav A. Nair, Pallavi Venkatesh
10.5120/ijca2017914749

Abhijith Chakiat, Akhil Sudhakaran, Abhinav A Nair and Pallavi Venkatesh. A Novel Double Backtracking Approach to the N-Queens Problem in Three Dimensions. International Journal of Computer Applications 169(5):1-5, July 2017. BibTeX

@article{10.5120/ijca2017914749,
	author = {Abhijith Chakiat and Akhil Sudhakaran and Abhinav A. Nair and Pallavi Venkatesh},
	title = {A Novel Double Backtracking Approach to the N-Queens Problem in Three Dimensions},
	journal = {International Journal of Computer Applications},
	issue_date = {July 2017},
	volume = {169},
	number = {5},
	month = {Jul},
	year = {2017},
	issn = {0975-8887},
	pages = {1-5},
	numpages = {5},
	url = {http://www.ijcaonline.org/archives/volume169/number5/27978-2017914749},
	doi = {10.5120/ijca2017914749},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

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

  1. F.W.M. Bezzel. Proposal of eight queens problem. Berliner Schachzeitung, 1848.
  2. W.W.Rouse Ball. The eight queens problem. Mathematical Recreations and Essays, pages 165–171, 1960.
  3. C.F.Gauss und H.C.Schumacher. 6, 1865. CF editor. [4] J W L. the problem of the eight queens. Philosophical Magazine, (4):457–467, November 1874.
  4. S.P.Nudelman. The modular n-queens problem in higher dimensions. Discrete Math., 146:159–167, 1995.
  5. 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.
  6. J. Barr and S. Rao. Some observations about the n-queens problem in higher dimensions. Midwest Instructions and Computing Symposium, 2004.
  7. M. Sharif S. Khan, M. Bilal, M.Sajid, and R.Baig. Solution of n-queen problem using aco. International Multitopic Conference, IEEE, 2009.
  8. M.Dorigo. Optimization, learning and natural algorithms. In PhD thesis, 1992.
  9. H.Talbi A.Draa, S.Meshoul and Batouche. A quantum-inspired differential evolution algorithm for solving the N-queens problem, page 2127. 2010.

Keywords

N-Queens, Three-Dimensional N-Queens, Backtracking