import java.io.*;
import java.text.*;
import java.util.*;
public class EightPuzzle{
//puzzle holds current state of puzzle, and goal holds goal state
private char [][] puzzle = new char [3][3];
private char [][] goal = new char [3][3];
//moves that can be made for current puzzle state
private ArrayList<Character> moves;
//frontier for A* search, static so it doesn't need to be allocated for
//each object, and is a member because it is used in multiple methods
private static Tree <EightPuzzle> frontier = new Tree<EightPuzzle>();
private static final int STEPCOST = 1;//cost to make a move
//used to keep track of heuristic being used
private String heuristicID = new String();
//heuristic value for EightPuzzle to goal, calculated by h1 or h2
private int heuristic;
/* constructor for an EightPuzzle takes a file and saves it in a string and
* initializes both goal and puzzle arrays in initialize function. Also gets
* the possible moves for the current state of the EightPuzzle and
* initializes the frontier for A* search to this object just created.
* This is used to construct the initial state of the puzzle.
*/
public EightPuzzle(File in, String heuristicID)
{
moves = new ArrayList<Character>();
String str = buildPuzzle(in);
this.initialize(str);
this.getPossibleMoves();
frontier = new Tree<EightPuzzle>(this);
this.heuristicID = heuristicID;
if(heuristicID.equals("h1"))
this.heuristic = heuristic1(this.puzzle);
else if(heuristicID.equals("h2"))
this.heuristic = heuristic2(this.puzzle);
else this.heuristic = heuristic1(this.puzzle);//default
}
/* constructs an EightPuzzle from the array passed in. Sets the puzzle value
* to state and gets the possible moves for that state.
*/
public EightPuzzle(char[][] state,String heuristicID)
{
moves = new ArrayList<Character>();
this.puzzle = state;
this.getPossibleMoves();
this.heuristicID = heuristicID;
if(heuristicID.equals("h1"))
this.heuristic = new Integer(heuristic1(this.puzzle));
else if(heuristicID.equals("h2"))
this.heuristic = new Integer(heuristic2(this.puzzle));
else this.heuristic = new Integer(heuristic1(this.puzzle));//default
}
/* copy constructor, makes a deep copy of p.
*/
public EightPuzzle(EightPuzzle p)
{
for(int i = 0; i < 3; i++)//deep copy puzzle
for(int j = 0; j < 3; j++)
{
this.puzzle[i][j] = new Character(p.puzzle[i][j]);
}
this.moves = new ArrayList<Character>();
final int SIZE = p.getMoves().size();
for(int i =0; i < SIZE;i++)//deep copy moves
this.moves.add(new Character(p.moves.get(i)));
//point to same goal in memory, doesn't need deep copy
this.goal = p.getGoal();
if(p.heuristicID.equals("h1"))
this.heuristic = new Integer(heuristic1(this.puzzle));
else if(p.heuristicID.equals("h2"))
this.heuristic = new Integer(heuristic2(this.puzzle));
else this.heuristic = new Integer(heuristic1(this.puzzle));//default
}
//accessor method for puzzle member
public char [][] getPuzzle()
{
return this.puzzle;
}
//accessor method for heuristic
public int getHeuristic()
{
return this.heuristic;
}
//accessor method for goal member
public char [][] getGoal()
{
return this.goal;
}
//accessor method for frontier member
public Tree<EightPuzzle> getFrontier()
{
return frontier;
}
//accessor method for moves member
public ArrayList<Character> getMoves()
{
return this.moves;
}
//entry point
public static void main(String [] args)
{
//EightPuzzle for h1
EightPuzzle p1 = new EightPuzzle(new File("in.txt"),"h1");
//solve puzzle with heuristic 1 and save it in pathH1
ArrayList<EightPuzzle> pathH1 = p1.solvePuzzle();
System.out.println("Solving with heuristic h1: \n");
final int SIZEH1 = pathH1.size();
for(int i = 0; i < SIZEH1;i++)//print pathH1
{
System.out.println("Step " + i + ":");
System.out.println(pathH1.get(i));
}
//EightPuzzle for h2
EightPuzzle p2 = new EightPuzzle(new File("in.txt"),"h2");
//solve puzzle with heuristic 2 and save it in pathH2
ArrayList<EightPuzzle> pathH2 = p2.solvePuzzle();
System.out.println("\nSolving with heurstic h2: \n");
final int SIZEH2 = pathH2.size();
for(int i = 0; i < SIZEH2; i++)//print pathH2
{
System.out.println("Step "+ i + ":");
System.out.println(pathH2.get(i));
}
//write the results to out.txt
EightPuzzle.writeResultsToFile("out.txt", pathH1,pathH2);
}
/* Writes the results for heuristics 1 and 2 to a textfile specified by the
* string file.
*/
public static void writeResultsToFile(String file,
ArrayList<EightPuzzle> pathH1,ArrayList<EightPuzzle> pathH2)
{
try
{
BufferedWriter out = new BufferedWriter(new FileWriter(file));
final int SIZEH1 = pathH1.size();
final int SIZEH2 = pathH2.size();
out.write("Solving with heuristic h1: \n\n");
for(int i = 0;i < SIZEH1;i++)//write h1 results to file
{
out.write("Step " + i + ":\n");
out.write(pathH1.get(i) + "\n");
}
out.write("\nSolving with heuristic h2: \n\n");
for(int i = 0;i < SIZEH2;i++)//write h2 results to file
{
out.write("Step " + i + ":\n");
out.write(pathH2.get(i) + "\n");
}
out.close();//closed the buffer
}catch(IOException E)
{
E.printStackTrace();
}
}
/*returns a string representation of the puzzle's initial state and goal
state from a textfile.
*/
public String buildPuzzle(File in)
{
//for building a string to ouput all at once
StringBuilder sb = new StringBuilder();
try//buffered reader reads one line at a time
{
BufferedReader reader = new BufferedReader(new FileReader(in));
try
{
String line = null;
while((line = reader.readLine()) != null)
{
sb.append(line);
sb.append(System.getProperty("line.separator"));
}
}
finally{reader.close();}//close input stream
}
catch(IOException E)//if file not found
{
E.printStackTrace();
}
return sb.toString();
}
/*
* Initializes the char 2-d array puzzle and goal. The string "puzzles"
* contains the initial state, which is initialized to puzzle array, and
* the goal state is separated by a blank line and is initialized to the
* goal array
*/
public void initialize(String puzzles)
{
CharacterIterator iter = new StringCharacterIterator(puzzles);
int row = 0;//row index for puzzle and goal
int column = 0;//column index for puzzle and goal
char c;
//stop iterating when row and column is equal to 3 so we can assign goal
//after done with puzzle assignment
for(c = iter.first();(row!=3&& column !=3);c=iter.next())
{
//if c is a digit or 'B', save it in puzzle
if(Character.isDigit(c) || c == 'B')
{
this.puzzle[row][column] = c;
if(column<2)
column++;
else
{
row++; column = 0;//reset column, new line
}
}
}
row=column=0;//reset row and column to zero
for(c = iter.next();(row!=3&&column!=3);c=iter.next())
{
//if c is a digit or 'B', save it in goal
if(Character.isDigit(c) || c == 'B')
{
this.goal[row][column] = c;
if(column < 2)
column++;
else
{
row++; column = 0;//reset column, new line
}
}
}
}
/* Find the possible moves for the current state of the puzzle, finds the
* row and column indices of 'B' in the EightPuzzle and adds the
* elements at compatible positions that can be swapped with 'B' to the
* moves member.
*/
public void getPossibleMoves()
{
//row and column index of 'B' in puzzle
int row=0;
int column=0;
//find index of 'B' in
for(int i = 0; i < 3;i++)
for(int j = 0; j < 3; j++)
{
if(puzzle[i][j] == 'B')
{
row = i; column = j; break;//break out of loop, found 'B'
}
}
//if 'B' is at [0][0], these are the two characters(digits) that it
//can be switched with
if(row == 0 && column == 0)
{
moves.add(puzzle[1][0]);
moves.add(puzzle[0][1]);
}
else if(row == 0 && column == 1)
{
moves.add(puzzle[0][0]);
moves.add(puzzle[0][2]);
moves.add(puzzle[1][1]);
}
else if(row == 0 && column == 2)
{
moves.add(puzzle[0][1]);
moves.add(puzzle[1][2]);
}
else if(row == 1 && column == 0)
{
moves.add(puzzle[0][0]);
moves.add(puzzle[1][1]);
moves.add(puzzle[2][0]);
}
else if(row == 1 && column == 1)
{
moves.add(puzzle[1][0]);
moves.add(puzzle[0][1]);
moves.add(puzzle[1][2]);
moves.add(puzzle[2][1]);
}
else if(row == 1 && column == 2)
{
moves.add(puzzle[1][1]);
moves.add(puzzle[0][2]);
moves.add(puzzle[2][2]);
}
else if(row == 2 && column == 0)
{
moves.add(puzzle[1][0]);
moves.add(puzzle[2][1]);
}
else if(row == 2 && column == 1)
{
moves.add(puzzle[2][0]);
moves.add(puzzle[1][1]);
moves.add(puzzle[2][2]);
}
else if(row == 2 && column == 2)
{
moves.add(puzzle[2][1]);
moves.add(puzzle[1][2]);
}
}
//returns string representation of the puzzle
@Override
public String toString()
{
//use to append each object before returning string
StringBuilder sb = new StringBuilder();
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
{
sb.append(puzzle[i][j]);
if(j==2)sb.append("\n");//end of line add a newline character
}
return sb.toString();
}
/* heursitic1() defines the heursitic for the 8 puzzle. It returns how many
* misplaced characters are in the 8 puzzle.
*/
public int heuristic1(char[][] state)
{
int count = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
{
if(state[i][j] != goal[i][j])//if the character is misplaced
count++;
}
return count;
}
/*Returns the sum of the manhattan distance of each misplaced character.
*///have not checked if this works
public int heuristic2(char [][] state)
{
//sum will be sum of manhattan distances of all misplaced elements
int sum = 0;
for(int i = 0; i < 3; i++)//for loops to find a misplaced element
for(int j = 0; j < 3; j++)
{
if(state[i][j]!=goal[i][j])
{
//for loops for manhattan distance computation
for(int m = 0; m < 3; m++)
for(int n = 0; n < 3; n++)
{
if(state[i][j] == goal[m][n])
{
sum += (Math.abs((m-i))
+Math.abs((n-j)));
}
}
}
}
return sum;
}
/* swaps the 'B' element of the EightPuzzle with c if c is in range '1'-'8'.
* finds the row and column indice's of 'B' and c in the puzzle and swaps
* the two.
*/
private EightPuzzle swap(char c)
{
EightPuzzle p = new EightPuzzle(this);
//check if in range
if((Character.digit(c, 10) > 0) && (Character.digit(c,10) <9))
{
//x is location of row of c, y is column of c, m is row of 'B',
//and n is column of 'B'
int x,y,m,n;
x = y = m = n = 0;
for(int i = 0; i < 3; i++)//find 'B' and c
for(int j = 0; j < 3; j++)
{
if(p.getPuzzle()[i][j] == 'B')
{
m = i; n = j;
}
if(p.getPuzzle()[i][j] == c)
{
x = i; y = j;
}
}
//found positions of 'B' and c, so now we swap
p.puzzle[m][n] = c;
p.puzzle[x][y] = 'B';
}
else System.out.println("Illegal move, \'" + c +"\' is out of range!");
return p;
}
/* Check if the current state is the goal state.
* Checks each element to see if it matches goal[row][column]
* if one element does not match, it returns false immediately,
* if all match it returns true.
*/
public boolean goalCheck()
{
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
{
if(puzzle[i][j] != goal[i][j])
return false;
}
return true;
}
/* solvePuzzle(String heuristic), solves the EightPuzzle using the A*
* search algorithm with the heuristic denoted by the string passed in.
* open is an ArrayList for the nodes that haven't been examined. closed
* is an ArrayList for the nodes that have been examined. path holds all of
* the nodes stored in order, so the path can be returned as the solution
* to the EightPuzzle. the initial state is added to the open list. while
* open isn't empty, items are dequeued from the sorted open list. open is
* sorted by increasing heursitic values, and sorted by the method defined
* by the heuristic passed in. The node examined is added to path, it is
* tested to see if it is the goal state, if so path is returned. Otherwise,
* The examined node is added to the closed list, the neighbor nodes are
* added to the frontier with getNeighborNodes(). gcost is updated because
* we are at a new level in the frontier. this is updated with
* node.getData().puzzle and node.getData().moves so the program will not
* use the moves and puzzle from the initial state. if the child node is in
* the open or closed list with a greater cost than gcost, the cost is
* updated in open or closed list. If the child is not in either list, it
* is added to the open list and the while loop continues until we find a
* solution or the open list runs out.
*/
public ArrayList<EightPuzzle> solvePuzzle()
{
//Nodes that haven't been examined yet
ArrayList<Node<EightPuzzle>> open = new ArrayList<Node<EightPuzzle>>();
//Nodes that have been examined
ArrayList<Node<EightPuzzle>> closed = new ArrayList
<Node<EightPuzzle>>();
//Nodes that have been explored, will contain path to goal
ArrayList<EightPuzzle> path = new ArrayList<EightPuzzle>();
//keep track of how far down tree we are for comparing gcost's of nodes
int gcost = 0;
//add the root node to the open ArrayList
open.add(frontier.getRoot());
while(!open.isEmpty())
{
//sort by best(lowest cost) e(n) = g(n)+h(n)
open = sort(open);
Node<EightPuzzle> node = new Node<EightPuzzle>
(new EightPuzzle(open.get(0).getData()));
//this level is STEPCOST + node's gcost
//gcost = STEPCOST + node.getgcost();
this.puzzle = node.getData().puzzle;//update this
this.moves = node.getData().getMoves();//update this
open.remove(0);
path.add(node.getData());//keep track of nodes visited in order
closed.add(node);//node has been visited
//check if we are at the goal
if(node.getData().goalCheck())
return path;
else
{
node.getData().getNeighborNodes(node,open,closed);
//this level is STEPCOST + node's gcost
//gcost = STEPCOST + node.getgcost();
final int SIZE = node.getNeighbors().size();
for(int i = 0; i < SIZE;i++)
{
//if node in the open list with greater cost, update it
//with the lower cost
inListWithGreaterCost(open,node.getNeighbors().get(i));
//if it is in neither list, add it to open
//if node in the closed list with greater cost, update it
//with the lower cost
inListWithGreaterCost(closed,node.getNeighbors().get(i));
if(!in(open,node.getNeighbors().get(i)) &&
!in(closed, node.getNeighbors().get(i)))
open.add(node.getNeighbors().get(i));
}
}
}
return path;
}
/* in() checks if node is in the ArrayList list. Each individual Node in the
* list is checked by counting how many elements are the same as node for
* that node in the list. If the count is 9, which means all elements are
* the same, in returns true, otherwise we keep going until count = 9 or
* the list runs out and in returns false when the list runs out because no
* match
*/
private boolean in(ArrayList<Node <EightPuzzle>> list, Node<EightPuzzle> node)
{
int count = 0;
final int SIZE = list.size();
for(int i = 0; i < SIZE;i++)
{//check if this element of list is equal to node
for(int j = 0; j < 3; j++)
for(int k = 0; k < 3; k++)
if(list.get(i).getData().puzzle[j][k] ==
node.getData().puzzle[j][k])
count++;
if(count == 9)//the node is in list
return true;
}//if not in list
return false;
}
/* inListWithGreaterCost() starts out like in() by checking to see if it
* is in list. If it is in the list the index is saved and the node at that
* index's gcost is compared to the gcost passed in. If it is less than the
* one passed in it is updated with that value and it's parent is updated
* and is added to the frontier with node as the parent.
*/
private void inListWithGreaterCost(ArrayList <Node<EightPuzzle>> list
, Node<EightPuzzle> node)
{
int index = -1;//will be index of node in list after it is found
final int SIZE = list.size();
for(int i = 0;i < SIZE;i++)
{//check if this member is in the list first, just like in
int count = 0;
for(int j = 0 ; j < 3; j++)
for(int k = 0; k < 3; k++)
{
if(list.get(i).getData().puzzle[j][k] ==
node.getData().puzzle[j][k])
count++;
}
if(count == 9)
{//only difference between in and first part of this function
index = i;
break;
}
}
if(index == -1)//not found in list
return;
//if gcost passed in is better than the gcost in the found node
//update the gcost of the node in the list with gcost
else if(node.getgcost() > list.get(index).getgcost())
{
//remove node from current parent
node.setgcost(list.get(index).getgcost());
list.set(index,node);
//list.remove(index);
//list.get(index).getParent().getNeighbors().remove(list.get(index));
//list.get(index).setgcost(gcost);//update gcost of node
//list.get(index).setParent(node.getParent());//change the parent to node
//append list.get(index) to frontier
//frontier.append(node.getParent(),list.get(index));
}
return;
}
/* sort() sorts list in order of increasing e(n). e(n) = h(n) + g(n).
* sort's behavior depends on the heuristic string, if "h1", heuristic1()
* is used to sort the list. If "h2", heuristic2() is used to sort the list.
* This is a bubblesort method.
*/
public ArrayList<Node<EightPuzzle>> sort(ArrayList<Node<EightPuzzle>> list)
{
boolean swapped = false;
do
{
swapped = false;
final int SIZE = list.size();
for(int i = 0; i < SIZE-1;i++)
{//if(e(ni) > e(ni+1) swap them
if((list.get(i).getData().getHeuristic()
+ list.get(i).getgcost())
> (list.get(i+1).getData().getHeuristic() +
list.get(i+1).getgcost()))
{
//swap the two members that are out of place
Node<EightPuzzle> temp = new Node<EightPuzzle>
(new EightPuzzle(list.get(i).getData()));
list.set(i, list.get(i+1));
list.set(i+1,temp);//.setData(new EightPuzzle(temp));
swapped = true;
}//else if it is equal, deepest node wins
else if((list.get(i).getData().getHeuristic()
+ list.get(i).getgcost())
== (list.get(i+1).getData().getHeuristic() +
list.get(i+1).getgcost()))
{
if(list.get(i).getgcost() < list.get(i+1).getgcost())
{
//swap the two members that are out of place
Node<EightPuzzle> temp = new Node<EightPuzzle>
(new EightPuzzle(list.get(i).getData()));
list.set(i, list.get(i+1));
//list.get(i).setData(new EightPuzzle
//(list.get(i+1).getData()));
list.set(i+1,temp);//.setData(new EightPuzzle(temp));
swapped = true;
}
}
}
}while(swapped);
return list;
}
/* getNeighborNodes() adds the neighbor nodes of node to the frontier(tree).
* It is done by traversing the moves element of the EightPuzzle contained
* in node and creating a new EightPuzzle by swapping the blank with the
* character corresponding to the index in moves.
*/
private void getNeighborNodes(Node<EightPuzzle> node,
ArrayList<Node<EightPuzzle>> open, ArrayList<Node<EightPuzzle>>
closed)
{
final int SIZE = node.getData().getMoves().size();
for(int i = 0; i < SIZE;i++)//traverse node.getData().getMoves
{
//make a new EightPuzzle by swapping the blank('B') with
//the corresponding character in the moves ArrayList inside the
//node's EightPuzzle member.
EightPuzzle p = new EightPuzzle
(swap(node.getData().getMoves().get(i)));
//Make a node for the new EightPuzzle
Node <EightPuzzle> child = new Node<EightPuzzle>(p);
//clear moves because the moves from node's EightPuzzle are copied
//to the new EightPuzzle
child.getData().moves.clear();
child.getData().getPossibleMoves();//get the available moves
if(!in(open,child) && !in(closed,child)){
child.setgcost(STEPCOST + node.getgcost());//set it's gcost
frontier.append(node, child);//add to the frontier
}
}
}
}
import java.util.*;
public class Node <E>{
private ArrayList<Node> neighborNodes;//children of this node
private E data;//data inside node
private Node<E> parent;//parent of this
/*gcost is the cost to get to the current level in the tree,
must be assigned it's "real value" as tree is constructed*/
private int gcost = 0;
/*assign Node's data value with value passed in constructor
we don't set gcost, it could be 1 + parent.gcost, but for root, this would
not work*/
public Node(E data)
{
neighborNodes = new ArrayList<Node>();
this.data=data;
}
/*No data assignment, allocates memory for neighborNodes ArrayList*/
public Node()
{
neighborNodes = new ArrayList<Node>();
}
//accessor method for neighborNodes ArrayList.
public List<Node> getNeighbors()
{
return this.neighborNodes;
}
//accessor method for gcost
public int getgcost()
{
return gcost;
}
//method for setting gcost member
public void setgcost(int n)
{
gcost = n;
}
/*adds n to the neighborNodes ArrayList and sets n's parent to this.*/
public void append(Node<E> n)
{
n.parent = this;
neighborNodes.add(n);
}
/*Accessor method for the data member*/
public E getData()
{
return data;
}
/*method for setting the data for the Node*/
public void setData(E data)
{
this.data = data;
}
//accessor method for the parent member
public Node<E> getParent()
{
return this.parent;
}
//changes the parent of the current node
public void setParent(Node<E> parent)
{
//check if it has a parent, if so remove it from the parents'
//neighborNodes ArrayList
if(this.parent != null)
parent.neighborNodes.remove(this);
this.parent = parent;
//add this to make it available in the parents neighborNode ArrayList
parent.neighborNodes.add(this);
}
}
import java.util.*;
public class Tree <E>
{
private Node<E> root;
//constructor: assigns root with data
public Tree(E data)
{
root=new Node(data);
}
public Tree(){}//empty constructor, no data assignment
//accessor method to return the root of the Tree
public Node<E> getRoot()
{
return root;
}
/* Finds the parent by comparing the toString() value of parent and
* the current Node in the frontier and making sure it is the same Node by
* comparing the gcost of the parent to the node. If it is, the child is
* appended to the parent. The search used is Breadth first search
*/
public void append(Node<E> parent, Node <E> child)
{
//Node<E> temp = root;
ArrayList<Node<E>> frontier = new ArrayList<Node<E>>();
frontier.add(root);
while(!frontier.isEmpty())
{
Node<E> N = frontier.get(0);//get a Node
frontier.remove(0);
if(N.getData().toString().equals(parent.getData().toString()) &&
N.getgcost() == parent.getgcost())//is this the parent?
{
parent.append(child);//if yes add child
break;//no more work to be done!
}
final int SIZE = N.getNeighbors().size();
for(int i = 0; i < SIZE;i++)//get neigbors
frontier.add(N.getNeighbors().get(i));
}
}
}
LinkBack URL
About LinkBacks
need help figuring out what is wrong with my A* search algorithm for an 8 puzzle
Reply With Quote
Related threads: