Formulate an admissible and accurate heuristic function for the 4-Queens problem
ID: 641441 • Letter: F
Question
Formulate an admissible and accurate heuristic function for the 4-Queens problem. You must discuss and demonstrate the admissibility and describe the degree of accuracy (in approximate terms) of your heuristic function. Define any other aspect of the problem formulation such as how a state should be represented for application of a heuristic search algorithm like the A*. In the "Four-Queens Puzzle", we try to place four queens on a 4x4 chess board so that none can capture any other. (That is, only one queen can be on any row, column, or diagonal of the array.) Suppose we try to solve this puzzle using the following problem space: The start node is labeled by an empty 4x4 array; the successor function creates new 4x4 arrays containing one additional legal placement of a queen anywhere in the array; the goal predicate is satisfied if and only if there are four queens in the array (legally positioned).
Explanation / Answer
// width of board
static final int SQUARES = 4;
// board
static boolean[][] board = new boolean[SQUARES][SQUARES];
// represents values for number of squares eliminated if queen is placed in square
static int[][] elimination = new int[SQUARES][SQUARES];
// store position of queens
static boolean[][] position = new boolean[SQUARES][SQUARES];
// store row
static int[] row = new int[4];
// store column
static int[] column = new int[4];
// Write a program to solve the Eight Queens problem
public static void main(String[] args)
{
Arrays.fill(row, -1);
Arrays.fill(column, -1);
// eliminate squares if a custom starting point is set
elimSquares();
// set elimination table
fillElim();
// count queens on board
// if first quuen is entered, counter must be 1
short counter = 0;
// while board is not full
while(counter < 8) {
// place next queen on board
placeQueen(-1, -1);
// reset elimination table
fillElim();
// backtrack and fill board back to this point
while(isFull() && counter < 7)
backtrack(counter);
counter++;
} // end while
// print starting square and board
System.out.println(row[0] + "/" + column[0]);
printBoard();
} // end method main
// Print board
public static void printBoard()
{
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board.length; j++) {
if(board[i][j] && position[i][j])
System.out.print("o ");
else if(board[i][j])
System.out.print("x ");
else
System.out.print("% ");
} // end inner for
System.out.println();
} // end outer for
} // end method printBoard
// Write method to calculate how many squares are eliminated if queen is placed in that square
public static void fillElim()
{
// if any squares that could be eliminated already are eliminated, subtract 1
for(int i = 0; i < elimination.length; i++) {
for(int j = 0; j < elimination[i].length; j++) {
elimination[i][j] = openSquares(i, j);
} // end inner for
} // end outer for
} // end method fillElimination
// Number of squares eliminatable by placing queen in any given square
public static int openSquares(int row, int column)
{
// if square is already eliminated, it cannot be used
if(board[row][column])
return 0;
// total number of squares elimintable from any given square, count square itself
int total = 1 + openHorizontal(row) + openVertical(column) + openUpSlope(row, column) + openDownSlope(row, column);
return total;
} // end method openSquares
// Return number of open squares in a row
public static int openHorizontal(int row)
{
// total of row
int total = 0;
for(boolean b : board[row]) {
// if square is "true" (open), increment total open squares
if(!b)
total++;
} // end for
// return total not counting current square
return total - 1;
} // end method openHorizontal
// Return number of open squares in a column
public static int openVertical(int column)
{
// total of column
int total = 0;
// if square is "true" (open), increment total open squares
for(boolean[] b : board) {
// if square is "true" (open), increment total open square
if(!b[column])
total++;
} // end for
// return total not counting current square
return total - 1;
} // end method openVertical
// Return number of open squares in a column
public static int openDownSlope(int x, int y)
{
// total of downward-sloping diagonal
int total = 0;
// if square is "true" (open), increment total open squares
for(int i = 0; i < board.length; i++) {
// test all values before use to prevent array index errors
// all squares to the top right of the checking square
if(x+i >= 0 && x+i < board.length && y+i >= 0 && y+i < board.length) {
// else increment total
if(!board[x+i][y+i])
total++;
} // end if
// all squares to the bottom left of the checking square
if(x-i >= 0 && x-i < board.length && y-i >= 0 && y-i < board.length) {
// else increment total
if(!board[x-i][y-i])
total++;
} // end if
} // end for
// return total not counting current square
return total - 2;
} // end method openDownSlope
// Return number of open squares in a column
public static int openUpSlope(int x, int y)
{
// total of upward-sloping diagonal
int total = 0;
// if square is "true" (open), increment total open squares
for(int i = 0; i < board.length; i++) {
// test all values before use to prevent array index errors
// all squares to the top right of the checking square
if(x+i >= 0 && x+i < board.length && y-i >= 0 && y-i < board.length) {
// else increment total
if(!board[x+i][y-i])
total++;
} // end if
// all squares to the bottom left of the checking square
if(x-i >= 0 && x-i < board.length && y+i >= 0 && y+i < board.length) {
// else increment total
if(!board[x-i][y+i])
total++;
} // end if
} // end for
// return total not counting current square
return total - 2;
} // end method openUpSlope
// Are all squares on the board filled?
public static boolean isFull()
{
// check all squares
for(boolean b[] : board) {
for(boolean bb : b) {
// if encounter open square
if(!bb)
return false;
} // end inner for
} // end outer for
// if this point is reached, board is full
return true;
} // end method isFull
// Place a queen on the board
public static void placeQueen(int lastRow, int lastCol)
{
// get next move
int[] bestSquare = bestMove(lastRow, lastCol);
// mark queen's position
position[bestSquare[0]][bestSquare[1]] = true;
// mark blocked squares as dead
elimSquares();
// store squares
for(int i = 0; i < row.length; i++) {
if(row[i] == -1) {
row[i] = bestSquare[0];
column[i] = bestSquare[1];
break;
} // end if
} // end for
} // end method placeQueen
// Return lowest number in elimination table
public static int[] bestMove(int lastRow, int lastCol)
{
// store coordinates
int[] move = {-1, -1};
// if lastRow is not -1, search for duplicate numbers after current square
if(lastRow != -1)
move = dupElimNums(lastRow, lastCol);
// if not received a value from dupElimNums, return value
if(move[0] == -1)
move = checkBoard(lastRow, lastCol);
return move;
} // end method bestMove
// Check for ties for elimination numbers, return first found after current position
public static int[] dupElimNums(int lastRow, int lastCol)
{
// store limit of use
int limit;
// set limit
if(lastRow == -1)
limit = -1;
else
limit = elimination[lastRow][lastCol];
// store move coordinates
int[] move = {-1, -1};
// get next square, accounting for end-of-row situations
int[] nextSquare = nextSquare(lastRow, lastCol);
// test for equal elimination numbers farther down on board
for(int i = nextSquare[0]; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
// start at 1 square after first position, then loop through rest of squares
if(i >= lastRow && j == 0)
j = nextSquare[1];
if(!board[i][j] && elimination[i][j] == limit) {
move[0] = i;
move[1] = j;
return move;
} // end if
} // end inner for
} // end outer for
return move;
} // end method dupElimNums
// Return next column, accounting for end-of-column/next-row situations
public static int[] nextSquare(int row, int column)
{
// num is not end of row
if(column < 3)
column++;
// num is end of row - go to next row
else {
column = 0;
row++;
}
// create array with coordinates
int[] square = {row, column};
// return array
return square;
} // end method nextSquare
// Check entire board for usable numbers
public static int[] checkBoard(int lastRow, int lastCol)
{
// store lowest number - set to impossibly low
int low = 100;
// store move coordinates
int[] move = {-1, -1};
// store limit of use
int limit;
// set limit
if(lastRow == -1)
limit = -1;
else
limit = elimination[lastRow][lastCol];
// test for any available squares left on board
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
if(!board[i][j] && elimination[i][j] > limit && elimination[i][j] < low)
low = elimination[i][j];
} // end inner for
} // end outer for
// get move coordinates for square, if needed to get best square after two backtracks
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
// return after executing so we return the first square available
if(!board[i][j] && elimination[i][j] == low) {
move[0] = i;
move[1] = j;
return move;
} // end if
} // end inner for
} // end outer for
return move;
} // end method checkBoard
// Eliminate dead squares
public static void elimSquares()
{
// reset board
resetBoard();
// eliminate dead squares
for(int r = 0; r < position.length; r++) {
for(int c = 0; c < position[r].length; c++) {
// if square is used, eliminate all squares vertically, horizontally, and diagonally
if(position[r][c]) {
elimHorizontal(r);
elimVertical(c);
elimUpSlope(r, c);
elimDownSlope(r, c);
} // end if
} // end inner for
} // end outer for
// reset elimination table
fillElim();
} // end method elimSquares
// Eliminate row
public static void elimHorizontal(int row)
{
// eliminate row
for (int i = 0; i < board[row].length; i++)
board[row][i] = true;
} // end method elimHorizontal
// Eliminate column
public static void elimVertical(int column)
{
// eliminate column
for(boolean[] b : board)
b[column] = true;
} // end method elimVertical
// Eliminate downward slope
public static void elimDownSlope(int x, int y)
{
// loop through downward slope
for(int i = 0; i < board.length; i++) {
// test all values before use to prevent array index errors
// eliminate all squares to the bottom right of the checking square
if(x+i >= 0 && x+i < board.length && y+i >= 0 && y+i < board.length)
board[x+i][y+i] = true;
// eliminate all squares to the top left of the checking square
if(x-i >= 0 && x-i < board.length && y-i >= 0 && y-i < board.length)
board[x-i][y-i] = true;
} // end for
} // end method elimDownSlope
// Eliminate upward slope
public static void elimUpSlope(int x, int y)
{
// loop through upward slope
for(int i = 0; i < board.length; i++) {
// test all values before use to prevent array index errors
// eliminate all squares to the bottom right of the checking square
if(x+i >= 0 && x+i < board.length && y-i >= 0 && y-i < board.length)
board[x+i][y-i] = true;
// eliminate all squares to the top left of the checking square
if(x-i >= 0 && x-i < board.length && y+i >= 0 && y+i < board.length)
board[x-i][y+i] = true;
} // end for
} // end method elimUpSlope
// If not found solution and board is full
public static void backtrack(int lastMove)
{
// store last move
int lastRow = row[lastMove];
int lastCol = column[lastMove];
// clear positions
resetPositions();
// go back 1 move
goBack(lastMove);
// refill board up to, not including, last point
for(int i = 0; i < row.length; i++) {
// escape if out of bounds
if(row[i] == -1)
break;
// enter position
position[row[i]][column[i]] = true;
// fill elimination table
elimSquares();
} // end for
// while no open squares, go back one more row
while(!openSpaces(lastRow, lastCol)) {
backtrack(lastMove-1);
// reset numbers if go back a move so we come down without useless restrictions
if(openSpaces(lastRow, lastCol)) {
lastRow = -1;
lastCol = -1;
// exit loop so we do not check for open spaces with -1 and -1
break;
} // end if
} // end while
// set queen in square
placeQueen(lastRow, lastCol);
} // end method backtrack
// Clear board
public static void resetBoard()
{
// clear board
for(boolean[] b : board)
for(int i = 0; i < b.length; i++)
b[i] = false;
} // end method resetBoard
// Clear positions
public static void resetPositions()
{
// clear positions
for(boolean[] b : position)
for(int i = 0; i < b.length; i++)
b[i] = false;
} // end method resetPositions
// Go back 1 move
public static void goBack(int lastMove)
{
// remove last move from table
row[lastMove] = -1;
column[lastMove] = -1;
} // end method goBack
// Return number of open, untested spaces on board
public static boolean openSpaces(int lastRow, int lastCol)
{
// store limit of use
int limit = elimination[lastRow][lastCol];
// test for any available squares left on board
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
if(!board[i][j] && elimination[i][j] > limit)
return true;
} // end inner for
} // end outer for
return false;
} // end method openSpaces