2013-10-22 2 views
5

나는 n-queen 백 트래커를 연구 중입니다. 누군가가 내게 어떻게 설명 할 수 있습니까 other_row_pos 대각선을 확인합니까? 나는 그것이 왜 작동하는지, 어떻게 작동하는지 잘 모르겠습니다. 위키 찍은n-queens의 대각선은 어떻게 테스트합니까?

-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

대각선은 기울기가 ± 1.0 ... –

+0

입니다. 새 여왕이 다른 여왕을 공격하지 않고 위치에 삽입 될 수 있는지 확인합니다. –

+0

제공된 링크에서 할당 취소를 수행 할 방법이 없다고 나타났습니다. 위치 [i]? 이 코드에서 백 추적기는 어디에 있습니까? – runners3431

답변

7

delta_row = 두 행 즈 사이의 차이, 및 = 열 delta_col 차이하자. 두 여왕은 delta_row == delta_col 또는 delta_row == -delta_col 인 경우 동일한 대각선에 위치합니다. 변수와

당신은 :

delta_row = other_row_pos - row_position 
delta_col = queen_number - i 

그래서 여왕은에있는 같은 대각선 경우 : 당신이 평등의 양쪽에 row_position를 추가하는 경우

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

, 당신은 상태를 얻을 수 귀하의 코드 :

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

또는 심지어 abs (other_row_pow - row_position) == abs (queen_number - i)를 선호하는 경우. – SirGuy

1

보드 요소 (x, y)가 어떤 대각선 요소로부터 공격 받았는지 여부. (x, y)는 대각선 요소에 놓인 요소가 여왕이면 대각선으로 공격 할 수 있습니다. 여론 (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]에있는 요소가 대각선 요소에 의해 공격 받거나 그렇지 않으면 다음과 같이됩니다 : -

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

희망이 도움이!