Wie testen Sie für Diagonale in N-Queens?

Question

Ich studiere die N-Königin Backtracker. Kann mir jemand erklären wie other_row_pos nach Diagonalen sucht? Ich bin mir nicht sicher, warum es funktioniert oder wie es funktioniert.

von wikibooks genommen - 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

Lassen delta_row = die Differenz in Reihen zwischen den beiden Königinnen, und delta_col = die Differenz in den Spalten. Die beiden Königinnen sind auf der gleichen Diagonale, wenn delta_row == delta_col oder delta_row == -delta_col.

Mit den Variablen Sie haben:

delta_row = other_row_pos - row_position 
delta_col = queen_number - i 

So sind die Königinnen sind auf die gleiche Diagonale, wenn:

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

Wenn Sie row_position auf beide Seiten der Gleichung hinzufügen, erhalten Sie den Zustand in Ihr Code:

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

Answer 2

Sie müssen überprüfen, ob Board-Element (x, y) kann von jedem Diagonalelement angegriffen werden oder nicht. (x, y) kann diagonal angegriffen werden, wenn ein Element, das auf seinem diagonalen Element liegt, eine Königin ist.Assume (p, q) ist Brettelement mit einer Königin.Now Bedingung für Element (x, y) auf Diagonalkoordinaten der Platine zu liegen Element (p, q) wäre p + q == x + y oder pq == xy. Dies kann auch als Bedingung für Elemente (p, q) und (x, y) interpretiert werden, die auf derselben Diagonale liegen wenn es Königin bei (p, q) ist, und wir müssen prüfen, ob (x, y) von dieser Königin angegriffen werden kann oder nicht, ist die Bedingung dafür wäre: -

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

komplette Funktion zur Überprüfung Wenn das Element bei (x, y) dh die Platte [x, y] von diagonalen Elementen angegriffen wird oder nicht, wäre: -

komplette Funktion zum Überprüfen, ob Element (x, y) angegriffen wird oder nicht wäre: -

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

hoffte, das hilft !!!