Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

How to use stack data structure to solve N Queens problem?

Posted on 2004-10-20
10
Medium Priority
?
2,841 Views
Last Modified: 2012-08-13
Hi there everyone,

Can anyone tell me how can I use the stack data structure(no recursive algorithm) to find all possible solutions for the N Queens puzzle and output all these solutions?

I have done the first part and find out the first solution for a N*N chessboard using StackReferenceBased class, and the code is:

import java.awt.*;
public class NQueens{

private StackReferenceBased stack;
private int size;
private Point[] stackMirror;
private boolean isSolutionFound;
private int stackSize;

public static void main(String args[]){

int noOfQueens = Integer.parseInt(args[0]);
System.out.println("The chessboard size is " + noOfQueens + "x" + noOfQueens);

NQueens queens = new NQueens(noOfQueens);
queens.search();
queens.output();
}

public NQueens(int size){
this.size = size;
stack = new StackReferenceBased();
stackMirror = new Point[size];
isSolutionFound = false;
}

public void search(){
stackReady();
while(true){
if(stackSize<size){//Push a Queen into stack while stack is not full
Point lastQueen = (Point)stack.peek();
Point newQueen = new Point(lastQueen.x+1,1);
stack.push(newQueen);
stackMirror[stackSize] = newQueen;
stackSize++;
}
else{
if(validate()==true){  // First solution found
isSolutionFound = true;
return;
}
else{  //backtracking
while(true){
if(stack.isEmpty()){ //If all Queens are popped,stack is empty,no solution found.
isSolutionFound = false;
return;
}

Point lastQueen = (Point)stack.pop();
--stackSize;
lastQueen.y +=1;
if(lastQueen.y>size){
continue;
}
stack.push(lastQueen);
stackMirror[stackSize] = lastQueen;
++stackSize;
break;
}
}
}
}
}

public void stackReady(){
Point first = new Point(1,1);
stack.push(first);
stackMirror[0]=first;
stackSize=1;
}

public boolean validate(){
for(int i=0;i<size-1;i++){
for(int j=i+1;j<size;j++){
if(validate2Queens(stackMirror[i],stackMirror[j])==false){
return false;
}
}
}
return true;
}

public boolean validate2Queens(Point queen1, Point queen2){
if ((queen1.y == queen2.y)||
(queen1.x == queen2.x)||
((queen2.x-queen1.x) == (queen2.y-queen1.y))||
((queen1.x-queen2.x) == (queen2.y-queen1.y))){
return false;
}
return true;
}

public void output(){
if(isSolutionFound == true){
System.out.println("Solution found: (column, row)");
for(int i=0; i<size; i++){
System.out.println("Place a queen at position: ("
+stackMirror[i].x+", "+stackMirror[i].y+")");
}
}
else{
System.out.println("No solution found.");
}
}
}
0
Comment
Question by:menghao
  • 5
  • 3
  • 2
10 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 12359006
How did you manage to get so far without knowing the rest - perhaps because that much was given by your teacher?
0
 

Author Comment

by:menghao
ID: 12359230
yes, the rest was provided by our teacher. :)
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 12359289
We're not allowed to do homework here. Only help with work you've already done
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

Author Comment

by:menghao
ID: 12359420
I just wanna get some hints on algorithm and how to find all solutions.
Cheers
0
 
LVL 4

Expert Comment

by:funnyveryfunny
ID: 12374238
hi,

I'm not familiar with N queens puzzle, can you explain how puzzle normally solve on paper then maybe I can guide you through the algo.
0
 

Author Comment

by:menghao
ID: 12376631
The common N Queens problem is a eight queens puzzle based on chess, The task is to put eight queens on an empty 8*8 chessboard, such that no queen can take another queen( no two queens may be on the same horizontal, vertical or diagonal line). for eight queens, two solutions are :

Q*******              *******Q
******Q*              ***Q****
****Q***              Q*******
*******Q       or    **Q*****
*Q******              *****Q**
***Q****              *Q******
*****Q**              ******Q*
**Q*****              ****Q***

