Как вы проверяете диагональ в n-ферзях?

Question

Как вы проверяете диагональ в n-ферзях?

Я изучаю 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;
}

5

c++n-queens

Решение

Другие решения

Учтите, что вы должны проверить, можно ли атаковать элемент доски (x, y) с любого диагонального элемента или нет. (x, y) может быть атакован по диагонали, если любой элемент, лежащий на его диагональном элементе, является королевой. Assume (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;
}

Надеюсь это поможет!!!

1

Источник

Accepted Answer

Позволять 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)

7