A-star AI 8-Puzzle

C-Pizzle · 2005-12-15T18:20:33

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 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 edit: added source tags -SiCrane [Edited by - SiCrane on December 14, 2005 8:10:54 AM]

Artificial Intelligence Programming

Started by C-Pizzle December 14, 2005 02:18 AM

9 comments, last by Timkin 18 years, 4 months ago

Timkin

864

December 15, 2005 06:20 PM

As to where to begin... as I said, read the articles by following the Resources link at the top of the page. Anyone capable of writing the code posted is capable of understanding the material presented in those articles and could write an implementation of A*. It's a straightforward algorithm with nothing technically difficult about its implementation.

Cheers,

Timkin

A-star AI 8-Puzzle

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

A-star AI 8-Puzzle

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines