(8 Queens) Find out if a Queen fits in 2D matrix

Question

I'm attempting to write a program which solves the 8 Queens Problem using a 2 dimensional array of booleans. I will use backtracking to find the solution. I know this is not the optimal way to solve this problem, and that I should probably go for a 1D array for simplicity, but I want to solve it this way.

Right now I'm stuck on the function which is supposed to check whether a queen fits at a given coordinate. My row, column and down-right diagonal checks work, but I can't get the down-left diagonal check to work. I'm struggling to find the correct indexes of i and j (x and y) to start at, and which counter to increment/decrement for each iteration. Right now my function looks like this:

public static boolean fits(int x, int y) {

    for(int i = 0; i < N; i++) {
        if(board[x][i]) {
            return false; // Does not fit on the row
        }
    }

    for(int i = 0; i < N; i++) {
        if(board[i][y]) {
            return false; // Does not fit on the column
        }
    }

    for(int i = Math.max(x-y, 0), j = Math.max(y-x, 0); i < N && j < N; i++, j++) {
        if(board[i][j]) {
            return false; // Down right diagonal issue
        }
    }

    for(int i = Math.min(x+y, N-1), j = Math.max(N-1-x, 0); i >= 0 && j < N; i--, j++) {
        if(board[i][j]) {
            return false; // Supposed to check the down-left diagonal, but does not work.
        }
    }

    return true;
}

As you can see there's a problem with the last loop here. I'd be very, very happy if someone could give me a working for-loop to check the down-left diagonal. Thanks in advance!

---

Edit: Here's the working code:

public class MyQueens {

    static boolean[][] board;
    static final int N = 8;

    public static void main(String[] args) {
        int p = 0;

        board = new boolean[N][N];

        board[1][1] = true;

        System.out.println(fits(0, 2));
        System.out.println(fits(2, 2));
    }

    public static boolean fits(int x, int y) {

        for(int i = 0; i < N; i++) {
            if(board[x][i]) {
                return false; // Row
            }
        }

        for(int i = 0; i < N; i++) {
            if(board[i][y]) {
                return false; // Column
            }
        }

        for(int i = 0, j = 0; i < N && j < 0; i++, j++) {
            if(board[i][j]) {
                return false; // for right diagonal
            }
        }

        int mirrorx = (N-1)-x;
        for(int i = Math.max(mirrorx-y, 0), j = Math.max(y-mirrorx, 0); i < N && j < N; i++, j++) {
            if(board[(N-1)-i][j]) {
                return false;
        }
    }

        return true;
    }

}

Answer 1

I'm attempting to write a program which solves the 8 Queens Problem using a 2 dimensional array of booleans.

This is not the optimal representation, because you must use four loops to check if a queen can be placed or not. A much faster way of doing it is available.

For the purposes of your program, there are four things that must be free of threats in order for a queen to be placed:

• A row,
• A column,
• An ascending diagonal, and
• A descending diagonal

Each of these four things can be modeled with a separate array of booleans. There are eight rows, eight columns, fifteen ascending diagonals, and fifteen descending diagonals (including two degenerate cases of one-cell "diagonals" in the corners).

Declare four arrays row[8], col[8], asc[15] and desc[15], and use these four methods to work with it:

public static boolean fits(int r, int c) {
    return !row[r] && !col[c] && !asc[r+c] && !desc[c-r+7];
}
public static void add(int r, int c) {
    set(r, c, true);
}
public static void remove(int r, int c) {
    set(r, c, false);
}
private static void set(int r, int c, boolean q) {
    row[r] = col[c] = asc[r+c] = desc[c-r+7] = q;
}

Answer 2

Just flip the board horizontally and reuse the same algorithm as for the down right diagonal:

int mirrorx = (N-1)-x;
for(int i = Math.max(mirrorx-y, 0), j = Math.max(y-mirrorx, 0); i < N && j < N; i++, j++) {
    if(board[(N-1)-i][j]) {
        return false;
    }
}

You could re-arrange it to make it more optimal.

Answer 3

Why don't you just use:

for(int i = 0, j = 0; i < N && j < 0; i++, j++) {
        if(board[i][j]) {
            return false; // for right diagonal
        }
    }

Similarly:

for(int i = 0, j = N-1; i < N && j >= 0; i++, j--) {
        if(board[i][j]) {
            return false; // for left diagonal
        }
    }