asked on

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

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.");
}
}
}

CEHJ

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

menghao

ASKER

yes, the rest was provided by our teacher. :)

CEHJ

We're not allowed to do homework here. Only help with work you've already done

menghao

ASKER

I just wanna get some hints on algorithm and how to find all solutions.
Cheers

funnyveryfunny

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.

menghao

ASKER

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.

ASKER CERTIFIED SOLUTION

funnyveryfunny

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

funnyveryfunny

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)

funnyveryfunny

forgot mine is based on 8x8 chessboard :)

funnyveryfunny