N-Queens program, with stacks

Question

I'm trying to write a program that will return the number of solutions to the N-Queens problem. The code uses a stack to keep track of the valid queen position, popping and pushing appropriately. But there are certain parts in the code that are never reached. I believe they are the cause of the program's not working. They have been marked with exclamation points. Can anyone explain why these portions are never reached?

import java.util.Stack;

public class nQ {

    public static Stack<Integer> s = new Stack<Integer>();
    public static int n; 
    public static int total; 
    public static int i; 

  //finds and prints out all solutions to the n-queens problem
  public static int solve(int n) {

     // i goes through each row to place a queen
      // x goes through the columns within each row 
      System.out.println("1");
      for(int i = 0; i < n; i++) {
         System.out.println("2");
          for(int x = 0; x<n; x++){
              System.out.println("3");
            if(conflict(x) == false){ // loop through each column and checks whether it conflicts with current position of queen
                System.out.println("4");
                s.push(x); // no conflict, push x 
                //Q = s.get(x); // set current position of queen
                break; //break out of loop to move on to next row, i++ 
                }

            else if (conflict(x)==true){
                System.out.println("5");
                if(s.isEmpty() == true){
                    System.out.println("!!!!6");
                    break; 
                }

                if(x==n-1){ // if its looped through all columns, and there's no valid position
                    s.pop(); //pop last entry 
                    i= i-1; // and backtrack to previous row, to find another valid position for q in previous row 
                    System.out.println("7");
                } 

            }

            if (s.size()==n){ // if stack size is n, then stack is full and a solution has been found
                total++; 
                System.out.print(s);// print solution 
                s.pop();
                i= i-1; //backtrack to find next solution
                System.out.println("!!!!!!!8");
            }
            System.out.println("9");
          }
          System.out.println("10");

  } 
      System.out.println("11");
      System.out.print(s);
      return total; 
  }

public static boolean conflict(int x) {

    for (int j = 0; j<s.size(); j++) {
        if ((s.get(j)==x) || ((x-s.get(j))== (i-(j))) || ((s.get(j)-x)== (i-(j)))) { 
            return true; //there is a conflict!! x 
        }
    }
return false; //no conflict
}



  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()


  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()

}

Answer 1

I've added some more meaningful information to your debugging output, including the size of the stack, and the loop index. It shows that the size of your stack increases to five, and then just bounces back between four and five. I don't know why this is happening, but this sort of diagnostic information is more useful than just knowing where the code is currently executing.

   import java.util.Stack;
public class nQ { 
    public static Stack<Integer> s = new Stack<Integer>();
    public static int n;
    public static int total;
    public static int i;

  //finds and prints out all solutions to the n-queens problem
  public static int solve(int n) {

     // i goes through each row to place a queen
      // x goes through the columns within each row
      for(int i = 0; i < n; i++) {
          for(int x = 0; x<n; x++){
              System.out.println("3  x=" + x + ", n=" + n + ", s.size()=" + s.size());
            if(conflict(x) == false){ // loop through each column and checks whether it conflicts with current position of queen
                s.push(x); // no conflict, push x
                System.out.println("4  s.size()=" + s.size());
                //Q = s.get(x); // set current position of queen
                break; //break out of loop to move on to next row, i++
                }

            else if (conflict(x)==true){
                System.out.println("5  x=" + x + ", n=" + n + ", s.size()=" + s.size());
                if(s.isEmpty() == true){
                    System.out.println("!!!!6");
                    break;
                }

                if(x==n-1){ // if its looped through all columns, and there's no valid position
                    s.pop(); //pop last entry
                 System.out.println("6  x=" + x + ", n=" + n + ", s.size()=" + s.size());
                   i= i-1; // and backtrack to previous row, to find another valid position for q in previous row
                    System.out.println("7");
                }

            }

        System.out.println("7a  x=" + x + ", n=" + n + ", s.size()=" + s.size());

            if (s.size()==n){ // if stack size is n, then stack is full and a solution has been found
                total++;
                System.out.print(s);// print solution
                s.pop();
                i= i-1; //backtrack to find next solution
                System.out.println("!!!!!!!8");
            }
          }

  }
      System.out.print(s);
      return total;
  }

public static boolean conflict(int x) {

    for (int j = 0; j<s.size(); j++) {
        if ((s.get(j)==x) || ((x-s.get(j))== (i-(j))) || ((s.get(j)-x)== (i-(j)))) {
            return true; //there is a conflict!! x
        }
    }
return false; //no conflict
}



  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()


  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()

}

