Java: N-Queens Problem - Using Stacks and Backtracking

[bori]

Hello all. Quick question on an assignment I've been working on for a while now:

What this problem calls for is to solve the N-Queens problem using a stack and backtracking.

Basically, the program calls on a N size board, with N queens. The object of the game is to place N queens on a NxN size board, without any queens being on the same row, column, or diagonal.

My process is this:

1.) I push the first queen on the first column of the first row.
2.) I then try to push a second queen on the second row, and compare each position to see if there is a conflict. If there is, I move onto the next column, and so on. If there is NOT a conflict, then that position is good, and we move onto the next ROW.
3.) We do the same thing above. If, there are conflicts for every column when placing the next queen (we run out of columns), then we POP the current queen, and backtrack! Meaning we go to the previous queen, and move it again to another working spot.
4.) We continue this cycle until all N queens have been placed on the board, and no conflicts arise.

I am supposed to find all solutions. Here is my code so far:

import java.util.Stack;

//fill in your information in the line below, and comment it out in order to compile
//Name: ???   Student ID: ???;

public class Assignment3 {
  boolean conflict, complete = false;
  //***** fill in your code here *****
  //feel free to add additional methods as necessary
  
  //finds and prints out all solutions to the n-queens problem
  public static int solve(int n) {
    //create a stack
    //each element stores the position of the queen on a different row
    Stack<Integer> s = new Stack<Integer> ();
    int solution = 0;
    int nextQueen = 0;
    boolean problem = false;
    s.push(0);
    do{
      for(int i = 0; i < s.size(); i++)
      {
        if(s.get(i) == nextQueen){ 
          problem = true;
          break;
        }
        else if(s.get(i) - i == nextQueen - s.size()){
          problem = true;
          break;
        }
        else if(s.get(i) + i == nextQueen + s.size()){
          problem = true;
          break;
        }
      }
      //***** fill in your code here *****
      if(problem = false){
        s.push(nextQueen);
        nextQueen = 0;}
      else{
        nextQueen++;
      }
      if(nextQueen == n){
        if(s.peek() == n){
          s.pop(); 
          nextQueen = s.pop()+ 1; 
        }
        else{
          nextQueen = s.pop()+ 1;
        }
      }
      }while(s.size() != n);
      
      printSolution(s);
      solution++;
      return solution;
      //(when a solution is found, call print_solution(s) to print it out)
      
    }//solve()
    
    //this method prints out a solution from the current stack
    //(you should not need to modify this method)
    private static void printSolution(Stack<Integer> s) {
      for (int i = 0; i < s.size(); i ++) {
        for (int j = 0; j < s.size(); j ++) {
          if (j == s.get(i))
            System.out.print("Q ");
          else
            System.out.print("* ");
        }//for
        System.out.println();
      }//for
      System.out.println();  
    }//printSolution()
    
    // ----- the main method -----
    // (you shouldn't need to change this method)
    public static void main(String[] args) {
      
      int n = 8;
      
      // pass in parameter n from command line
      if (args.length == 1) {
        n = Integer.parseInt(args[0].trim());
        if (n < 1) {
          System.out.println("Incorrect parameter");
          System.exit(-1);
        }//if   
      }//if
      
      int number = solve(n);
      System.out.println("There are " + number + " solutions to the " + n + "-queens problem.");
    }//main()
    
  }//Assignment3

The main method is not supposed to be changed. As you can see, if you run it, there is a StackExcception thrown, due to the peek method, but I'm not sure what I'm doing wrong. Can anyone help? If you have any more questions, please ask.

[Jihara]

First thing I see is

if(problem = false){
        s.push(nextQueen);
        nextQueen = 0;}
      else{
        nextQueen++;
      }

needs to be if(problem == false) , or better if(!problem) .. This way, you put problem to "false" each time you hit the if clause, which screws up the whole algorithm.

Also, you need to put problem to false each time you go through the loop, or it will stay true forever once you tried to place the Queen next to the first one.

Fixing that I find one "solution" but with only 7 queens.. I'll have another look at it in a bit and try to fix it.

[Teorem]

http://java.sun.com/j2se/1.5.0/docs/...tml#peek%28%29

The documentation tells you specifically why an (and in fact, the only) exception would be thrown. Think about how and if the stack operators you're calling are modifying the stack, and whether you're calling them correctly (both semantically and with the appropriate frequency).

Now's a great time to sit down with a pen and paper and run through your program step-by-step for a small N value. It's your assignment after all, show what you've done to debug it so far.

[Jihara]

