CODEWITHSUNDEEP
javan-queens
user12001836
user12001836

Reputation:

Diagonally check the n queen JAVA

I am having a problem about understanding the code i got online. It's the checking of the queen if there's a collision with other queens. Can somebody explain to me what does this do? The first condition, I knew it's the checking of the same row, but what about the absolute number?

if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) 
{
     return false;
}

Here is the full code:

class NQueen {

private int[] board;
private int size;
private ArrayList allSolutions = null;

public int[] getBoard() {
    return board;
}
public ArrayList getAllSolutions() {
    return this.allSolutions;
}
public NQueen(int size) {
    this.size = size;
    board = new int[this.size];
    this.allSolutions = new ArrayList();
}
public void place(int row) {
            // base case
    if (row == size) {
        int[] temp = new int[size];
                    // copy in temp array
        System.arraycopy(board, 0, temp, 0, size);
                    // add to the list of solution
        allSolutions.add(new Solution(temp));
        return ;
    } else {
        for (int i = 0; i < size; i++) {

            board[row] = i;
                            /* when you place a new queen
                             * check if the row you add it in, isn't 
                             * already in the array. since the value of arrray is
                             * the row, so we only need to check the diagonals no need to check for collisions on the left or right. 
                             * As long as there is no duplicate values in the array.*/
            if (valid(row)){
                               place(row + 1);
                            }

        }
    }
}
public boolean valid(int row) {
    for (int i = 0; i < row; i++) {
                    // if same row  or same diagonal
        if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) 
                    {
                        return false;
        }
    }
    return true;
}

}

Upvotes: 0

Views: 711

Answers (1)

knittl
knittl

Reputation: 265341

If you have a 2-dimensional array and each position on the board "cell" in the array, then to be in the same diagonal, a piece have to have the same horizontal and vertical distance.

Math.abs(board[row] - board[i]) == (row - i)

Checks exactly that. The Math.abs is because the second piece can be top-left, top-right, bottom-right, and bottom-left. Not sure how exactly your algorithm is implemented, but it's probably a good idea to take the absolute value of the second operand too.

Example with a small board:

  1 2 3 4
1
2 x
3
4     y

So here we have a horizontal distance of 2 (abs(1-3)) and a vertical distance also of 2 (abs(2-4))

Example 2:

  1 2 3 4
1       x
2     y
3 
4

Here we have only horizontal and vertical distance of only 1 (abs(4-3) and abs(1-2))

Follow up

Your array stores in each element the position of the queen in this row. So it is only a one-dimensional array (not two dimensional as originally suggested by me).

So for my first example your array would contain:

[ 0, 1, 0, 3 ]

(I think the code from the OP assumes 0-based positions but initializes the array elements with 0 (new int[size]). This might be a bug, because 0 is a valid position and could conflict with other constraints, i.e. you will not be able to place a queen on index 1 if the queen from the previous or next row is uninitialized (=position 0).)

Back to the example (using 1-based indices for clarity and to avoid the bug mentioned above): a[2] - a[4] == 1 - 3 (a[2] == 1, a[4] == 3)

If the "y" piece was moved to column 2 instead, then you would get a[2] - a[4] != 1 - 3, because they do not share the diagonal (a[2] == 1, a[4] == 3)

Upvotes: 2

Related Questions