The N-Queens, in 3-D.
The 8-Queens problem is a classic well-known chessboard problem of placing 8 Queens on a chessboard in such a way that none of them are attacking. This problem has been a focus of study for many years and the generalized N-Queens problem of placing N Queens on a N×N board such that none of them are attacking is well-known too.
http://www.ijcaonline.org/archives/volume169/number5/27978-2017914749Let’s get started
We studied this problem in detail and proposed a method to extend this problem to the third dimension. This, too, has been done in several ways (check references of the paper). Our method is novel and defines the 3-D approach differently.
Our approach to the 3-Dimensional Queens problem defines the problem with the same definition of that of the classic N-Queens problem, but with the extension to the third dimension such that when any N 2-D solutions are stacked on top of each other, no two queens are placed in the same vertical line, i.e no queen is vertically on top of another. This can be mentally visualised as a square building with N floors, each floor containing N Queens that are non attacking in the same floor, and that no queen is exactly on top of another in the building.
For all those who want to directly feast on the paper, can find the problem discussed in detail here.
A quick look
To reiterate the problem of the classic N-Queens, determine the placement of N queens on an N×N chess board such that no two queens can attack each other. A queen can attack another queen in the same column, row, or diagonal. For the math geeks, a more understandable definition would be:
The solution is represented by a set D, if for the Cartesian product, D×D, each element ((ik, jk), (il, jl)) either satisfies all of the following rules or fails all of them.(1) ik ≠ il (not on same column)
(2) jk ≠ jl (not on same row)
(3) ik + jk ≠ il + jl (not on same diagonal)
(4) ik − jk ≠ il − jl (not on same diagonal)
Our definition of the 3-D problem adds another rule to the above:
(5) ih ≠ jh (not on the same vertical plane with height h)The classic problem itself is quite computationally expensive as the number the solutions increase exponentially with linear increase in the number of queens.
How we did it
Our proposed explains a way to find a single solution to the 3-Dimensional Queens problem, i.e a single configuration where Queens are placed in non attacking position in a N×N×N cube.
The major strategy is the Backtracking algorithm, which is used to obtain all the two dimensional solutions for a given value of N. The three dimensional solution is obtained by using backtracking again to stack up the two dimensional solution on top one another till the desired result is found. An abstract block representation of the proposed model is shown.
For a given value of N, all the solutions to the classic N-Queens problem (two dimensional) is constructed and maintained, in what we call a 2-D solution stack.
The three dimensional solution constructor picks up a 2D dimensional solution from this 2-D solution stack and starts building the three dimensional solution. It is done by placing one 2-D solution over another and checking whether the move is legal according to the proposed representation of the problem, i.e whether a queen lies vertically on another queen across the previously selected 2-D solutions. Of course, the first 2-D solution is always selected without any constraint. If the move is legal, then the selected 2-D solution is placed on the previously constructed partial solution and a new solution is picked up from the 2-D solution stack and the process repeats all over again till N such 2-D solutions are stacked.
If a particular step is illegal, it is discarded. If no solution is being found from the previously constructed partial solution, then the algorithm backtracks and replaces a previous selection with the next candidate available at that particular instant. The proposed approach stops when a single solution is constructed.
The implementation is discussed in details along with the necessary algorithms in the paper here.
Moving onwards
The solution to this problem can be visualised as shown in the image where we have solved for 5 Queens.
Also, the 3-D solution might exist if and only if, for a given N, the number of two dimensional solutions is greater than or equal to N. Consider N = 4, there are only two 2-D solutions hence a 3-D solution is impossible. The general backtracking algorithm for the N-queens problem has a time complexity of O(N!). Back tracking is used twice in the proposed approach, hence an upper bound of O(N!) is seen.
Another concise representation of this solution is given in the paper, wherein the solution is represented in a 2-D array (table) with each digit denoting the level (or floor, according to the building analogy) in which the queen is placed.
Much work can be done to improve or build upon this approach, to optimise it to run faster. Parallelisation is one way of improving this. Other techniques could include using the Ant Colony Optimisation or a Quantum inspired approach as discussed here.