I figured it out now and find all 92 solutions.

Problems you need to think about are:

1) What number is n , and which numbers are put into the stack? Be careful when comparing those.

2) Your algorithm is supposed to stop once you found ALL solutions. At the moment, you return "solution" after finding only one.

3) You need to make sure that you somehow save the solutions you have already found, so you don't print doubles. (ie use an ArrayList you put some sort of identification in and check if the found solution is already in there)

4) Have you done recursion yet in your class?

If you need any more help or can't figure it out until the assignment is due, feel free to send me a PM.

[Julian]

Oh man, I remember solving this in my first year programming class with just recursion and backtracking, damn that thing was inefficient, didn't learn about stacks back then. =(

Also, as someone pointed out, the main method looks like it's asking you to find ALL possible solutions for an nxn sized board, which they specify to be 8.

[bori]

I figured it out now and find all 92 solutions.

Problems you need to think about are:

1) What number is n , and which numbers are put into the stack? Be careful when comparing those.

2) Your algorithm is supposed to stop once you found ALL solutions. At the moment, you return "solution" after finding only one.

3) You need to make sure that you somehow save the solutions you have already found, so you don't print doubles. (ie use an ArrayList you put some sort of identification in and check if the found solution is already in there)

4) Have you done recursion yet in your class?

If you need any more help or can't figure it out until the assignment is due, feel free to send me a PM.

Answering the last question, he says it could be done by recursion, but he specifically wants us to use a stack. I went ahead and fixed the "problem = false" situation, and now it runs, but only shows one solution. Also, I noticed it only placed 7 queens on the 8 queens problem, probably due to some variable being off by 1. I'll try to figure it out..

[diggme]

Out of sheer curiosity how exactly did you fix the "problem=false" situation?

[bori]

Ugh..it prints something now, but totally not what I want. It's stuck in infinite loop I believe, and still doesn't print out all n-queens on the board. My code, updated:

import java.util.Stack;

//fill in your information in the line below, and comment it out in order to compile
//Name: ???   Student ID: ???;

public class Assignment3 {
  
  //***** fill in your code here *****
  //feel free to add additional methods as necessary
  
  //finds and prints out all solutions to the n-queens problem
  public static int solve(int n) {
    //create a stack
    //each element stores the position of the queen on a different row
    Stack<Integer> s = new Stack<Integer> ();
    int solution = 0;
    int nextQueen = 0;
    boolean problem = false;
    boolean done = false;
    s.push(0);
    while(!done)
    {
      do{
        for(int i = 0; i < s.size(); i++)
        {
          if(s.get(i) == nextQueen){ 
            problem = true;
            break;
          }
          else if(s.get(i) - i == nextQueen - s.size()){
            problem = true;
            break;
          }
          else if(s.get(i) + i == nextQueen + s.size()){
            problem = true;
            break;
          }
          
        }
        //***** fill in your code here *****
        if(!problem){
          s.push(nextQueen);
          nextQueen = 0;
        }
        else{
          nextQueen++;
        }
        if(nextQueen == n){
          
          if(s.peek() == n){
            s.pop(); 
            nextQueen = s.pop()+ 1; 
            
          }
          else{
            nextQueen = s.pop()+ 1;
            
          }
          
        }
        problem = false;
        
      }while(s.size() != n);
      
      if(s.isEmpty())
      {
        
        done = true;
        
      }
      solution++;
      printSolution(s);   
    } 
    
    return solution;
    
    //(when a solution is found, call print_solution(s) to print it out)
    
  }//solve()
  
  //this method prints out a solution from the current stack
  //(you should not need to modify this method)
  private static void printSolution(Stack<Integer> s) {
    for (int i = 0; i < s.size(); i ++) {
      for (int j = 0; j < s.size(); j ++) {
        if (j == s.get(i))
          System.out.print("Q ");
        else
          System.out.print("* ");
      }//for
      System.out.println();
    }//for
    System.out.println();  
  }//printSolution()
  
  // ----- the main method -----
  // (you shouldn't need to change this method)
  public static void main(String[] args) {
    
    int n = 8;
    
    // pass in parameter n from command line
    if (args.length == 1) {
      n = Integer.parseInt(args[0].trim());
      if (n < 1) {
        System.out.println("Incorrect parameter");
        System.exit(-1);
      }//if   
    }//if
    
    int number = solve(n);
    System.out.println("There are " + number + " solutions to the " + n + "-queens problem.");
  }//main()
  
}//Assignment3

I'm pretty much stuck right now. : /