there are totally 92 solutions for 8 Queens puzzle.

To slolve this problem, using backtracking to the position in the previous column if there is no avaliable safe position in the current column.

For my problem is how can we output all solutions and how to improve the execution time using stack data structure.
0
 
LVL 4

Accepted Solution

by:
funnyveryfunny earned 2000 total points
ID: 12391003
Hi,

I looked at your puzzle and initially I came up with the idea of using two stacks to solve but came to a dead end as this was not possible to produce all the solutions for every queen-start positions as I couldn't trace back.

But the good news is, with the similar idea, I have managed to solve it using 8 stacks and I have all 92 solutions.

Here is the idea of how to produce all the valid solutions to this puzzle:

1) First what we need are 8 stacks for each stack corresponds to a single row of a chessboard, so I named each stack like this row_1st, row_2nd .... row_8th. And a Point[8] array to store each combination. And a vector to store all combinations.

2) I then used waterfall-cycle like to produce all the possible solutions based on each queen_start. Each queen_start is store in row_1st stack, imagine row_1st looks like this:

                                         |(1,8)|
                                         |(1,7)|
                                         |(1,6)|
                                         |(1,5)|
                                         |(1,4)|
                                         |(1,3)|
                                         |(1,2)|
                                         |(1,2)|

3) the, we pop the first queen from row_1st stack, i.e position (1,8) and produce all the valid positions the 2nd_queen  can be on 2nd row and store these positions in row_2nd stack.

4) Similar to step 3) but on row_2nd stack, we store all the possible positions 3rd_queen can be on 3rd row in row_3rd.

5) Step 4) is then carried out until you reach row 8, which all the possible positions of 8th_queen is stored in row_8th.

6) After step 5) you have so far produce all the possible solutions to queen_start(1,8).

7) Next step is to store all these possible solutions, the procedure to storing all the positions is like trying to produce all the combinations to a safe (hacking - password guessing etc) but the only catch is every combination is valid because each stack only holds valid positions.

8) Back to step 1, pop out the next queen_start position and the process repeats until row_1st stack is empty.


A mechanical description is like this: Imagine you have 8 wheels connected to each other. Wheel 1 represents row_1st and wheel 2 represents row_2nd and so on to wheel 8=row_8th. Then wheel 1 is connected to wheel 2, and wheel 2 is connected to wheel 3....wheel 7 to 8. For every full rotation of wheel 2, wheel 1 moves by 1 click...imagine clock's hour/min/sec hands relationship. And for every full rotation of wheel 3, wheel 2 also moves by 1 click.....same applied to other wheels.


Try to understand the idea here and come up with psuedo-code for it.
0
 
LVL 4

Expert Comment

by:funnyveryfunny
ID: 12391028
My program takes 170 ~ 160 millisecs to solve and 380 millisecs included console printing.

Here are some results for validation:

