c++ - 你如何测试 n-queens 中的对角线？

Question

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

摘自 wikibooks - 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;
}

Answer 1

令 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)