现在我正试图解决8x8板上有8个皇后的问题,你必须把它们放在没有一个可以捕获另一个的地方 . 这是使用递归的非常流行的问题,但是我仍然无法弄清楚为什么它不起作用 . 以下是检查展示位置是否有效的主要代码,然后如果它是有效的展示位置,则会放置皇后,否则尝试将皇后放在右边一个单元的位置(新列,同一行) . 这是代码:
private boolean placeQueen(int row, int column)
{
if(check(row, column))
{
board[column][row] = 'Q';
queenCount++;
return true;
}else if(column == board.length)
{
queenCount++;
return false;
}else
{
return (placeQueen(row, column + 1));
}
//return false;
}
private boolean check(int row, int column)
{
//checking vertical axis
for(int i = 0; i < board.length; i++)
{
if(board[column][i] == 'Q' && i != row)
{ //does not check its own row
return false;
}
}
int i = column;
int j = row;
//left one, up one
while(i >= 0 && j >= 0)
{
try{
if(board[i--][j--] == 'Q')
{
return false;
}else
{
i--;
j--;
}
}catch(ArrayIndexOutOfBoundsException e)
{
break;
}
}
i = column;
j = row;
//right one, up one
while(i <= 8 && j >= 0)
{
try{
if(board[i++][j--] == 'Q')
{
return false;
}else
{
i++;
j--;
}
}catch(ArrayIndexOutOfBoundsException e)
{
break;
}
}
return true;
}
我只需要检查向上的对角线,因为我在放下它时放置了皇后 . 这是输出,这是不正确的:
Q * * * * * * *
* Q * * * * * *
* * * Q * * * *
* * Q * * * * *
* * * * * * * Q
* * * * * * Q *
* * * * Q * * *
* * * * * Q * *
它是我的递归方式,还是我如何检查对角线?
这是我如何运行它
public void run()
{
createBoard();
while(queenCount != board.length)
{
placeQueen(queenCount, 0);
}
printBoard();
}
1 回答
这是Queens problem上的众多例子之一
希望它会有所帮助......