Output:

[R:\jeffy\programming\sandbox\xbnjava]java nQ
3  x=0, n=8, s.size()=0
4  s.size()=1
3  x=0, n=8, s.size()=1
5  x=0, n=8, s.size()=1
7a  x=0, n=8, s.size()=1
3  x=1, n=8, s.size()=1
4  s.size()=2
3  x=0, n=8, s.size()=2
5  x=0, n=8, s.size()=2
7a  x=0, n=8, s.size()=2
3  x=1, n=8, s.size()=2
5  x=1, n=8, s.size()=2
7a  x=1, n=8, s.size()=2
3  x=2, n=8, s.size()=2
5  x=2, n=8, s.size()=2
7a  x=2, n=8, s.size()=2
3  x=3, n=8, s.size()=2
4  s.size()=3
3  x=0, n=8, s.size()=3
5  x=0, n=8, s.size()=3
7a  x=0, n=8, s.size()=3
3  x=1, n=8, s.size()=3
5  x=1, n=8, s.size()=3
7a  x=1, n=8, s.size()=3
3  x=2, n=8, s.size()=3
5  x=2, n=8, s.size()=3
7a  x=2, n=8, s.size()=3
3  x=3, n=8, s.size()=3
5  x=3, n=8, s.size()=3
7a  x=3, n=8, s.size()=3
3  x=4, n=8, s.size()=3
4  s.size()=4
3  x=0, n=8, s.size()=4
5  x=0, n=8, s.size()=4
7a  x=0, n=8, s.size()=4
3  x=1, n=8, s.size()=4
5  x=1, n=8, s.size()=4
7a  x=1, n=8, s.size()=4
3  x=2, n=8, s.size()=4
5  x=2, n=8, s.size()=4
7a  x=2, n=8, s.size()=4
3  x=3, n=8, s.size()=4
5  x=3, n=8, s.size()=4
7a  x=3, n=8, s.size()=4
3  x=4, n=8, s.size()=4
5  x=4, n=8, s.size()=4
7a  x=4, n=8, s.size()=4
3  x=5, n=8, s.size()=4
5  x=5, n=8, s.size()=4
7a  x=5, n=8, s.size()=4
3  x=6, n=8, s.size()=4
4  s.size()=5
3  x=0, n=8, s.size()=5
5  x=0, n=8, s.size()=5
7a  x=0, n=8, s.size()=5
3  x=1, n=8, s.size()=5
5  x=1, n=8, s.size()=5
7a  x=1, n=8, s.size()=5
3  x=2, n=8, s.size()=5
5  x=2, n=8, s.size()=5
7a  x=2, n=8, s.size()=5
3  x=3, n=8, s.size()=5
5  x=3, n=8, s.size()=5
7a  x=3, n=8, s.size()=5
3  x=4, n=8, s.size()=5
5  x=4, n=8, s.size()=5
7a  x=4, n=8, s.size()=5
3  x=5, n=8, s.size()=5
5  x=5, n=8, s.size()=5
7a  x=5, n=8, s.size()=5
3  x=6, n=8, s.size()=5
5  x=6, n=8, s.size()=5
7a  x=6, n=8, s.size()=5
3  x=7, n=8, s.size()=5
5  x=7, n=8, s.size()=5
6  x=7, n=8, s.size()=4
7
7a  x=7, n=8, s.size()=4
3  x=0, n=8, s.size()=4
5  x=0, n=8, s.size()=4
7a  x=0, n=8, s.size()=4
3  x=1, n=8, s.size()=4
5  x=1, n=8, s.size()=4
7a  x=1, n=8, s.size()=4
3  x=2, n=8, s.size()=4
5  x=2, n=8, s.size()=4
7a  x=2, n=8, s.size()=4
3  x=3, n=8, s.size()=4
5  x=3, n=8, s.size()=4
7a  x=3, n=8, s.size()=4
3  x=4, n=8, s.size()=4
5  x=4, n=8, s.size()=4
7a  x=4, n=8, s.size()=4
3  x=5, n=8, s.size()=4
5  x=5, n=8, s.size()=4
7a  x=5, n=8, s.size()=4
3  x=6, n=8, s.size()=4
4  s.size()=5
3  x=0, n=8, s.size()=5
5  x=0, n=8, s.size()=5
7a  x=0, n=8, s.size()=5
3  x=1, n=8, s.size()=5
5  x=1, n=8, s.size()=5
7a  x=1, n=8, s.size()=5
3  x=2, n=8, s.size()=5
5  x=2, n=8, s.size()=5
7a  x=2, n=8, s.size()=5
3  x=3, n=8, s.size()=5
5  x=3, n=8, s.size()=5
7a  x=3, n=8, s.size()=5
3  x=4, n=8, s.size()=5
5  x=4, n=8, s.size()=5
7a  x=4, n=8, s.size()=5
3  x=5, n=8, s.size()=5
5  x=5, n=8, s.size()=5
7a  x=5, n=8, s.size()=5
3  x=6, n=8, s.size()=5
5  x=6, n=8, s.size()=5
7a  x=6, n=8, s.size()=5
3  x=7, n=8, s.size()=5
5  x=7, n=8, s.size()=5
6  x=7, n=8, s.size()=4
7
7a  x=7, n=8, s.size()=4
3  x=0, n=8, s.size()=4
5  x=0, n=8, s.size()=4
7a  x=0, n=8, s.size()=4
3  x=1, n=8, s.size()=4
5  x=1, n=8, s.size()=4
7a  x=1, n=8, s.size()=4
3  x=2, n=8, s.size()=4
5  x=2, n=8, s.size()=4
7a  x=2, n=8, s.size()=4
3  x=3, n=8, s.size()=4
5  x=3, n=8, s.size()=4
7a  x=3, n=8, s.size()=4
3  x=4, n=8, s.size()=4
5  x=4, n=8, s.size()=4
7a  x=4, n=8, s.size()=4
3  x=5, n=8, s.size()=4
5  x=5, n=8, s.size()=4
7a  x=5, n=8, s.size()=4
3  x=6, n=8, s.size()=4
4  s.size()=5
3  x=0, n=8, s.size()=5
5  x=0, n=8, s.size()=5
7a  x=0, n=8, s.size()=5
3  x=1, n=8, s.size()=5
5  x=1, n=8, s.size()=5
7a  x=1, n=8, s.size()=5
3  x=2, n=8, s.size()=5
5  x=2, n=8, s.size()=5
7a  x=2, n=8, s.size()=5
3  x=3, n=8, s.size()=5
5  x=3, n=8, s.size()=5
7a  x=3, n=8, s.size()=5
3  x=4, n=8, s.size()=5
5  x=4, n=8, s.size()=5
7a  x=4, n=8, s.size()=5
3  x=5, n=8, s.size()=5
5  x=5, n=8, s.size()=5
7a  x=5, n=8, s.size()=5
3  x=6, n=8, s.size()=5
5  x=6, n=8, s.size()=5
7a  x=6, n=8, s.size()=5
3  x=7, n=8, s.size()=5
5  x=7, n=8, s.size()=5
6  x=7, n=8, s.size()=4
7
7a  x=7, n=8, s.size()=4
3  x=0, n=8, s.size()=4
5  x=0, n=8, s.size()=4
7a  x=0, n=8, s.size()=4
3  x=1, n=8, s.size()=4
5  x=1, n=8, s.size()=4
7a  x=1, n=8, s.size()=4
3  x=2, n=8, s.size()=4
5  x=2, n=8, s.size()=4
7a  x=2, n=8, s.size()=4
3  x=3, n=8, s.size()=4
5  x=3, n=8, s.size()=4
7a  x=3, n=8, s.size()=4
3  x=4, n=8, s.size()=4
5  x=4, n=8, s.size()=4
7a  x=4, n=8, s.size()=4
3  x=5, n=8, s.size()=4
5  x=5, n=8, s.size()=4
7a  x=5, n=8, s.size()=4
3  x=6, n=8, s.size()=4
4  s.size()=5
[0, 1, 3, 4, 6]There are 0 solutions to the 8-queens problem.