(1.0,5.0)(2.0,1.0)(3.0,4.0)(4.0,6.0)(5.0,8.0)(6.0,2.0)(7.0,7.0)(8.0,3.0)
(1.0,4.0)(2.0,8.0)(3.0,5.0)(4.0,3.0)(5.0,1.0)(6.0,7.0)(7.0,2.0)(8.0,6.0)
(1.0,4.0)(2.0,8.0)(3.0,1.0)(4.0,5.0)(5.0,7.0)(6.0,2.0)(7.0,6.0)(8.0,3.0)
(1.0,4.0)(2.0,8.0)(3.0,1.0)(4.0,3.0)(5.0,6.0)(6.0,2.0)(7.0,7.0)(8.0,5.0)
(1.0,4.0)(2.0,7.0)(3.0,5.0)(4.0,3.0)(5.0,1.0)(6.0,6.0)(7.0,8.0)(8.0,2.0)
(1.0,4.0)(2.0,7.0)(3.0,5.0)(4.0,2.0)(5.0,6.0)(6.0,1.0)(7.0,3.0)(8.0,8.0)
(1.0,4.0)(2.0,7.0)(3.0,3.0)(4.0,8.0)(5.0,2.0)(6.0,5.0)(7.0,1.0)(8.0,6.0)
(1.0,4.0)(2.0,7.0)(3.0,1.0)(4.0,8.0)(5.0,5.0)(6.0,2.0)(7.0,6.0)(8.0,3.0)
(1.0,4.0)(2.0,6.0)(3.0,8.0)(4.0,3.0)(5.0,1.0)(6.0,7.0)(7.0,5.0)(8.0,2.0)
(1.0,4.0)(2.0,6.0)(3.0,8.0)(4.0,2.0)(5.0,7.0)(6.0,1.0)(7.0,3.0)(8.0,5.0)
(1.0,4.0)(2.0,6.0)(3.0,1.0)(4.0,5.0)(5.0,2.0)(6.0,8.0)(7.0,3.0)(8.0,7.0)
(1.0,4.0)(2.0,2.0)(3.0,8.0)(4.0,6.0)(5.0,1.0)(6.0,3.0)(7.0,5.0)(8.0,7.0)
(1.0,4.0)(2.0,2.0)(3.0,8.0)(4.0,5.0)(5.0,7.0)(6.0,1.0)(7.0,3.0)(8.0,6.0)
(1.0,4.0)(2.0,2.0)(3.0,7.0)(4.0,5.0)(5.0,1.0)(6.0,8.0)(7.0,6.0)(8.0,3.0)
(1.0,4.0)(2.0,2.0)(3.0,7.0)(4.0,3.0)(5.0,6.0)(6.0,8.0)(7.0,5.0)(8.0,1.0)
(1.0,4.0)(2.0,2.0)(3.0,7.0)(4.0,3.0)(5.0,6.0)(6.0,8.0)(7.0,1.0)(8.0,5.0)
(1.0,4.0)(2.0,2.0)(3.0,5.0)(4.0,8.0)(5.0,6.0)(6.0,1.0)(7.0,3.0)(8.0,7.0)
(1.0,4.0)(2.0,1.0)(3.0,5.0)(4.0,8.0)(5.0,6.0)(6.0,3.0)(7.0,7.0)(8.0,2.0)
(1.0,4.0)(2.0,1.0)(3.0,5.0)(4.0,8.0)(5.0,2.0)(6.0,7.0)(7.0,3.0)(8.0,6.0)
(1.0,3.0)(2.0,8.0)(3.0,4.0)(4.0,7.0)(5.0,1.0)(6.0,6.0)(7.0,2.0)(8.0,5.0)
(1.0,3.0)(2.0,7.0)(3.0,2.0)(4.0,8.0)(5.0,6.0)(6.0,4.0)(7.0,1.0)(8.0,5.0)
(1.0,3.0)(2.0,7.0)(3.0,2.0)(4.0,8.0)(5.0,5.0)(6.0,1.0)(7.0,4.0)(8.0,6.0)
(1.0,3.0)(2.0,6.0)(3.0,8.0)(4.0,2.0)(5.0,4.0)(6.0,1.0)(7.0,7.0)(8.0,5.0)
(1.0,3.0)(2.0,6.0)(3.0,8.0)(4.0,1.0)(5.0,5.0)(6.0,7.0)(7.0,2.0)(8.0,4.0)
(1.0,3.0)(2.0,6.0)(3.0,8.0)(4.0,1.0)(5.0,4.0)(6.0,7.0)(7.0,5.0)(8.0,2.0)
(1.0,3.0)(2.0,6.0)(3.0,4.0)(4.0,2.0)(5.0,8.0)(6.0,5.0)(7.0,7.0)(8.0,1.0)
(1.0,3.0)(2.0,6.0)(3.0,4.0)(4.0,1.0)(5.0,8.0)(6.0,5.0)(7.0,7.0)(8.0,2.0)
(1.0,3.0)(2.0,6.0)(3.0,2.0)(4.0,7.0)(5.0,5.0)(6.0,1.0)(7.0,8.0)(8.0,4.0)
(1.0,3.0)(2.0,6.0)(3.0,2.0)(4.0,7.0)(5.0,1.0)(6.0,4.0)(7.0,8.0)(8.0,5.0)
(1.0,3.0)(2.0,6.0)(3.0,2.0)(4.0,5.0)(5.0,8.0)(6.0,1.0)(7.0,7.0)(8.0,4.0)
(1.0,3.0)(2.0,5.0)(3.0,8.0)(4.0,4.0)(5.0,1.0)(6.0,7.0)(7.0,2.0)(8.0,6.0)
(1.0,3.0)(2.0,5.0)(3.0,7.0)(4.0,1.0)(5.0,4.0)(6.0,2.0)(7.0,8.0)(8.0,6.0)
(1.0,3.0)(2.0,5.0)(3.0,2.0)(4.0,8.0)(5.0,6.0)(6.0,4.0)(7.0,7.0)(8.0,1.0)
(1.0,3.0)(2.0,5.0)(3.0,2.0)(4.0,8.0)(5.0,1.0)(6.0,7.0)(7.0,4.0)(8.0,6.0)
(1.0,3.0)(2.0,1.0)(3.0,7.0)(4.0,5.0)(5.0,8.0)(6.0,2.0)(7.0,4.0)(8.0,6.0)
(1.0,2.0)(2.0,8.0)(3.0,6.0)(4.0,1.0)(5.0,3.0)(6.0,5.0)(7.0,7.0)(8.0,4.0)
(1.0,2.0)(2.0,7.0)(3.0,5.0)(4.0,8.0)(5.0,1.0)(6.0,4.0)(7.0,6.0)(8.0,3.0)
(1.0,2.0)(2.0,7.0)(3.0,3.0)(4.0,6.0)(5.0,8.0)(6.0,5.0)(7.0,1.0)(8.0,4.0)
(1.0,2.0)(2.0,6.0)(3.0,8.0)(4.0,3.0)(5.0,1.0)(6.0,4.0)(7.0,7.0)(8.0,5.0)
(1.0,2.0)(2.0,6.0)(3.0,1.0)(4.0,7.0)(5.0,4.0)(6.0,8.0)(7.0,3.0)(8.0,5.0)
(1.0,2.0)(2.0,5.0)(3.0,7.0)(4.0,4.0)(5.0,1.0)(6.0,8.0)(7.0,6.0)(8.0,3.0)
(1.0,2.0)(2.0,5.0)(3.0,7.0)(4.0,1.0)(5.0,3.0)(6.0,8.0)(7.0,6.0)(8.0,4.0)
(1.0,2.0)(2.0,4.0)(3.0,6.0)(4.0,8.0)(5.0,3.0)(6.0,1.0)(7.0,7.0)(8.0,5.0)
(1.0,1.0)(2.0,7.0)(3.0,5.0)(4.0,8.0)(5.0,2.0)(6.0,4.0)(7.0,6.0)(8.0,3.0)
(1.0,1.0)(2.0,7.0)(3.0,4.0)(4.0,6.0)(5.0,8.0)(6.0,2.0)(7.0,5.0)(8.0,3.0)
(1.0,1.0)(2.0,6.0)(3.0,8.0)(4.0,3.0)(5.0,7.0)(6.0,4.0)(7.0,2.0)(8.0,5.0)
(1.0,1.0)(2.0,5.0)(3.0,8.0)(4.0,6.0)(5.0,3.0)(6.0,7.0)(7.0,2.0)(8.0,4.0)
0
 
LVL 4

Expert Comment

by:funnyveryfunny
ID: 12391032
forgot mine is based on 8x8 chessboard :)
0
 
LVL 4

Expert Comment

by:funnyveryfunny
ID: 12392755
:)
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses

972 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question