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
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.