你如何測試n皇后對角線？

我正在學習n皇后回溯。有人可以向我解釋other_row_pos如何檢查對角線嗎？我不確定它爲什麼有效，或者它是如何工作的。從維基採取你如何測試n皇后對角線？

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

來源

2013-10-22 runners3431

對角線是斜線±1 ... –

它檢查新的女王是否可以插入一個位置而不攻擊其他女王 –

在提供的鏈接中，我注意到沒有辦法做UNDO的轉讓位置[I]？此代碼中的回溯器在哪裏？ – runners3431

讓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)

來源

2013-10-22 17:23:13 interjay

甚至'abs（other_row_pow - row_position）== abs（queen_number - i）'如果有人喜歡。 – SirGuy

考慮您必須檢查板元素（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）處的元素即板[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; 
}

希望這有助於！

來源

2018-01-04 18:57:21

你如何測試n皇后對角線？

回答

相關問題