Làm thế nào để bạn kiểm tra đường chéo trong n-queens?

Question

Tôi đang nghiên cứu trình theo dõi n-nữ hoàng. Ai đó có thể giải thích cho tôi cách kiểm tra số diagonals other_row_pos không? Tôi không chắc chắn tại sao nó hoạt động hoặc cách nó hoạt động.

lấy từ 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

Hãy delta_row = sự khác biệt trong hàng giữa hai nữ hoàng, và delta_col = sự khác biệt trong cột. Hai nữ hoàng sẽ ở cùng một đường chéo nếu delta_row == delta_col hoặc delta_row == -delta_col.

Với các biến bạn có:

delta_row = other_row_pos - row_position 
delta_col = queen_number - i 

Vì vậy, các nữ hoàng đang ở trên cùng một đường chéo nếu:

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

Nếu bạn thêm row_position cho cả hai bên của bình đẳng, bạn sẽ có được điều kiện trong mã của bạn:

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

Answer 2

Hãy xem xét bạn phải kiểm tra xem phần tử bảng (x, y) có thể bị tấn công từ bất kỳ phần tử đường chéo nào hay không. (x, y) có thể bị tấn công theo đường chéo nếu bất kỳ phần tử nằm trên phần tử chéo của nó là một queen.Assume (p, q) là thành phần bảng có một điều kiện queen.Now cho phần tử (x, y) nằm trên tọa độ chéo của bảng phần tử (p, q) sẽ là p + q == x + y hoặc pq == xy. Điều này cũng có thể được hiểu là điều kiện cho các phần tử (p, q) và (x, y) nằm trên cùng một đường chéo. , nếu có nữ hoàng tại (p, q) và chúng ta phải kiểm tra xem (x, y) có thể bị tấn công bởi nữ hoàng này hay không, điều kiện này sẽ là: -

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

chức năng đầy đủ để kiểm tra nếu phần tử tại (x, y) tức là, bảng [x, y] bị tấn công bởi các phần tử chéo hoặc không phải là: -

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; 
      } 
     } 
    } 

chức năng đầy đủ để kiểm tra nếu phần tử (x, y) bị tấn công hay không sẽ là: -

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; 
} 

Hope this helps !!!