如何检查二维数组中的对角线元素是否被占用？

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