如何檢查二維數組中的對角線元素是否被佔用？

Question

我正在嘗試用2D數組來完成nQueens拼圖問題。我無法檢查當前元素的對角元素是否被佔用？我試着做另一個for循環，但它只改變了下一行的輸出，其餘的都是一樣的。

這裏是我的代碼：

package main; 

public class Board { 
public static final int n = 8; 

static boolean isSafe(boolean[][]board , int r, int c) { 
    int i; 
    int j; 
    for(i = 0; i < r; i++){ 
     if(board[i][c] == true){ 
      return false; 
      } 
    }  
    return true; 
} 
static boolean fillPositions(boolean [][]board, int r){ 
    for(int c = 0; c < n; c++){ 
     if(isSafe(board, r, c)){ 
      board[r][c] = true; 
      if(r == (n - 1) || fillPositions(board, r+1)){ 
       return true; 
      } 
      board[r][c] = false; 
     } 
    } 
    return false; 
} 

public static void main(String[] args){ 
    boolean[][] board = new boolean[n][n]; 

    if(fillPositions(board, 0)){ 
     for(int i = 0; i < n; i++){ 
      for(int j = 0; j < n; j++){ 
       if(board[i][j]){ 
        System.out.print("|Q"); 
       } else { 
        System.out.print("|*"); 
       } 
      } 
      System.out.println("|"); 
     } 
    } else { 
     System.out.println("None"); 
    } 
} 
} 

Answer 1

的問題是與isSafe，該方法不檢查這就是爲什麼它只是被推進到下一個對角線的對角線元素，因爲當前的檢查會前進到下一個row [fillPositions（board，r + 1）]，isSafe只是掃描左邊的列。

以下修改應該幫助

static boolean _isSafe(boolean board[][], int row, int col) 
    { 
     int i, j; 

     /* Check this row on left side */ 
     for (i = 0; i < row; i++) 
      if (board[i][col]) 
       return false; 

     /* Check upper diagonal on left side */ 
     for (i=row, j=col; i>=0 && j>=0; i--, j--) 
      if (board[i][j]) 
       return false; 

     /* Check lower diagonal on left side */ 
     for (i=row, j=col; j>=0 && i<board.length; i++, j--) 
      if (board[i][j]) 
       return false; 

     return true; 
    }