To implement A* Algorithm to solve the following problems (i.e. find the goal):

Question

To implement A* Algorithm to solve the following problems (i.e. find the goal): to select either 1) N-Queen or 2) 8-puzzle. Plus, one problem of your choice. 1) N-Queen (N should be greater than or equal to 8): 2) 8 Puzzle Problem: The 8 puzzle consists of eight numbered, movable tiles set in a 3x3 frame. One cell of the frame is always empty thus making it possible to move an adjacent numbered tile into the empty cell. Such a puzzle is illustrated in following diagram.

The program is to change the initial configuration into the goal configuration. A solution to the problem is an appropriate sequence of moves, such as “move tiles 5 to the right, move tile 7 to the left, move tile 6 to the down, etc”.

need help understanding the proper code for this problem

Explanation / Answer

* Board.java

import java.util.Arrays;

import java.lang.System;

public class Board {
//public Board(int[][] blocks) construct a board from an N-by-N array of blocks
// (where blocks[i][j] = block in row i, column j)
//public int dimension() board dimension N
//public int hamming() number of blocks out of place
//public int manhattan() sum of Manhattan distances between blocks and goal
//public boolean isGoal() is this board the goal board?
//public Board twin() a board obtained by exchanging two adjacent blocks in the same row
//public boolean equals(Object y) does this board equal y?
//public Iterable<Board> neighbors() all neighboring boards
//public String toString() string representation of the board (in the output format specified below)
  
private final int[][] tiles;
private int size;
private int zeroCol;
private int zeroRow;
private int hamming;
private int manhattan;

public Board(int[][] blocks){
size = blocks.length;
tiles =new int[size][size];
for(int i = 0; i <size; i++){
for(int j = 0; j<size; j++){
this.tiles[i][j] = blocks[i][j];
if(tiles[i][j] == 0)
setZero(i,j);
}
}
}
  
private void setZero(int i, int j){
this.zeroRow = i;
this.zeroCol = j;
}
  
public int dimension(){
return size;
}
  
public String toString() {
int N = size;
StringBuilder s = new StringBuilder();
s.append(N + " ");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
s.append(String.format("%2d ", tiles[i][j]));
}
s.append(" ");
}
return s.toString();
}
  
public int manhattan(){
int arrayPosition;
int tile;
manhattan = 0;
for(int i = 0; i <size; i++){
for(int j = 0; j<size; j++){
tile = tiles[i][j];
if(tile == 0)
continue;
arrayPosition = 1+ j +(i*this.size);
  
if(arrayPosition-tile == 0)
continue;
double ii = Math.floor(((double)(tile-1))/this.size);
double jj = (tile-1)%this.size;
manhattan += (Math.abs(i-ii)+Math.abs(j-jj));
//StdOut.println("Tile:" + tile + " [MOVES:"+ (Math.abs(i-ii)+Math.abs(j-jj))+"] | Offsets: i "+ Math.abs(i-ii) + " j "+ Math.abs(j-jj));
}
}
return manhattan;
}

public int hamming(){
int arrayPosition;
int tile;
int displaced =0;
  
for(int i = 0; i <size; i++){
for(int j = 0; j<size; j++){
tile = tiles[i][j];
if(tile ==0)
continue;
arrayPosition = 1+ j +(i*this.size);
  
if(tile != arrayPosition)
displaced++;
else
continue;
}
}
return displaced;
}
  
public boolean isGoal(){
int arrayPosition;
int tile;

for(int i = 0; i <size; i++){
for(int j = 0; j<size; j++){
if(i==size-1 && j == size -1)
continue;
tile = tiles[i][j];
arrayPosition = 1+ j +(i*this.size);
if(tile != arrayPosition)
return false;
}
}
return true;
}
  
private int[][]deepCopy(int[][] array){
int[][] copy = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
copy[i][j] =array[i][j];
}
}
return copy;
}
  
public Board twin() {
int[][] twin = deepCopy(tiles);
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (tiles[i][j] != 0 && tiles[i][j + 1] != 0 && j < (size - 1)) {
int swap = twin[i][j];
twin[i][j] = twin[i][j + 1];
twin[i][j + 1] = swap;
return new Board(twin);
}
}
}
return new Board(twin);
}
  
