n-queens謎題是指在一個(n×n)棋盤上放置n個皇后，使得沒有兩個皇后可以相互攻擊的問題。
我使用回溯法來解決這個問題。但我遇到了一個奇怪的問題。
下面是我寫的代碼：
import java.util.ArrayList。
public class NQueenProblem {
static ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer> > ();
static ArrayList<ArrayList<Integer>> nQueen(int) {
ArrayList<Integer> positions = new ArrayList<Integer>（）。
//boolean[][] placed = new boolean[n][n];
solveNQueenRec(n, 0, new boolean[n][n], positions) 。
//用于除錯的目的。這將列印出空陣列。不明白為什么？
for (ArrayList<Integer> list : ans)
System.out.println(list)。
return ans;
}
static void solveNQueenRec(int n, int col, boolean[] [] placed, ArrayList< Integer> positions） {
if (col == n) {
//for debugging process
System.out.println("添加" positions)。
ans.add(position)。
System.out.println("添加了" positions)。
}
for (int row = 0; row < n & col < n; row ) {
if (isSafe(row, col, placed, n)) {
placed[row][col] = true;
positions.add（row 1）。
solveNQueenRec(n, col 1, placed, positions)。
placed[row][col] = false;
positions.remove(position.size() - 1) 。
}
}
//return null;
}
private static boolean isSafe（int row, int col, boolean[] [] placed, int n） {
boolean safe = true。
//檢查是否存在于同一行。
for (int i = 0; i < col; i ) {
if (place[row][i])
safe = false;
}
//檢查上對角線。
for (int i = row, j=col; i >= 0 && j >= 0; i-, j-) {
if (place[i][j])
safe = false;
}
//checking for lower diagonal; }
for (int i = row, j = col; i < n && j >=0; i , j-) {
if (place[i][j])
safe = false;
}
return safe。
}
public static void main（String[] args） {
//TODO 自動生成的方法存根
nQueen(4)。
}
我不明白的是，為什么我的答案是空的，而我可以在日志串列中看到被添加到我的答案中。 我是不是犯了什么愚蠢的錯誤。請幫助我解決這個問題。如果可能的話，請幫我提供鏈接以了解這個問題，以及我如何在未來避免這些問題。
uj5u.com熱心網友回復：
我認為你認為當JVM執行
時 ans.add(position)。
它正在復制positions的當前狀態并將其添加到串列中。其實不然，它所做的正是代碼中所說的：將一個ArrayList的參考添加到ans。
ans中的所有專案都是對同一個ArrayList的參考，而當你列印出ans時，這個陣列串列是空的。
uj5u.com熱心網友回復：
ans.add(position);
就是你的 "問題"。你只是向ans添加了一個對串列positions的參考。因此，ans充滿了對同一個positions串列的參考。當你在插入后多次修改positions，直到清空它，在最后ans充滿了對同一個positions串列的n參考（n是找到的解決方案的數量），這個串列在最后是空的。
你需要的是在找到一個解決方案的時候，插入一份當前positions串列的副本：
ans.add(new ArrayList<Integer> (position))。
復制是通過構建一個新的串列，其內容與原始串列完全相同而得到的。
uj5u.com熱心網友回復：
添加這個檢查，確保它大于零，然后列印出答案。此外，添加print queen函式，你會清楚地看到答案。如果這能解決你的問題，請把它作為答案。
for（ArrayList<Integer> list : ans）{
if (list.size() > 0)
System.out.println(list)。
}
static void solveNQueenRec(int n, int col, boolean[] [] placed, ArrayList< Integer> positions） {
if (col == n)
printQueens(position)。
for (int row = 0; row < n & col < n; row ) {
if (isSafe(row, col, placed, n)) {
placed[row][col] = true;
positions.add(row 1)。
solveNQueenRec(n, col 1, placed, positions)。
placed[row][col] = false;
positions.remove(position.size() - 1) 。
}
}
//return null;
}
public static void printQueens(ArrayList< Integer> q) {
int n = q.size（）。
for (int i = 0; i < n; i ) {
for (int j = 1; j <=n; j ) {
if (q.get(i) == j)
System.out.print("Q"/span>)。
else[/span
System.out.print("*")。
}
System.out.println()。
}
System.out.println()。
}
4-queens樣本的解決方案。
* Q * *
* * * Q
Q * * *
* * Q *
* * * Q
* Q * *
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/308813.html
標籤：