你如何测试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)