回 帖 发 新 帖 刷新版面

主题:关于八皇后中一个隐含的问题

我看到数据结构书中有关八皇后的代码如下:
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)点显然是无效的,那么在接下来的搜索中就会出现错误。请问以上书中的代码为什么没有解决这个错误?还是我理解有误

回复列表 (共2个回复)

沙发

首先赞一下你的书,用数组判断重复的方法是比较不错的。

是你理解有误,你要观察到这一点,一个点能否放子,要同时满足四个条件:

同一行无子,同一列无子,以及两个对角线无子。

在你书上的这个例子中不需要判断行重复,这个是比较容易理解的。

所以这里有三个判断:
if (column[col] == available &&
    leftDiagonal [row+col] == available &&
    rightDiagonal[row-col+norm] == available) 

回头来看看你所说的(2, 2)点,没错,当撤销(1, 2)点时,第2列的约束没了,但是并不代表(2, 2)所在的对角线上的约束也被取消了。

要这三个约束都没有时,才可以下子。

板凳

非常感谢!!!呵呵

我来回复

您尚未登录,请登录后再回复。点此登录或注册