N後算法的錯誤以及如何打印所有的解決方案

Question

對A N皇后問題（非遞歸和一個堆棧）工作，有兩個非常具體的問題：

我「notSafe」的方法，檢查是否有是同一行/列和對角線中的皇后，而另一皇后並不真正工作。我無法發現邏輯錯誤，這可能是由於另一種方法「完成」，可能無法正確回溯。

此外，第二個問題：關於如何打印出所有解決方案的任何想法？也許有一些提示讓我開始。

import java.util.Stack; 

public class Test1 { 

static Stack<Integer> s = new Stack<Integer>(); 
static int topRow = 0; 
static int currentRow = 0; 
static int row = 0; 
static int n = 8; 


public static void main(String args[]) { 

    finish(n); 

} 

public static void finish(int n) { 
    placeQueen(); 
    placeQueen(); 

    boolean success = false; 
    while (success != true) { 

     if (notSafe() == true && s.empty() == false) { 
      int c = 1; 

      do { 

       if (c <= n) { 
        s.pop(); 
        row--; 
        c++; 
        s.push(c); 
        row++; 
       } else if (c <= n && s.size() == 0) { 
        c++; 
        s.push(c); 
        row++; 

       } else { 
        c = 1; 
        s.pop(); 

       } 

      } while (notSafe() == true); 

     } else if (s.size() == n && notSafe() == false) { 
      display(); 
      break; 
     } else { 
      placeQueen(); 

     } 

    } 
} 

public static boolean notSafe() { 
    boolean status = false; 
    int top = s.size()-1; 

    topRow = row; 
    int temp = row; 
    currentRow = temp - 1; 

    if (s.size() > 1) { 

     for (int m = top; m >= 1; m--) { 
      int x = (Integer) s.get(top); 
      int y = (Integer) s.get(m - 1); 
      if ((x == y) || x - y == currentRow || x + y == currentRow) { 

       status = true; 

      } 
     } 
    } 

    return status; 
} 

public static void placeQueen() { 

    s.push(1); 
    row++; 

} 
//======Display=======// 
public static void display() { 
    int z = 0; 
    while (z != s.size()) { 

     int x = (Integer) s.pop(); 
     for (int y = 1; y <= n; y++) { 

      if (x != (y)) { 
       System.out.print("-"); 

      } else 
       System.out.print("q"); 
     } 
     System.out.print("\n"); 
    } 
} 

}

Answer 1

的幾個問題在這裏指出：

• 你似乎是放置在第1行兩個皇后在第2列。這將使解決方案變得非法（假設n> 1）
• 您不需要繼續測試已放置的皇后：只需檢查您即將用於下一列的行是否相同與之前的任何皇后相同（改變方法接受一行測試）。

如果按照建議的那些作品，那麼你可以簡化爲：

private boolean rowIsSafe(int testRow) { 
    for (int col = 0; col < stack.size(); col++) { 
     if (stack.get(col) == testRow) 
      return false; 
     if (Maths.abs(testRow - stack.get(col)) == stack.size() - col) 
      return false; 
    } 
    return true; 
} 

或者，在Java 8：

IntStream.range(0, stack.size()).noneMatch(col -> stack.get(col) == testRow 
    || Maths.abs(testRow - stack.get(col)) == stack.size() - col) 

打印出所有的解決方案只是意味着你不停止（即break），一旦你遇到一個解決方案：打印它，彈出並繼續。