主题:关于八皇后中一个隐含的问题
我看到数据结构书中有关八皇后的代码如下:
void ChessBoard::putQueen(int row) {
for (int col = 0; col < squares; col++)
if (column[col] == available &&
leftDiagonal [row+col] == available &&
rightDiagonal[row-col+norm] == available) //判断当前点是否可
//放置皇后。
{
positionInRow[row] = col;
column[col] = !available; //把当前点所引发的不 可放置皇后的点置为无效
leftDiagonal[row+col] = !available;
rightDiagonal[row-col+norm] = !available;
if (row < squares-1)
putQueen(row+1); //进入递归
else printBoard(cout);
column[col] = available; [color=FF0000]//重置无效点为有效[/color]
leftDiagonal[row+col] = available;
rightDiagonal[row-col+norm] = available;
}
}
那么因此而产生一个问题,例如当我0,0点放置皇后后,那么0行,0列,以及它的对角线都是无效了,进入第二行搜索到,(1,2)点为有效,放置皇后,继续搜索后发现不满足条件,那么就要回滚到上一步,即撤销(1,2)点换成(1,3)点。那么当撤销(1,2)点的时候,它就把整个行1,列2以及对角线都置为有效了(譬如(2,2)点)),而(2,2)点对于刚开始第一步的(0,0)点显然是无效的,那么在接下来的搜索中就会出现错误。请问以上书中的代码为什么没有解决这个错误?还是我理解有误
void ChessBoard::putQueen(int row) {
for (int col = 0; col < squares; col++)
if (column[col] == available &&
leftDiagonal [row+col] == available &&
rightDiagonal[row-col+norm] == available) //判断当前点是否可
//放置皇后。
{
positionInRow[row] = col;
column[col] = !available; //把当前点所引发的不 可放置皇后的点置为无效
leftDiagonal[row+col] = !available;
rightDiagonal[row-col+norm] = !available;
if (row < squares-1)
putQueen(row+1); //进入递归
else printBoard(cout);
column[col] = available; [color=FF0000]//重置无效点为有效[/color]
leftDiagonal[row+col] = available;
rightDiagonal[row-col+norm] = available;
}
}
那么因此而产生一个问题,例如当我0,0点放置皇后后,那么0行,0列,以及它的对角线都是无效了,进入第二行搜索到,(1,2)点为有效,放置皇后,继续搜索后发现不满足条件,那么就要回滚到上一步,即撤销(1,2)点换成(1,3)点。那么当撤销(1,2)点的时候,它就把整个行1,列2以及对角线都置为有效了(譬如(2,2)点)),而(2,2)点对于刚开始第一步的(0,0)点显然是无效的,那么在接下来的搜索中就会出现错误。请问以上书中的代码为什么没有解决这个错误?还是我理解有误