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_row2 つのクイーン間の行の差、およびdelta_col= 列の差とします。delta_row == delta_colまたはの場合、2 つのクイーンは同じ対角線上にあり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 に答える