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

Question

我正在尝试用二维数组完成 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 上，该方法没有检查对角线元素，这就是为什么它只是前进到下一个对角线，因为当前检查会前进到下一行 [ 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;
    }

Answer 2

要检查所有可能的 8 个方向，这里是 C++ 代码。这里，

board 是你的 2d array/vector,
row和col为位置参数，
n 是您 row/col 的大小。

#include <bits/stdc++.h>

bool possible(vector<vector<int>> board, int row, int col, int n){
    int i, j;
    
    /* Check this col on up side */
    for (i = 0; i < row; i++)
        if (board[i][col])
            return false;
            
    /* Check this col on down side */
    for (i = row; i < n; i++)
        if (board[i][col])
            return false;
            
    /* Check this row on left side */
    for (j = 0; j < col; j++)
        if (board[row][j])
            return false;
            
    /* Check this row on right side */
    for (j = col; j < n; j++)
        if (board[row][j])
            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<n; i++, j--)
        if (board[i][j])
            return false;
            
    /* Check upper diagonal on right side */
    for (i=row, j=col; i>=0 && j<n; i--, j++)
        if (board[i][j])
            return false;
            
    /* Check lower diagonal on right side */
    for (i=row, j=col; j<n && i<n; i++, j++)
        if (board[i][j])
            return false;

    return true;
}

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

How can I check if a diagonal element in 2D array is occupied?

java

multidimensional-array

n-queens