# Eight Queens Heuristic

1 view

I am developing a heuristic to place 8 queens on the 8x8 chessboard. each square has its elimination number (to indicate how many squares of an empty chessboard are “eliminated” if a queen is placed in that square.) and each queen should be placed in the square which has the lowest elimination number.

my problem is that I don't know what to do to keep decreasing specific elimination numbers of their appropriate squares, so I'll be thankful if you helped me with that. another problem, I feel that my code is very complicated, so any notes to make it more simple?

here's my code

public class Queen {

private final int SIZE = 8;

private int board[][] = new int[SIZE][SIZE]; // 8x8 board

private int hor[] = new int[SIZE]; // horizontal moves

private int ver[] = new int[SIZE]; // vertical moves

private int lowestValue = 22;

private int[][] queens = new int[SIZE][2]; // 8 queens

public Queen () {

// initialize each square with its own elimination number

for (int row = 0; row < board.length; row++) {

for (int col = 0; col < board[row].length; col++) {

if (row == 0 || row == 7 || ((row >= 1 && row <= 6) && (col == 0 || col == 7))) {

board[row][col] = 22;

}

else if ((row == 1 || row == 6) && (col >= 1 && col <= 6) || (row > 1 && row < 6) && (col == 1 || col == 6)) {

board[row][col] = 24;

}

else if ((row == 2 || row == 5) && (col >= 2 && col <= 5)|| (row > 2 && row < 5) && (col == 2 || col == 5)){

board[row][col] = 26;

}

else if ((row == 3 || row == 4) && (col >= 3 && col <= 4)){

board[row][col] = 28;

}

}

}// end initializing

// initialize moves

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

//up right

hor[4] = 1;

ver[4] = -1;

hor[7] = -1;

ver[7] = 1;

//up left

hor[5] = -1;

ver[5] = -1;

//down right

hor[6] = 1;

ver[6] = 1;

// down left

for (int queen = 0; queen < queens.length; queen++) {

placeQueens(queen);

}

displayBoard();

}// end constructor

// eliminate squares according to the place of the queen

private void eliminate (int queen_row, int queen_col) {

// eliminate diagonal

int rowCopy = queen_row;// helper row

int colCopy = queen_col;// helper column

try {

// eliminate up right

for (int move = 0; move < 8; move++) {

rowCopy += ver[4];

colCopy += hor[4];

if (board[rowCopy][colCopy] > 0) {

board[rowCopy][colCopy] = 0;

}

}

}

catch (ArrayIndexOutOfBoundsException e) {

}

try {

rowCopy = queen_row;

colCopy = queen_col;

// eliminate up left

for (int move = 0; move < 8; move++) {

rowCopy += ver[5];

colCopy += hor[5];

if (board[rowCopy][colCopy] > 0) {

board[rowCopy][colCopy] = 0;

}

}

}

catch (ArrayIndexOutOfBoundsException e) {

}

try {

rowCopy = queen_row;

colCopy = queen_col;

// eliminate down right

for (int move = 0; move < 8; move++) {

rowCopy += ver[6];

colCopy += hor[6];

if (board[rowCopy][colCopy] > 0) {

board[rowCopy][colCopy] = 0;

}

}

}

catch (ArrayIndexOutOfBoundsException e) {

}

try {

rowCopy = queen_row;

colCopy = queen_col;

// eliminate down left

for (int move = 0; move < 8; move++) {

rowCopy += ver[7];

colCopy += hor[7];

if (board[rowCopy][colCopy] > 0) {

board[rowCopy][colCopy] = 0;

}

}

}

catch (ArrayIndexOutOfBoundsException e) {

}

// eliminate row

for (int col = 0; col < 8;col++) {

if (board[queen_row][col] > 0) {

board[queen_row][col] = 0;

}

}

// eliminate col

for (int row = 0; row < 8; row++) {

if (board[row][queen_col] > 0) {

board[row][queen_col] = 0;

}

}

}// end elimination

// decrease elimination number of each square

public void decreaseElimination () {

}// end decrease elimination

public void countEliminated () {

int counter = 0;

for (int row = 0; row < board.length; row++) {

for (int col = 0; col < board[row].length; col++) {

if (board[row][col] == 0) {

counter++;

}

}

}

System.out.printf("%d squares eliminated\n", counter);

}

public void placeQueens(int queenNum) {

int targetRow;

int targetCol;

// find lowest elimination number

for (int row = 0; row < board.length; row++) {

for (int col = 0; col < board[row].length; col++) {

if (board[row][col] > 0 && board[row][col] < lowestValue) {

lowestValue = board[row][col];

targetRow = row;

targetCol = col;

queens[queenNum][0] = targetRow;

queens[queenNum][1] = targetCol;

}

}

}

System.out.printf("queen %d has been placed in [%d][%d]\n", queenNum + 1, queens[queenNum][0], queens[queenNum][1]);

eliminate(queens[queenNum][0], queens[queenNum][1]);

decreaseElimination();

countEliminated();

}

// display board

public void displayBoard () {

for (int row = 0; row < board.length; row++) {

for (int col = 0; col < board[row].length; col++) {

System.out.printf("|%2d|", board[row][col]); // display elimination number of each square

}

System.out.println();

}

}// end displayBoard

}

my main method is in a separate class.

by (57.5k points)

This piece of code is inherently flawed:

code is: for (int queen = 0; queen < queens.length; queen++) {

placeQueens(queen);

}

You can't decide where to put queen 0 without deciding where to put queen 1 to 8 at the same time. You've implemented "First Fit":

And First Fit does not appear in a feasible solution as you can see in the example above. More info in this manual (including algorithms that do work) are as follows:

https://docs.jboss.org/drools/release/5.5.0.Beta1/drools-planner-docs/html_single/index.html#d0e5858