CODEWITHSUNDEEP
javamultidimensional-arrayn-queens
user3600008
user3600008

Reputation: 31

Java Method that checks for objects diagonally in 2D array

I am doing an N Queens Program in Java. I was able to print all the solutions where each Queen is on a different row and column. Now I need to keep track of the diagonals for collisions. So there are 2n-1 diagonal lines on a 2D array. The algorithm wants us to there are 2n-1 negative diagonal lines and 2n - 1 positive diagonal lines on the chessboard. There is an array of size 2n-1, called d1, that keeps track of the number of queens, i.e., the number of collisions, on each of the 2n-1 negative diagonal lines. If there are k queens on the mth negative diagonal line, there are k-1 collisions on this diagonal line. The number k is written into the mth element of the d1 array. Similarly, we choose another array with size 2n-1, called d2, for 2n-1 positive diagonal lines.

Here is my method for D2, but I am completely lost. I know that all the up diagonals are row + col, but that is it.

      public void D2(){
          int[] upDiag = new int[2*board.length - 1];
          int numberOfCollisions = 0;
             for(int row = 0; row < board.length; row++){
                 for(int col = 0; col < board.length; col++){
                    if(isQueen(row, col)){
                    upDiag[numberOfCollisions++];
                  }   
                }
               }
             }

Upvotes: 0

Views: 812

Answers (1)

wadda_wadda
wadda_wadda

Reputation: 1004

I've written a three-part series on the Eight-Queens/N-Queens Problem.

Here's a general outline of the problem, and a recursive solution.

Here's a genetic algorithm solution.

Here's a simulated annealing solution.

For the collision checking itself, something like this works very well: 

double assessFitness(Integer[] candidate) {
    int collisions = 0;
    final int MAXIMUM_COLLISIONS = calculateMaxCollisions();
    for (int i = 0; i < GRID_SIZE - 1; i++) {
        for (int j = i + 1; j < GRID_SIZE; j++) {
            if ((candidate[i].equals(candidate[j])) || j - i == Math.abs(candidate[i] - candidate[j]))
                collisions++;
        }
    }
    return (MAXIMUM_COLLISIONS - collisions) / (double) MAXIMUM_COLLISIONS;
}

Note that this is adapted from my genetic algorithm solution. I do explain why I return a value that scales from 0 to 1 in the blog article, but in your case a slight modification would yield the result you're looking for:

int countCollisions(Integer[] candidate) {
    int collisions = 0;
    final int MAXIMUM_COLLISIONS = calculateMaxCollisions();
    for (int i = 0; i < GRID_SIZE - 1; i++) {
        for (int j = i + 1; j < GRID_SIZE; j++) {
            if ((candidate[i].equals(candidate[j])) || j - i == Math.abs(candidate[i] - candidate[j]))
                collisions++;
        }
    }
    return collisions;
}

In order for this to work, you do need to calculate the maximum allowable number of collisions for your N-Queens problem. 

private int calculateMaxCollisions() {
    int sum = 0;
    for (int i = GRID_SIZE - 1; i > 0; i--) {
        sum += i;
    }
    return sum;
}

Upvotes: 1

Related Questions