0

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

}
4

1 回答 1

1

我在调试输出中添加了一些更有意义的信息，包括堆栈大小和循环索引。它表明你的筹码量增加到五，然后在四到五之间反弹。我不知道为什么会发生这种情况，但这种诊断信息比只知道代码当前执行的位置更有用。

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

}

输出：

[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.
于 2014-02-24T18:27:23.743 回答