我正在使用堆棧而不是遞歸調用來解決 N 皇后問題，以便找到 N 皇后的解決方案總數。我相信我的程序是有效的，只是我無法弄清楚如何打破尋找解決方案的循環。有哪些方法可以解決這個問題？這是我的計算機科學課程之一，使用 java。我已經嘗試過我的朋友建議的方法，即在當前行位于棋盤內時暫時滿足條件，但這導致在找到解決方案之前停止解決方案搜索出現一些問題。我還嘗試在堆棧大小為1時跳出循環，但這僅在N = 4時有效，不適用于較大的N值，該程序也可能不適用于N > 4，尚未測試過還沒有。當 N = 5 時以及當Exception in thread "main" java.util.EmptyStackException at java.base/java.util.Stack.peek(Stack.java:102) at java.base/java.util.Stack.pop(Stack.java:84) at Assignment22.stacker(Assignment22.java:61) at Assignment22.main(Assignment22.java:11)我預計程序最終會停止，但我遇到了無限循環，并且根據我嘗試過的修復，出現 ArrayIndexOutOfBoundsException 或 EmptyStackException
1 回答
HUWWW
TA貢獻1874條經驗 獲得超12個贊
我發現的主要問題是，當 N > 4 時，皇后不能放置在最后一列的任何位置，所以我修改了這個條件
if (!(col < board[row].length - 1)) {
col = queensPos.pop();
row -= 1;
board[row][col] = false;
numQueens += 1;
col += 1;
} else {
col += 1;
}
并添加了 row > 0 的條件
最終堆垛方法：
public static int stacker(boolean[][] board, int numQueens) {
Stack<Integer> queensPos = new Stack<Integer>();
int row = 0;
int col = 0;
int numSolutions = 0;
int colLastUsed = 0;
// need to figure out how to tell program to
// go back to previous row and remove queen
// if col = 3 and row = 1, queen will always be placed there
// however if queen is placed there, there is no solution
// if row being worked on is in the board
while (row <= board.length) {
// if you have no more queens to place
if (numQueens == 0) {
// you have a solution
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j]) {
System.out.print("Q");
} else {
System.out.print("*");
}
}
System.out.println();
}
System.out.println();
/*for (int i = 0; i < queensPos.size(); i++) {
System.out.print(queensPos.get(i) +" ");
}
System.out.println();*/
numSolutions += 1;
// go back to last row
row -= 1;
// remove queen
col = queensPos.pop();
board[row][col] = false;
// go back one row
//row -= 1;
numQueens += 1;
if (col < board.length - 1) {
// add one to col if it is not at end of row
col += 1;
} else {
// go back another row
row -= 1;
col = queensPos.pop();
board[row][col] = false;
numQueens += 1;
col += 1;
}
// if there is a conflict and column is within board
} else {
if (col == board[row].length && row == 0) {
break;
} else if (IsConflictPresent(board, row, col) && col < board[row].length - 1) {
// shift queen rightward
col += 1;
// if column is out of board
} else if (IsConflictPresent(board, row, col) && col == board[row].length - 1) {
// look at value of column, if it is at end of board
// go back to previous row
// looks at top of stack
col = queensPos.pop();
if (row > 0) {
row -= 1;
}
board[row][col] = false;
numQueens += 1;
// attempt to solve problem where queen at end of 2nd row would keep getting placed
// appears to be working
if (!(col < board[row].length - 1) && row > 0) {
col = queensPos.pop();
row -= 1;
board[row][col] = false;
numQueens += 1;
col += 1;
} else {
col += 1;
}
// how to check to see if the column number you used
} else {
// if queen can be placed
// place queen at row, col
board[row][col] = true;
queensPos.push(col);
numQueens -= 1;
// move to next row
row += 1;
// start at beginning of row
col = 0;
}
}
}
return numSolutions;
}
添加回答
舉報
0/150
提交
取消