package puzzle;
import framework.*;
import java.util.*;
/**
This class is respnsible for representing the internal details of a bridge state, displaying bridge state to output, and checking for state equality.
*/
public class puzzleState implements State
{
/**
*private String array for tile numbers.
*/
private int [] tileNums;
/**
* Creates a new puzzle state
* @param tileNums is a string
*/
public puzzleState(int[] tileNumsIn)
{ tileNums = tileNumsIn;
}
/**
* This method displays the outputs.
*/
public void display()
{
}
/**
Tests for equality between this state and the argument state
Two states are equals if all the same people are on the same sides.
@param state the state to test against this state
@return wheather the states are equal
*/
public boolean equals(State state)
{
puzzleState aState = (puzzleState) state;
if (getArray() == aState.getArray())
return true;
else
return false;
}
public int[] getArray() {
return tileNums;
}
/**
*Accessor for array index of the blank position
*@return int blank
*/
public int getBlank() {
int[] copy = getArray();
int blank=-1;
int i=0;
while (i <= 8) {
if (copy == 0) { blank=i; }
i++;
}
return blank;
}
}
package puzzle;
import framework.*;
import java.util.*;
/**
This class is responsible for performing the legal moves that can be
done on states in the puzzle problem
*/
public class puzzleMove extends Move
{
/**
@param BLOCKUP moves the blank block up
@param BLOCKDOWN moves the blank block down
@param BLOCKRIGHT moves the blank block right
@param BLOCKLEFT moves the blank block left
*/
public static final String ML = "ml";
public static final String MD = "md";
public static final String MR = "mr";
public static final String MU = "mu";
public static final String randM = "rand";
private static final int SECOND = 1;
private static final int Zero = 0;
//private String moveName;
/**
Creates a puzzle Move.
@param moveName a user command
@precondition moveName must be one of the listed commands
*/
public puzzleMove(String moveName)
{ super(moveName);
}
/*
Accessor for puzzle Move name
@return the name of this move
public String getMoveName()
{ return moveName;
}*/
/**
* This method moves the zero up.
*/
public puzzleState moveUp(puzzleState stateIn)
{
int blankPos = stateIn.getBlank(); //locate zero with incoming state
if (blankPos == 0 || blankPos == 1 || blankPos == 2) {
//JOptionPane.showMessageDialog(null,"Invalid State");
return null;
}
else {
int[] temp = stateIn.getArray(); //get the array
int temp2 = temp[blankPos-3]; //store dest in temp
temp[blankPos-3]=Zero; //move blank into dest
temp[blankPos]=temp2; //move temp into blank
puzzleState newState = new puzzleState(temp);
return newState;
}
}
/**
* This method moves the zero down.
*/
public puzzleState moveDown(puzzleState stateIn)
{
int blankPos = stateIn.getBlank(); //locate zero with incoming state
if (blankPos == 6 || blankPos == 7 || blankPos == 8) {
//JOptionPane.showMessageDialog(null,"Invalid State");
return null;
}
else {
int[] temp = stateIn.getArray(); //get the array
int temp2 = temp[blankPos+3]; //store dest in temp
temp[blankPos+3]=Zero; //move blank into dest
temp[blankPos]=temp2; //move temp into blank
puzzleState newState = new puzzleState(temp);
return newState;
}
}
/**
* This method moves the zero left.
*/
public puzzleState moveLeft(puzzleState stateIn)
{
int blankPos = stateIn.getBlank(); //locate zero with incoming state
if (blankPos == 0 || blankPos == 3 || blankPos == 6) {
//JOptionPane.showMessageDialog(null,"Invalid State");
return null;
}
else {
int[] temp = stateIn.getArray(); //get the array
int temp2 = temp[blankPos-1]; //store dest in temp
temp[blankPos-1]=Zero; //move blank into dest
temp[blankPos]=temp2; //move temp into blank
puzzleState newState = new puzzleState(temp);
return newState;
}
}
/**
*this method is responsible for randomizing the problem in any possible state
*
*/
private int[] randomizeInitialState() {
puzzleState randState;
int[] victim = {1,2,3,4,5,6,7,8,0}; //the victim to be randomized
Random rand = new Random();
int max = 8;
int victim2=0;
for (int i=0; i<= max; i++) {
victim2=rand.nextInt(max+1);
//System.out.println(victim2);
if (i==0) victim=victim2;
else if (contains(victim, i, victim2)==true) i--;
else if (contains(victim, i, victim2)==false)
victim=victim2;
}
return victim;
}
private boolean contains(int[] victim, int size, int element) {
int counter=0;
boolean flag=false;
while (counter <= size) {
if (victim[counter] == element) {
flag = true;
//System.out.println("collsion:"+element);
}
counter++;
}
return flag;
}
public puzzleState randomize() {
System.out.println("Randomize:");
int[] victim = randomizeInitialState();
puzzleState victim2 = new puzzleState(victim);
return victim2;
}
/**
* This method moves the zero right.
*/
public puzzleState moveRight(puzzleState stateIn)
{
int blankPos = stateIn.getBlank(); //locate zero with incoming state
if (blankPos == 2 || blankPos == 5 || blankPos == 8) {
//JOptionPane.showMessageDialog(null,"Invalid State");
return null;
}
else {
int[] temp = stateIn.getArray(); //get the array
int temp2 = temp[blankPos+1]; //store dest in temp
temp[blankPos+1]=Zero; //move blank into dest
temp[blankPos]=temp2; //move temp into blank
puzzleState newState = new puzzleState(temp);
return newState;
}
}
/**
Performs a puzzle move on the given puzzle state.
@param state and exisiting puzzle state.
@return a new state resulting from the move
*/
public puzzleState doMove(State state) {
puzzleState finalState;
puzzleState state1 = (puzzleState) state;
state = (puzzleState) state;
finalState = TestMove(state1);
return finalState;
}
private puzzleState TestMove(puzzleState testState){
puzzleState newState = testState;
char ch = getMoveName().charAt(SECOND);
switch(ch) {
case 'l':
newState = moveLeft(testState);
break;
case 'r':
newState = moveRight(testState);
break;
case 'u':
newState = moveUp(testState);
break;
case 'd':
newState = moveDown(testState);
break;
case 'a':
newState = randomize();
break;
default:
System.out.println("Error in Switch Statement.");
newState = null;
// ****** MAYBE NOT newState = NULL
}//end switch
return newState;
}//end TestMove
}
package puzzle;
import framework.*;
import java.util.*;
/**
This class keeps track of the current state of the puzzle problem,
collects the legal bridge moves, attempts to transform the current state
given a user command, and checks for problem success.
*/
public class puzzleProblem extends Problem{
/**
begin holds the intial puzzleState
*/
private static puzzleState begin;
private int heur;
/**
moves holds the list of moves availbile
*/
private static ArrayList moves;
/**
Creates a new puzzle problem
@param init The initial puzzle State
@param moves The list of legal puzzle Moves
*/
public puzzleProblem (/*puzzleState init, ArrayList moveList, String intro*/){
super(init, new ArrayList(Arrays.asList(moveList)), intro);
begin = (puzzleState) init;
}
/**
Tests for whether the current state of the problem represent success
@return true if the user gets 1 through 8 around the edge of the grid
*/
public boolean success(State state){
begin = (puzzleState) state; //super.getCurState();
int[] temp = begin.getArray();
if(temp[0]==1 && temp[1]==2 && temp[2]==3 && temp[3]==8 && temp[4]==0 && temp[5]==4 && temp[6]==7 && temp[7]==6 && temp[8]==5 ){
return true;
}//end if
else{
return false;
}//end else
}
/**
*Accessor for the current state
*@return puzzleState
*/
public puzzleState getCurState() {
begin = (puzzleState)super.getCurState();
return begin;
}
/**
* Computes the heuristic value for a given state.
* This is using A* search.
* @param state a state to compute the heuristic for
* @return the heuristic value
*/
public int computeHeuristic(State state)
{
int md = 0;
begin = (puzzleState) state;
int[] temp = begin.getArray();
/**
*Calculating the number of moves the corresponding
*number is away from the goal state.
*Checking the first position.
**/
if (temp[0] == 1)
md += 0;
else if (temp[0] == 2)
md += 1;
else if (temp[0] == 3)
md += 2;
else if (temp[0] == 4)
md += 3;
else if (temp[0] == 5)
md += 4;
else if (temp[0] == 6)
md += 3;
else if (temp[0] == 7)
md += 2;
else if (temp[0] == 8)
md += 1;
/**
*Checking the second position
*/
if(temp[1] == 1)
md += 1;
else if(temp[1] == 2)
md += 0;
else if(temp[1] == 3)
md += 1;
else if(temp[1] == 4)
md += 2;
else if(temp[1] == 5)
md += 3;
else if(temp[1] == 6)
md += 2;
else if(temp[1] == 7)
md += 3;
else if(temp[1] == 8)
md += 2;
/**
*Checking the third position.
*/
if(temp[2] == 1)
md += 2;
else if(temp[2] == 2)
md += 1;
else if(temp[2] == 3)
md += 0;
else if(temp[2] == 4)
md += 1;
else if(temp[2] == 5)
md += 2;
else if(temp[2] == 6)
md += 3;
else if(temp[2] == 7)
md += 4;
else if(temp[2] == 8)
md += 3;
/**
*Checking the third position
*/
if(temp[3] == 1)
md += 1;
else if(temp[3] == 2)
md += 2;
else if(temp[3] == 3)
md += 3;
else if(temp[3] == 4)
md += 2;
else if(temp[3] == 5)
md += 3;
else if(temp[3] == 6)
md += 2;
else if(temp[3] == 7)
md += 1;
else if(temp[3] == 8)
md += 0;
/**
*Checking the fourth position.
*/
if(temp[4] == 1)
md += 2;
else if(temp[4] == 2)
md += 1;
else if(temp[4] == 3)
md += 2;
else if(temp[4] == 4)
md += 1;
else if(temp[4] == 5)
md += 2;
else if(temp[4] == 6)
md += 1;
else if(temp[4] == 7)
md += 2;
else if(temp[4] == 8)
md += 1;
/**
*Checking the fifth position.
*/
if (temp[5] == 1)
md += 3;
else if (temp[5] == 2)
md += 2;
else if (temp[5] == 3)
md += 1;
else if (temp[5] == 4)
md += 0;
else if (temp[5] == 5)
md += 1;
else if (temp[5] == 6)
md += 2;
else if (temp[5] == 7)
md += 3;
else if (temp[5] == 8)
md += 2;
/**
*Checking the sixth position.
*/
if (temp[6] == 1)
md += 2;
else if (temp[6] == 2)
md += 3;
else if (temp[6] == 3)
md += 4;
else if (temp[6] == 4)
md += 3;
else if (temp[6] == 5)
md += 2;
else if (temp[6] == 6)
md += 1;
else if (temp[6] == 7)
md += 0;
else if (temp[6] == 8)
md += 1;
/**
*Checking the seventh position.
*/
if (temp[7] == 1)
md += 3;
else if (temp[7] == 2)
md += 2;
else if (temp[7] == 3)
md += 3;
else if (temp[7] == 4)
md += 2;
else if (temp[7] == 5)
md += 1;
else if (temp[7] == 6)
md += 0;
else if (temp[7] == 7)
md += 1;
else if (temp[7] == 8)
md += 2;
/**
*Checking the eighth position.
*/
if (temp[8] == 1)
md += 4;
else if (temp[8] == 2)
md += 3;
else if (temp[8] == 3)
md += 2;
else if (temp[8] == 4)
md += 1;
else if (temp[8] == 5)
md += 0;
else if (temp[8] == 6)
md += 1;
else if (temp[8] == 7)
md += 2;
else if (temp[8] == 8)
{ md += 3; }
heur = md;
return md;
}
public String getIntroduction() {
return intro;
}
public int getHeur() {
return heur;
}
/**
*array for list of legal moves
*/
private static puzzleMove[] moveList = {new puzzleMove(puzzleMove.ML),new puzzleMove(puzzleMove.MR),new puzzleMove(puzzleMove.MU),new puzzleMove(puzzleMove.MD), new puzzleMove(puzzleMove.randM)};
/**
*a basic initial state to start the game with
*/
private static int[] puzzleInit = {2,4,5,1,3,7,6,8,0};//==randomizeState
//private static int[] puzzleInit = randomizeInitialState();
/**
*private var State init is the initial state and will be provided by either the basic example or the randomize function
*/
private static State init = new puzzleState(puzzleInit);
private static String intro = "Welcome to the 8 Puzzle!\n\nMove the blank tile to get the following configuration:\n\n1\t2\t3\n8\t \t4\n7\t6\t5\n";
}//end class
package puzzle;
import framework.*;
import javax.swing.*;
import java.awt.*;
import java.awt.geom.*;
import java.awt.event.*;
import java.util.*;
/**
This class is responsible for displaying the puzzle GUI.
*/
public class puzzleGUI implements UI{
/**
The problem.
*/
private puzzleProblem problems;
/**
The number of moves user has taken in solving the problem.
*/
private int moveCount;
/**
*The internal frame.
*/
public final JInternalFrame frame;
/**
Button Height
*/
private final int BUTTON_HIDTH = 10;
/**
Button Width
*/
private final int BUTTON_WIDTH = 30;
/**
Frame Width
*/
private final int FRAME_WIDTH = 600;
/**
Frame Height
*/
private final int FRAME_HIDTH = 500;
/**
* Strings for image filenames
*/
private final String Ione = "images/one.jpg";
private final String Itwo = "images/two.jpg";
private final String Ithree = "images/three.jpg";
private final String Ifour = "images/four.jpg";
private final String Ifive = "images/five.jpg";
private final String Isix = "images/six.jpg";
private final String Iseven = "images/seven.jpg";
private final String Ieight = "images/eight.jpg";
private final String Iblank = "images/blank.jpg";
public ImageIcon one = new ImageIcon(Ione);
public JLabel Jone = new JLabel(one);
public ImageIcon two = new ImageIcon(Itwo);
public JLabel Jtwo = new JLabel(two);
public ImageIcon three = new ImageIcon(Ithree);
public JLabel Jthree = new JLabel(three);
public ImageIcon four = new ImageIcon(Ifour);
public JLabel Jfour = new JLabel(four);
public ImageIcon five = new ImageIcon(Ifive);
public JLabel Jfive = new JLabel(five);
public ImageIcon six = new ImageIcon(Isix);
public JLabel Jsix = new JLabel(six);
public ImageIcon seven = new ImageIcon(Iseven);
public JLabel Jseven = new JLabel(seven);
public ImageIcon eight = new ImageIcon(Ieight);
public JLabel Jeight = new JLabel(eight);
public ImageIcon blank = new ImageIcon(Iblank);
public JLabel Jblank = new JLabel(blank);
public JPanel puzzlePanel = new JPanel();
public JPanel framePanel = new JPanel();
public JPanel buttonPanel = new JPanel();
public Container contentPane;
public GridLayout myGrid = new GridLayout(3,3,0,0);
public JTextArea intro, ePanel;
public String menu = "\n\nml=move blank left\nmr=move blank right\nmu=move blank up\nmd=move blank down";
/**
*constructor sets up a new GUI for the puzzle game
*@param puzzleProblem problem
*/
public puzzleGUI(puzzleProblem problem){
JButton moveL, moveR, moveU, moveD, random, solve, quit;
problems = problem;
problems.setUI(this);
moveCount = 1;
frame = new JInternalFrame();
contentPane = frame.getContentPane();
frame.setSize(FRAME_WIDTH, FRAME_HIDTH);
frame.setTitle("Puzzle Problem");
// JPanel framePanel = new JPanel();
framePanel.setLayout(new BorderLayout());
intro = new JTextArea();
intro.setText(problems.getIntroduction());
intro.setEditable(false);
intro.setBounds(25, 10, 400, 200);
framePanel.add(intro,BorderLayout.NORTH);
ePanel = new JTextArea();
ePanel.setText("InfoPanel:\nmoveCount:0"+menu);
ePanel.setEditable(false);
//ePanel.setBounds(25, 10, 400, 200);
framePanel.add(ePanel,BorderLayout.CENTER);
//JPanel buttonPanel = new JPanel();
buttonPanel.setLayout(new FlowLayout());
//GridLayout myGrid = new GridLayout(3,3,0,0);
puzzlePanel.setLayout(myGrid);
puzzlePanel.setBackground(Color.WHITE);
String buttonLabels = "ml mr mu md rand solve";
StringTokenizer parser = new StringTokenizer(buttonLabels);
while(parser.hasMoreTokens()){
final String label = parser.nextToken();
JButton keyButton = new JButton(label);
buttonPanel.add(keyButton);
keyButton.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent event){
problems.processCommand(label);
}
});
}//end while
quit = new JButton("Quit");
quit.setBounds(175, 350, BUTTON_WIDTH, BUTTON_HIDTH);
quit.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent event){
System.exit(0);
}});
buttonPanel.add(quit);
int[] tiles = problems.getCurState().getArray();
int i=0;
while (i<=8) {
puzzlePanel.add(getLabel(tiles));
i++;
}
framePanel.add(buttonPanel, BorderLayout.SOUTH);
framePanel.add(puzzlePanel, BorderLayout.WEST);
contentPane.add(framePanel);
frame.setDefaultCloseOperation(JInternalFrame.EXIT_ON_CLOSE);
frame.pack();
frame.show();
}//end constructor
/**
Accessor for the problem.
@return the problem.
*/
public puzzleProblem getProblem() {
return problems;
}
/**
Accessor for the move count
@return the move count.
*/
public int getMoveCount(){
return moveCount;
}
/**
*this method increments movecount and checks for success
*/
public void getCommand() {
moveCount++;
puzzleState current = problems.getCurState();
if(problems.success(current)){
JOptionPane.showMessageDialog(null, "Congratulations. You solved the problem in " + moveCount + " moves");//" and in " + time + " minutes.");
}
}
/**Displays Message to the user
*@param String
*/
public void displayMessage(String message){
JOptionPane.showMessageDialog(null,message);
}
/**
Gets the current state from the problem and displays it to the
user.
*/
public void update() {
problems.computeHeuristic(problems.getCurState());
int heur = problems.getHeur();
int[] tiles = problems.getCurState().getArray();
int i=0;
while (i<=8) {
puzzlePanel.add(getLabel(tiles));
i++;
}
ePanel.setText("InfoPanel:\nmoveCount:"+moveCount+"\nheuristic:"+heur+menu);
ePanel.updateUI();
puzzlePanel.updateUI();
}
/**
GetIcon gets the icon on the Jframe
*/
public JLabel getLabel(int label){
if (label == 0) {return Jblank;}
else if (label == 1) {return Jone;}
else if (label == 2) {return Jtwo;}
else if (label == 3) {return Jthree;}
else if (label == 4) {return Jfour;}
else if (label == 5) {return Jfive;}
else if (label == 6) {return Jsix;}
else if (label == 7) {return Jseven;}
else if (label == 8) {return Jeight;}
else return null;
}
/**
*Accessor for the internal frame
*/
public JInternalFrame getFrame() {
return frame;
}
}//end class
A-star AI 8-Puzzle
Author
Here is my source code in java. I need to devise a AI for automatically solving any given state. Any help would be much appreciated. I am lost for this part of my project. The goal state is like this
1 2 3
8 0 4
7 6 5 where 0 is the blank
edit: added source tags -SiCrane
[Edited by - SiCrane on December 14, 2005 8:10:54 AM]
Author
I need to have the COMputer solve the puzzle auto. using A* search. Dont have a clue Please help
A good explanation of A* can be found here
It's about 10 lines of code given the framework you posted above.
It's about 10 lines of code given the framework you posted above.
It looks like it's an homework... but I might be wrong.
C-Pizzle, if you have any SPECIFIC question, ask it, but we can't/won't do the work for you.
Eric
C-Pizzle, if you have any SPECIFIC question, ask it, but we can't/won't do the work for you.
Eric
This looks very much like a homework problem. The source code posted is documented in a style typically used in teaching (I should know ;) ) and the fact that the OP joined today is a dead-giveaway. C-Pizzle, we don't do peoples homework for them. The members of this forum would be happy to help by answering specific questions that would enable you to understand the A* algorithm better. However, we won't write your code for you. I suggest you follow the link at the top of the page to the Articles & Resources section of this website and read the articles under AI:Pathfinding. If you have trouble understanding any of that material, feel free to post here. Otherwise, please don't try and solicit answers to your homework.
Regards,
Timkin
Regards,
Timkin
Author
FOr everyones information I wrote this myself, I have a framework package that i also wrote. I just want to have AI to solve for it and i dontknow how to begin.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
