Я работаю над проблемой старых добрых N-королев, используя стек вместо рекурсивных вызовов, чтобы найти общее количество решений для N королев. Я считаю, что программа, которая у меня есть, работает, за исключением того, что мне сложно понять, как выйти из цикла, который находит решения. Какие есть способы сделать это?
Это для одного из моих классов информатики, использующих Java. Я уже попробовал то, что предложил мой друг, чтобы было условие, пока текущая строка находится внутри доски, но это вызвало некоторые проблемы с остановкой поиска решения до того, как решение будет найдено. Я также пытался выйти из цикла, когда размер стека был равен 1, но это работало только при N = 4, но не при больших значениях N, программа также может не работать при N> 4, не проверял этоеще нет.
EmptyStackException, когда 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)
// gets number of solutions to N Queens
public static int stacker(boolean[][] board, int numQueens) {
Stack<Integer> queensPos = new Stack<Integer>();
int row = 0;
int col = 0;
int numSolutions = 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 < queensPos.size(); i++) {
System.out.println(queensPos.get(i));
}
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;
col += 1;
} else {
// if there is a conflict and column is within board
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(); // <- EmptyStackException occurs here
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)) {
col = queensPos.pop();
row -= 1;
board[row][col] = false;
numQueens += 1;
col += 1;
} else {
col += 1;
}
} 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;
// when the below code is put in, EmptyStackException occurs when numQueens = 5
if (queensPos.size() == 1) {
row -= 1;
col = queensPos.pop();
numQueens += 1;
}
}
}
}
return numSolutions;
}
public static boolean IsConflictPresent(boolean[][] boardToCheck, int row, int col) {
// figure out how to check one diagonal
int i,j;
int N = boardToCheck.length;
// use 4 for loops
// check on left side of row specified
for (i = 0; i <= col; i++) {
if (boardToCheck[row][i])
{
return true;
}
}
for (i = 0; i < boardToCheck[row].length - 1; i++) {
if (boardToCheck[i][col]) {
return true;
}
}
// to check diagonal, start at row 0 column 0, go up to row and column specified
// upper diag on left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (boardToCheck[i][j]) {
return true;
}
}
// upper right diagonal check
for (i = row, j = col; i >= 0 && j < N; i--, j++) {
if (boardToCheck[i][j]) {
return true;
}
}
// lower diagonal on left side
for (i = row, j = col; j >= 0 && i < N; i++, j--) {
if (boardToCheck[i][j]) {
return true;
}
}
// lower diagonal on right side
for (i = row, j = col; j < N && i < N; i++, j++) {
if (boardToCheck[i][j]) {
return true;
}
}
return false;
}
Я ожидаю, что программа в конечном итоге остановится, но я получаю бесконечный цикл, и, в зависимости от исправлений, япробовал ArrayIndexOutOfBoundsException или EmptyStackException