我需要写一个算法,使用回溯来解决问题。我想出了以下代码:
public boolean queenPuzzleRec(int queens) {
if(queens == SIZE) {
boardToString();
return true;
}
for(int i=0; i<SIZE; i++) {
for(int j=0; j<SIZE; j++) {
if(Legal(i, j)) {
board[i][j]=true;
if(queenPuzzleRec(queens+1)) {
return true;
}
else {
board[i][j]=false;
}
}
}
}
return false;
}
该代码仅适用于某些电路板尺寸,但不适用于所有尺寸。例如,对于SIZE = 6,解决方案如下:
1 0 0 0 0 00 0 0 1 0 00 0 0 0 0 10 0 0 0 1 00 0 1 0 0 00 1 0 0 0 0
例如,对于SIZE = 8,10和11,也会发生相同的错误(两个对角线彼此相邻,但对于4,5,7或9不会这样做。
同时,我读到了正确的算法,但是我不明白为什么我的算法不能很好地工作。顺便说一句,问题不在于Legal(i,j)方法(我检查了有问题的场景,并将其与工作代码一起使用-但当然,如果需要的话,我会添加它)
只需再次说明-我不需要解决问题,我想知道我的代码有什么问题。
谢谢
编辑-法律功能:
public boolean Legal(int i, int j) {
if (i >= SIZE || j >= SIZE) {
return false;
}
// checks row
for (int k = 0; k < SIZE; k++) {
if (board[i][k] == true) {
return false;
}
}
// checks col
for (int k = 0; k < SIZE; k++) {
if (board[k][j] == true)
return false;
}
int row = i;
int col = j;
// first diagonal forward
while (row < SIZE && col < SIZE) {
if (board[row][col] == true)
return false;
row++;
col++;
}
row = i;
col = j;
// first diagonal backward
while (row >= 0 && col >= 0) {
if (board[row][col] == true)
return false;
row--;
col--;
}
row = i;
col = j;
// second diagonal forward
while (row >= 0 && col < SIZE) {
if (board[row][col] == true)
return false;
row--;
col++;
}
row = i;
col = j;
// second diagonal backward
while (row < SIZE && col >= 0) {
if (board[i][j] == true)
return false;
row++;
col--;
}
return true;
}