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

Tags: , ,



I’m trying to complete the nQueens puzzle problem with a 2D array. I’m having trouble checking to see if an element diagonal to the current element is occupied? I tried doing another for loop, but it only changes the output of the next row and then the rest are the same.

Here’s my code:

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

The issue is with isSafe, the method was not checking the diagonal elements which is why it was merely advancing to the next diagonal because the current checks would have advanced to the next row [ fillPositions(board, r+1) ] and isSafe was just scanning the columns to the left.

Following modifications should help

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


Source: stackoverflow