public boolean equals(Object y){
Board that = (Board) y;
if (y == null) return false;
if (this == y) return true;
if (this.getClass() != y.getClass()) return false;
if (that.size != this.size) return false;
  
return Arrays.deepEquals(this.tiles, that.tiles );
}
  
public Iterable<Board> neighbors(){
Stack<Board> boards = new Stack<Board>();

if(zeroRow > 0){
Board boardUP = new Board(swap(tiles,-1,0));
boards.push(boardUP);
}
  
if(zeroRow < size-1){
Board boardDown = new Board(swap(tiles,1,0));
boards.push(boardDown);
}
  
if(zeroCol > 0){
Board boardLeft = new Board(swap(tiles,0,-1));
boards.push(boardLeft);
}
  
if(zeroCol <size-1){
Board boardRight = new Board(swap(tiles,0,1));
boards.push(boardRight);
}

return boards;
  
}
public int[][] swap(int[][] board, int rowOffset, int colOffset){
int[][] tempBoard = deepCopy(board);
tempBoard[zeroRow][zeroCol]= tiles[zeroRow+rowOffset][zeroCol+colOffset];
tempBoard[zeroRow+rowOffset][zeroCol+colOffset]=0;

return tempBoard;
}
}

* Solver.java
* Description: Solve the 8-puzzle using A* algorithm

public class Solver {

//public Solver(Board initial) // find a solution to the initial board (using the A* algorithm)
//public boolean isSolvable() // is the initial board solvable?
//public int moves() // min number of moves to solve initial board; -1 if no solution
//public Iterable<Board> solution() // sequence of boards in a shortest solution; null if no solution
//public static void main(String[] args) // solve a slider puzzle (given below)
// you will want to use comparator for hamming & man
//MinPq<node> pq as the priority queue

private Node goalNode;
private MinPQ<Node> pq = new MinPQ<Node>();
private MinPQ<Node> pqTwin = new MinPQ<Node>();
  
public class Node implements Comparable<Node>{
public Board board;
public Node previous;
public int moves;

public int compareTo(Node that){
//StdOut.println("i:" + this.priority() + " j:" + that.priority() + " "+ ((this.priority() > that.priority()) ? 1 : -1));
if(this.priority() == that.priority()) return 0;
return (this.priority() > that.priority()) ? 1 : -1;
}
  
public Node(Board b, Node prev, int m){
board = b;
previous = prev;
moves = m;
}
  
public int priority(){
return board.manhattan() + moves;
}
}
  
public Solver(Board initial){
Board initialBoard;
Queue<Board> neighbors = new Queue<Board>();
initialBoard = initial;

Node currentNode = new Node(initial, null, 0);
Node currentTwin = new Node(initial.twin(), null, 0);
pq.insert(currentNode);
pqTwin.insert(currentTwin);
  
while(!currentNode.board.isGoal() && !currentNode.board.isGoal()){

currentNode = pq.delMin();
currentTwin = pqTwin.delMin();

for(Board b : currentNode.board.neighbors()) {
if(!b.equals(currentNode.board))
pq.insert(new Node(b, currentNode, currentNode.moves +1));
}
  
for(Board b : currentTwin.board.neighbors()) {
if(!b.equals(currentNode.board))
pqTwin.insert(new Node(b, currentTwin, currentTwin.moves +1));
}
}
  
if(currentNode.board.isGoal())
goalNode = currentNode;
else
goalNode = currentTwin;
}
  
public Iterable<Board> solution(){
Queue<Board> trace = new Queue<Board>();
trace.enqueue(goalNode.board);
while (goalNode.previous != null){
goalNode = goalNode.previous;
trace.enqueue(goalNode.board);
}
  
return trace;
}
  
public boolean isSolvable(){
return goalNode != null;
}
  
public int moves(){
return goalNode.moves;
}
  
public static void main(String[] args) {
// create initial board from file
In in = new In(args[0]);
int N = in.readInt();
int[][] blocks = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
blocks[i][j] = in.readInt();
Board initial = new Board(blocks);
  
// solve the puzzle
Solver solver = new Solver(initial);
  
  
// print solution to standard output
if (!solver.isSolvable())
StdOut.println("No solution possible");
else {
StdOut.println("Minimum number of moves = " + solver.moves());
for (Board board : solver.solution())
StdOut.println(board);
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.