1
\$\begingroup\$

I am trying to solve the 8 queens problem using a heuristic similar to "the accessibility heuristic" used in Knight's Tour problem. this heuristic simply means that each square of the chess board has the value of the numbers of squares that will be attacked if the queen is placed on that square. and asks me to place the next queen in the square that carries the lowest number (that attacks the least number of squares).

I think I did it and here's my code, please check if there are an errors or better ways to do things.

public class Queen {
private final int SIZE = 8;//board size
private int[][] board;//chess board
private int[]hor;//horizontal moves
private int[]ver;//vertical moves
private int eliminatedSquares;
private int remainingSquares;

public Queen () {
    //constructor initializes the board
    //initializes the moves


    board = new int[SIZE][SIZE];

    //first row
    board[0][0] = 21;
    board[0][1] = 21;
    board[0][2] = 21;
    board[0][3] = 21;
    board[0][4] = 21;
    board[0][5] = 21;
    board[0][6] = 21;
    board[0][7] = 21;
    //second row
    board[1][0] = 21;
    board[1][1] = 23;
    board[1][2] = 23;
    board[1][3] = 23;
    board[1][4] = 23;
    board[1][5] = 23;
    board[1][6] = 23;
    board[1][7] = 21;
    //third row
    board[2][0] = 21;
    board[2][1] = 23;
    board[2][2] = 25;
    board[2][3] = 25;
    board[2][4] = 25;
    board[2][5] = 25;
    board[2][6] = 23;
    board[2][7] = 21;
    //forth row
    board[3][0] = 21;
    board[3][1] = 23;
    board[3][2] = 25;
    board[3][3] = 27;
    board[3][4] = 27;
    board[3][5] = 25;
    board[3][6] = 23;
    board[3][7] = 21;
    //fifth row
    board[4][0] = 21;
    board[4][1] = 23;
    board[4][2] = 25;
    board[4][3] = 27;
    board[4][4] = 27;
    board[4][5] = 25;
    board[4][6] = 23;
    board[4][7] = 21;
    //sixth row
    board[5][0] = 21;
    board[5][1] = 23;
    board[5][2] = 25;
    board[5][3] = 25;
    board[5][4] = 25;
    board[5][5] = 25;
    board[5][6] = 23;
    board[5][7] = 21;
    //seventh row
    board[6][0] = 21;
    board[6][1] = 23;
    board[6][2] = 23;
    board[6][3] = 23;
    board[6][4] = 23;
    board[6][5] = 23;
    board[6][6] = 23;
    board[6][7] = 21;
    //eighth row
    board[7][0] = 21;
    board[7][1] = 21;
    board[7][2] = 21;
    board[7][3] = 21;
    board[7][4] = 21;
    board[7][5] = 21;
    board[7][6] = 21;
    board[7][7] = 21;

    //initializing moves
    hor = new int[SIZE];
    ver = new int[SIZE];
    //right
    hor[0] = 1;
    ver[0] = 0;
    //left
    hor[1] = -1;
    ver[1] = 0;
    //up
    hor[2] = 0;
    ver[2] = -1;
    //down
    hor[3] = 0;
    ver[3] = 1;
    //upper right
    hor[4] = 1;
    ver[4] = -1;
    //upper left
    hor[5] = -1;
    ver[5] = -1;
    //down right
    hor[6] = 1;
    ver[6] = 1;
    //down left
    hor[7] = -1;
    ver[7] = 1;

}//end constructor

public void displayBoard () {
    //displays the board

    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board[row].length; col++) {
            if (board[row][col] == -1) {
                System.out.printf("|%-2s|","*");
            }
            else {
                System.out.printf("|%-2d|",board[row][col]);
            }

            if (board[row][col] == 0 || board[row][col] == -1) {
                ++eliminatedSquares;
            }
        }//end inner for
        System.out.println();
    }//end for

}//end displayBoard

public boolean possibleMove (int move, int row, int col) {
    //tests whether a move is valid

    if (move < 0 || move > 7)  {
        return false;
    }//end if
    else if (row + ver[move] < 0|| row + ver[move] > 7) {
        return false;
    }//end else if
    else if (col + hor[move] < 0|| col + hor[move] > 7) {
        return false;
    }//end else if
    else{
        return true;
    }//end else

}//end possibleMove

public void placeQueen (int row, int col) {
    //eliminates the squares attacked by the current square of the queen
    board[row][col] = -1;
    ++eliminatedSquares;
    //try the eight possible moves
    for (int move = 0; move < SIZE; move++) {
        int r = row;
        int c = col;
        while (possibleMove(move, r, c)) {
            r += ver[move];
            c += hor[move];
            if (board[r][c] != -1 && board[r][c] > 0) {
                board[r][c] = 0;
                decreaseAccessibilty(r, c);
                ++eliminatedSquares;
            }
        }//end while
    }//end for
}//placeQueen

public boolean testSquare (int row, int col) {

    if (board[row][col] > 0) {
        return true;
    }
    else {
        return false;
    }
}


public void decreaseAccessibilty (int row, int col) {
    for (int move = 0; move < SIZE; move++) {
        int r = row;
        int c = col;
        while (possibleMove(move, r, c)) {
            r += ver[move];
            c += hor[move];
            if (board[r][c] > 0) {
                board[r][c]--;
            }//end if
        }//end while
    }
}//end decrease accessibility 

public int getAccessibility (int row, int col) {
    //returns the accessibility number of a square
    return board[row][col];

}

public int getEliminatedSquares () {
    return eliminatedSquares;
}
public int getRemainingSquares () {
    remainingSquares = 64 - eliminatedSquares;
    return remainingSquares;
}   }//end Queen

public class QueenTest {
private static int lowest;
public static void main(String[] args) {
    Queen q = new Queen();

    int nextRow = 0;
    int nextCol = 0;
    lowest = q.getAccessibility(nextRow, nextCol);
    int remaining = q.getRemainingSquares();
    while (remaining != 0) {

        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                if (q.testSquare(row, col)) {
                    lowest = q.getAccessibility(row, col);
                    nextRow = row;
                    nextCol = col;
                    col = 8;
                    row = 8;
                }
            }
        }

        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                if (q.getAccessibility(row, col) > 0 && q.getAccessibility(row, col) <= lowest) {
                    lowest = q.getAccessibility(row, col);
                    nextRow = row;
                    nextCol = col;
                }
            }
        }

        q.placeQueen(nextRow, nextCol);

        remaining = q.getRemainingSquares();
        System.out.printf("queen placed at %d, %d\n", nextRow, nextCol);
    }

    q.displayBoard();
}}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I think I did it and here's my code, please check if there are an errors or better ways to do things.

Do not get it wrong, but to ask it in a direct way: Did you try to run the code? You could see directly that the proposed solution is not a solution. There are only 7 queens.

Which shows the problem with the heuristic: It can help to find the next good move, but it could also fail and lead to a dead end.

I do not think that it is a good approach to make comments about the style for the non working solution. First, you should get a working solution, probably with a backtracking approach.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.