java - 使用堆栈和回溯的 N 皇后程序

Question

我正在尝试编写一个具有 nxn 板的程序(用于家庭作业)，我需要算法来找到所有可能的解决方案，以使 n 个皇后处于一个皇后无法互相捕获的位置。所以我现在的代码看起来像这样。

import java.util.Stack;

public class NQueens {

  public static int solve(int n) {
      Stack<Integer> s = new Stack<Integer>();

      int  current = 0;
      int numSolutions = 0;
      while(!(current>n)){
          if(s.size() == n){
              break;
          }
          if(current == n){
              if((s.peek()==n) && (s.size() == 1)){
                  break;
              }
              if(s.peek() == n){
                  s.pop();
                  current = s.pop()+1;
              }
              else{
                  current = s.pop()+1;
              }
          }
          else if(validPositionChecker(s, current)){
              s.push(current);
              current = 0;
          }
          else{
              current++;
          }
      }
      if(s.size()==n){
          printSolution(s);
          numSolutions++
      }

      return numSolutions;
      }
  public static boolean validPositionChecker(Stack<Integer> s, int currentPosition) {
      for (int i = 0; i < s.size(); i++) {
          if (s.get(i) == currentPosition){
              return false;
          }
          if ((s.get(i) - currentPosition) == (s.size() - i)){
              return false;   
          }
          if ((currentPosition - s.get(i)) == (s.size() - i)){
              return false;   
          }
      }
      return true;
  }
  //this method prints out a solution from the current stack


  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("* ");
      }
      System.out.println();
    }
    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()

}

所以解释一下这段代码。这段代码有效。但它只打印出解决方案之一。在 8x8 的默认 nxn 板中，它应该有 92 个独特的解决方案。

我的问题是如何让它打印所有的解决方案。我知道我可以在求解方法中在给定的 while 循环之上使用另一个 while ，但我不知道要为 while 循环提供哪些参数以使其退出。基本上重申一下，我需要知道在什么条件下我知道更大的 while 循环在找到所有解决方案后何时停止。

我必须使用堆栈，并且不能使用递归来完成此作业。递归会使事情变得简单得多。

Answer 1

import java.util.Stack;

public class QueenSolver {
private static final int NUM_QUEENS = 8;
private static int[] board = new int[NUM_QUEENS];

public static void solve(int n) {
    int current = 0;
    int numSolutions = 0;

    Stack<Integer> s = new Stack<>();

    while (true) {
        while (current < n) {
            if (isBoardCorrect(s, current)) {
                s.push(current);
                board[s.size() - 1] = current;
                current = 0;
            } else {
                current++;
            }
        }

        if (s.size() == n) {
            printSolution(++numSolutions);
        }

        if (s.isEmpty()) {
            break;
        }

        if (s.peek() == n) {
            s.pop();
        }

        current = s.pop() + 1;
    }
}

private static boolean isBoardCorrect(Stack<Integer> s, int currentPosition) {
    for (int i = 0; i < s.size(); i++) {
        if (board[i] == currentPosition
                || currentPosition == board[i]
                || Math.abs(currentPosition - board[i]) == s.size() - i) {

            return false;
        }
    }
    return true;
}

private static void printSolution(int num) {
    System.out.print(num + ": ");
    for (int i = 0; i < board.length; i++) {
        System.out.print("(" + i + "," + board[i] + ")");
        if (i < board.length - 1) {
            System.out.print(", ");
        }
    }
    System.out.println();
}

public static void main(String[] args) {
    QueenSolver.solve(8);
}

}