7

我正在研究 n-queen 回溯器。有人可以向我解释如何other_row_pos检查对角线吗？我不确定它为什么起作用或如何起作用。

取自维基书籍 - http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens：

bool isSafe(int queen_number, int row_position) {
    // Check each queen before this one
    for(int i=0; i<queen_number; i++) {
        // Get another queen's row_position
        int other_row_pos = position[i];
        // Now check if they're in the same row or diagonals
        if(other_row_pos == row_position || // Same row
           other_row_pos == row_position - (queen_number-i) || // Same diagonal
           other_row_pos == row_position + (queen_number-i))   // Same diagonal
            return false;
    }
    return true;
}
4

2 回答 2

9

让delta_row= 两个皇后之间的行差异，并且delta_col= 列的差异。delta_row == delta_col如果或，两个皇后将在同一对角线上delta_row == -delta_col。

使用您拥有的变量：

delta_row = other_row_pos - row_position
delta_col = queen_number - i

所以皇后在同一对角线上，如果：

other_row_pos - row_position == queen_number - i ||
other_row_pos - row_position == -(queen_number - i)

如果你添加row_position到等式的两边，你会在你的代码中得到条件：

other_row_pos == row_position + (queen_number-i) ||
other_row_pos == row_position - (queen_number-i)
于 2013-10-22T17:23:13.473 回答
2

考虑您必须检查是否可以从任何对角元素攻击棋盘元素 (x,y)。如果位于其对角元素上的任何元素是皇后，则可以对角攻击 (x,y)。假设 (p,q) 是具有皇后的棋盘元素。现在条件元素 (x,y) 位于棋盘的对角坐标上元素 (p,q) 将是 p+q == x+y 或 pq == xy 。这也可以解释为元素 (p,q) 和 (x,y) 位于同一对角线上的条件。所以, 如果 (p,q) 有皇后并且我们必须检查 (x,y) 是否可以被这个皇后攻击, 条件是:-

            if((board[p][q] == 1 ) && ((p+q == x+y) || (p-q == x-y))){
                return true; 
            }

检查 (x,y) 处的元素，即 board[x,y] 是否被对角元素攻击的完整功能是：-

for(int p=1;p<board.length;p++){
        for(int q=1;q<board.length;q++){

            if(p==x && q==y){   //skipping check if element under consideration is same
                continue;
            }

            if((board[p][q] == 1 )&& ((p+q == x+y) || (p-q == x-y))){
                return true;
            }
        }
    }

检查元素（x，y）是否受到攻击的完整功能是：-

    public static boolean is_attacked(int x,int y,int board[][],int n){
    for(int i = 1;i < board.length;i++){
        if(board[x][i] == 1){            //if any cell in xth row is 1 i.e.,queen is there in that row
            return true;
        }
    }
    for(int i = 1;i < board.length;i++){     
        if(board[i][y] == 1){         //if any cell in yth column is 1 i.e.,queen is there in that column
            return true;
        }
    }
    for(int p=1;p<board.length;p++){
        for(int q=1;q<board.length;q++){

            if(p==x && q==y){
                continue;
            }

            if((board[p][q]== 1 )&& ((p+q== x+y) || (p-q == x-y))){
                return true;
            }
        }
    }
    return false;
}

希望这可以帮助！！！

于 2018-01-04T18:57:21.483 回答