Chris Pollett>Old Classes>PIC 20, Winter 2000>Hw4>Hw4 Solutions
// Program Name: FPuzzle.java
//
// Purpose: This is the file that contains the applet part of a program
// to play the 2X2, 3X3, 4X4, version 5X5 of the Tile game
//
// Known Bugs: Probably could break the init method into a nicer grouping
// of methods.
//
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
public class FPuzzle extends JApplet
{
Puzzle puzzle; // this is a JPanel where actual puzzle drawn
int size = 3; // initial puzzle size.
Container c;
JButton randomize, solve;
JPanel buttonPanel, sizeAndLabel, directionGadget;
JLabel sizeLabel,title;
// Name: init()
//
// Purpose: This method adds all the GUI components onto theapplet
//
// Known Bugs: Should probably be split into smaller methods
//
public void init()
{
String sizeArray[] = new String[size+1]; // Strings for the
//JComboBox
for(int i=0; i <= size;i++)
{
sizeArray[i] = ""+(i+2);
}
//
//set up the background layout and font of the applet
//
c = getContentPane();
c.setBackground(Color.white);
c.setLayout(new BorderLayout());
c.setFont( new Font("Serif",Font.PLAIN,15));
//
// add title label
//
title = new JLabel("Tile Puzzle");
title.setFont( new Font("Serif", Font.BOLD,30));
c.add(title,BorderLayout.NORTH);
//
//add puzzle
//
puzzle = new Puzzle(size,c);
puzzle.setBackground(Color.white);
c.add(puzzle,BorderLayout.CENTER);
//
// add SizeSelector and set up its listener
//
sizeLabel = new JLabel("Size Selector");
sizes = new JComboBox(sizeArray);
sizes.setMaximumRowCount(3);
sizes.setSelectedIndex(size-2);
sizes.addItemListener(
new ItemListener()
{
public void itemStateChanged(ItemEvent e)
{
int sel= sizes.getSelectedIndex();
if(sel+ 2 != size)
{
size = sel + 2;
puzzle.setPuzzleSize(size);
c.repaint();
}
}
});
//
//Initalize and add listeners to buttons controlling
//movement
//
setUpDirectionGadget();
//
//Put sizeLabel JLabel, sizes JComboBox, and direction gadget
// on a JPanel and add it to the applet
//
sizeAndLabel = new JPanel();
sizeAndLabel.setLayout(new GridLayout(3,1,5,5));
sizeAndLabel.setBackground(Color.white);
sizeAndLabel.add(sizeLabel);
sizeAndLabel.add(sizes);
sizeAndLabel.add(directionGadget);
c.add(sizeAndLabel,BorderLayout.EAST);
//
//add the randomize and solve buttons and their listeners
//
randomize =new JButton("Randomize");
randomize.addActionListener(
new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
puzzle.randomize();
c.repaint();
}
}
);
solve =new JButton("Solve");
solve.addActionListener(
new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
puzzle.solveTimer(FPuzzle.this);
}
} );
buttonPanel = new JPanel();
buttonPanel.setLayout(new GridLayout(1,2,5,5));
buttonPanel.setBackground(Color.white);
buttonPanel.add(randomize);
buttonPanel.add(solve);
c.add(buttonPanel, BorderLayout.SOUTH);
}
// Name: setUpDirectionGadget()
//
// Purpose: Puts the four direction control buttons on a JPanel
// and adds their listeners. The movements should
// be thought of moving the hole around
//
// Known Bugs:
//
void setUpDirectionGadget()
{
directionGadget = new JPanel();
directionGadget.setLayout(new BorderLayout());
directionGadget.setBackground(Color.white);
JLabel move;
JButton north,south,east,west;
move = new JLabel("move");
directionGadget.add(move,BorderLayout.CENTER);
north = new JButton("^");
north.addActionListener(
new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
puzzle.move(Puzzle.NORTH);
FPuzzle.this.repaint();
}
}
);
east = new JButton(">");
east.addActionListener(
new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
puzzle.move(Puzzle.EAST);
FPuzzle.this.repaint();
}
}
);
west = new JButton("<");
west.addActionListener(
new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
puzzle.move(Puzzle.WEST);
FPuzzle.this.repaint();
}
}
);
south = new JButton("v");
south.addActionListener(
new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
puzzle.move(Puzzle.SOUTH);
FPuzzle.this.repaint();
}
}
);
directionGadget.add(north,BorderLayout.NORTH);
directionGadget.add(east,BorderLayout.EAST);
directionGadget.add(west,BorderLayout.WEST);
directionGadget.add(south,BorderLayout.SOUTH);
}
}
// Program Name: Puzzle.java
//
// Purpose: This class extends JPanel and is used to draw the tile puzzle
// It has a method move(i) which given a direction will
// will move the whole in the puzzle in that direction. it also
// has a public method randomize() to randomize the puzzle and
// a method solveTimer() which solves the puzzle and
// and starts a timer of the moves to do in carrying out the
// solution.
//
//
// Known Bugs: The directions for NORTH SOUTH EAST WEST have been modified
// to improve speed of the move method. It would not be too
// hard to change move(i) to map the spec values to these values
// then do move(i, puzzleArray) but would probably make the code
// less clear
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import java.util.*;
public class Puzzle extends JPanel
{
public static final int NORTH=-1, SOUTH=1, WEST=-2, EAST=2;
//integer values correspond to moving
// moving a tile. Not exactly as in the spec
// see above. Notice NORTH = -SOUTH
// and WEST = -EAST. Will use this to save
// copying boards in minToConsider method
public int searchDelay=10; // time between moves when showing
//solution to puzzle
public int moveDelay=10; //timer delay bewteen 2 pixel increments
//in moving a piece
public int pieceSizeX =40, pieceSizeY=40; // x and y dimension of
// a tile
public int slideX, slideY,xOff, yOff, mDir;
//x and y in matrix of puzzle of piece being moved
//xOff and yOff are how many pixels the tile has
//currently been moved
//mdir is the movement direction
public boolean moving=false, wasRunning =false;
//booleans used in drawing the puzzle if a piece is moving
//and for the timers
public int ranMoves=200; // hom many random moves to insert
//in randomizing the board
Container c; //container of the applet
JApplet test; //name of applet that puzzle lives on so
// we can call showStatus
Rectangle tile; //tile shape
GradientPaint tColor; //gradient paint for the tile
Rectangle border; // big rectangle for perimeter of puzzle
int puzzleArray[][]; //array which stores the puzzle
int tmp[][]; // temporary array used in solving puzzle
int less[][]; // temporary array use to store
// puzzle of current lowest value
// while solving the puzzle
Point blankLocation =new Point(0,0); //used in solving the
//puzzle to store the x,y location
// of the hole on the current board
//under consideration
int puzzleSize,colSize,rowSize; // respectively
// the number of tiles in a row or column, the
// number of pixels in a column, and the number
// of pixels in a row
int totalNumPieces;//total number of squares in the puzzle
Timer puzzleTimer, moveTimer;
Hashtable active;
HashSet inActive;
// Name: Puzzle
//
// Purpose: constructor for the Puzzle. It sets the container
// whose repaint method should be called during a move
// then initializes the puzzle array.
//
// Known Bugs:
//
public Puzzle(int pSize, Container parent)
{
c=parent;
setPuzzleSize(pSize);
}
// Name: setPuzzleSize
//
// Purpose: Initializes the puzzleArray as well as any global
// variables that depend on puzzleSize.
//
// Known Bugs:
//
public void setPuzzleSize(int pSize)
{
if (puzzleTimer != null) puzzleTimer.stop();
if (moveTimer != null) moveTimer.stop();
puzzleSize = pSize;
totalNumPieces = puzzleSize;
puzzleArray = new int[puzzleSize][puzzleSize];
//elts initialized to zero
tmp=new int[puzzleSize][puzzleSize];
less =new int[puzzleSize][puzzleSize];
tile=new Rectangle(0,0,pieceSizeX,pieceSizeY);
tColor = new GradientPaint( 0,0,Color.white,
pieceSizeX, pieceSizeY,Color.blue,false);
colSize = pieceSizeY*puzzleSize;
rowSize = pieceSizeX*puzzleSize;
border = new Rectangle(5,5,10+rowSize,10+colSize);
randomize();
}
// Name: randomize
//
// Purpose: Inserts ranMoves many move into the board to randomize it
//
// Known Bugs:
//
public void randomize()
{
int tmp =0;
// make sure timers don't go off
if (puzzleTimer != null) puzzleTimer.stop();
if (moveTimer != null) {moveTimer.stop();
moving = false;}
for(int i =0; i< puzzleSize; i++)
{
for(int j=0; j< puzzleSize; j++)
{
puzzleArray[i][j] = i+j*puzzleSize;
}
}
for(int i= 0; i< ranMoves; i++)
{
tmp = (int)(Math.random()*4.99)-2;
if(tmp==0) continue;
move( tmp,puzzleArray);
}
}
// Name: solveTimer
//
// Purpose: Solves the puzzle and sets up a Timer to execute the
// solution moves
//
// Known Bugs:
//
public void solveTimer(JApplet par)
{
test=par;
if(puzzleTimer != null) puzzleTimer.stop();
puzzleTimer = new Timer(searchDelay, new ActionListener()
{
Stack s =new Stack();
public void actionPerformed(ActionEvent e)
{
if(s.isEmpty()){
puzzleTimer.stop();
s=Puzzle.this.solve();
if(!s.isEmpty())
puzzleTimer.restart();
}
else
{move(((Integer)s.pop()).intValue());}
}
} );
puzzleTimer.start();
}
// Name: getEmpty
//
// Purpose: Put into the global variable blankLocation
// the x,y value of the blank in board[][]
//
// Known Bugs:
//
void getEmpty(int board[][])
{
for(int i=0; i < puzzleSize;i++)
{
for(int j=0; j < puzzleSize; j++)
{
if(board[i][j]==0)
{blankLocation.setLocation(i,j); return;}
}
}
}
// Name: valuePuzzle
//
// Purpose: Computes the value of a board according to
// the sum of the distance each piece is from their
// correct position
//
// Known Bugs:
//
public int valuePuzzle(int board[][])
{
int sum =0;
int tmp;
for(int i=0; i < puzzleSize; i++)
{
for(int j=0; j < puzzleSize; j++)
{
tmp = board[i][j];
sum += Math.abs(i-tmp%puzzleSize)
+ Math.abs(j-tmp/puzzleSize);
}
}
return sum;
}
// Name: move(int i)
//
// Purpose: public method used by FPuzzle and solveTimer
// to move the puzzle pieces
//
// Known Bugs:
//
public void move(int i)
{
getEmpty(puzzleArray);
xOff =0;
yOff =0;
if(!move(i,puzzleArray)) return;
slideX = blankLocation.x;
slideY = blankLocation.y;
mDir = (i >0)? 1 : -1;
if(Math.abs(i) == 1) yOff=pieceSizeY;
else xOff=pieceSizeX;
moving =true;
wasRunning = false;
moveTimer = new Timer(moveDelay, new ActionListener()
{
public void actionPerformed(ActionEvent e)
{ c.repaint();
if(xOff == 0 && yOff == 0)
{ moving = false;
moveTimer.stop();
if(wasRunning) puzzleTimer.restart();
}
if( xOff> 0) xOff-=2;
if( yOff> 0) yOff-=2;
}
});
if(puzzleTimer != null && puzzleTimer.isRunning())
{
puzzleTimer.stop();
wasRunning=true;
}
moveTimer.start();
}
// Name: move(int i, int board[][])
//
// Purpose: changes board[][] to the puzzle that
// that would result if move i was applied
// If move can be applied true is returned
// If move not valid false returned
//
// Known Bugs:
//
boolean move(int i, int board[][])
{
getEmpty(board);
int xLoc = blankLocation.x;
int xMov = xLoc + i/2;
int yLoc = blankLocation.y;
int yMov = yLoc + i%2;
if(xMov < 0 || xMov >= puzzleSize ||
yMov < 0 || yMov >= puzzleSize)
return false;
board[xLoc][yLoc] = board[xMov][yMov];
board[xMov][yMov] = 0;
return true;
}
// Name: solve()
//
// Purpose: solves the puzzle returns a stack with the moves for
// the solution. Uses the A* algorithm
//
// Known Bugs:
//
public Stack solve()
{
active = new Hashtable(); // Hashtable is in java.util
// entries are key value pair
// and given a key the method
// to look up the associated value
// is very fast
inActive = new HashSet(); //Hashset is in java.util
//It contains collection of objects
//and the method to see if an
//object is already stored is
//very fast
Stack ansStack = new Stack();
BoardNode b;
Integer hash;
int min =valuePuzzle(puzzleArray);
if(min == 0 ) return ansStack;
b =new BoardNode();
b.setBoard(puzzleArray,null, min, 0,0);
active.put(hashBoard(puzzleArray),b);
while(!active.isEmpty())
{
b=minToConsider();
if(b.value == 0) return b.path();
//check if any node should be moved to
//the inActive Hashset
if(nodeDone(b.parent))
{
hash=hashBoard(b.parent.board);
inActive.add(hash);
active.remove( hash );
}
if(nodeDone(b))
{
hash=hashBoard(b.board);
inActive.add(hash);
active.remove(hash);
}
else {
active.put(hashBoard(b.board),b);
}
}
return ansStack;
}
// Name: minToConsider()
//
// Purpose: Searches the children of the active
// Hashtable BoardNodes and returns the
// least child that has not yet been considered
//
// Known Bugs:
//
public BoardNode minToConsider()
{
BoardNode b, least=new BoardNode();
int min = 1000;
int val,depth,heu;
Integer hash;
Enumeration e=active.elements(); //an Enumeration
// is a class in java.util
// If a class has a method
// to returns an enumeration
// then the Enumeration
// can be used to list out the
// data stored in the class.
// In this case the active's
// element() method returns an
// Enumeration class for the values
// stored in the Hashtable.
// The Enumeration methods
// nextElement()
// and hasMoreElements() can be used to
// list out these values.
// Like an Iterator in C++ or
// Java 1.2
while(e.hasMoreElements())
{
b = (BoardNode)e.nextElement();
copyBoard(b.board,tmp);
depth = b.depth+1;
for(int j=-2; j <= 2; j++)
{
if(j == 0) j++;
if(!move(j,tmp)) continue;
val=valuePuzzle(tmp);
hash=hashBoard(tmp);
heu = val+depth; // this is the A* heuristic
if(heu < min&&!active.containsKey(hash)
&&!inActive.contains(hash))
{
min = heu;
copyBoard(tmp,less);
least.setBoard(less,b,val,j,depth);
}
move(-j,tmp); //undoes the just tried move
}
}
test.showStatus("depth="+least.depth+"val="+least.value);
return least;
}
// Name: hashBoard
//
// Purpose: returns a unique integer object corresponding
// to a board. To check if two key object
// are equal in a Hashtable the equals method of
// method of the object is called. The default
// equals in the Object class just compares
// references but that of the Integer class
// actually checks if the numbers stored in the objects
// are equal. This was the reason this function was written
//
// Known Bugs: For the 5X5 board there may be conflicting
// keys so would probably be better off
// returning Long but that would be slower.
public Integer hashBoard( int board[][])
{
int hash=0;
for(int i =0 ; i < puzzleSize; i++)
{
for(int j=0; j < puzzleSize; j++)
{
hash += board[i][j];
hash *= totalNumPieces;
}
}
return new Integer(hash);
}
// Name: nodeDone
//
// Purpose: Returns true if all the children of the
// BoardNode b either appear in active or inActive
//
// Known Bugs:
//
public boolean nodeDone (BoardNode b)
{
Integer hash;
copyBoard(b.board,tmp);
for(int i=-2; i <= 2; i++)
{
if(i==0) i++;
if(!move(i,tmp)) continue;
hash=hashBoard(tmp);
if(!active.containsKey(hash) &&
!inActive.contains(hash))
{
move(-i,tmp); //undo just tried move
return false;
}
move(-i,tmp); //undoes the just tried move
}
return true;
}
// Name: copyBoard
//
// Purpose: copies the puzzle in board to board2
//
// Known Bugs:
//
void copyBoard(int board[][], int board2[][])
{
for(int i =0 ; i< puzzleSize; i++)
{
for(int j =0 ; j < puzzleSize; j++)
{ board2[i][j]=board[i][j];}
}
}
// Name: paint
//
// Purpose: draws the puzzle
//
// Known Bugs:
//
public void paint( Graphics g)
{
Graphics2D g2d = (Graphics2D) g;
AffineTransform t;
int pieceij;
int xOffDir = xOff*mDir;
int yOffDir = yOff*mDir;
g2d.setPaint(Color.black);
g2d.fill( border);
g2d.translate(10-pieceSizeX,10+colSize-pieceSizeY);
for(int i=0; i < puzzleSize; i++)
{
g2d.translate(pieceSizeX,-colSize);
for(int j=0; j < puzzleSize;j++)
{
pieceij = puzzleArray[i][j];
g2d.translate(0,pieceSizeY);
if(pieceij != 0 &&
(!moving || slideX !=i || slideY !=j))
{
g2d.setPaint(tColor);
g2d.fill( tile);
g2d.setColor(Color.black);
g2d.drawString( ""+pieceij,15,15);
}
else if(pieceij==0 && moving)
{
t= g2d.getTransform();
g2d.translate(pieceSizeX*(slideX-i),
pieceSizeY*(slideY-j));
g2d.setPaint( Color.black);
g2d.fill( tile);
g2d.translate(xOffDir,yOffDir);
g2d.setPaint( tColor);
g2d.fill( tile);
g2d.setPaint(Color.black);
g2d.drawString(""+ puzzleArray[slideX][slideY],
15, 15);
g2d.setTransform(t);
}
}
}
}
// Name: class BoardNode
//
// Purpose: This class is used by solve() to store
// data on board that it is considering as part of the
// solution process. The data that is stored is the
// board itself, the parent BoardNode, the value of the
// board, the move that changed the parent to this board,
// and depth of the branch from puzzleArray to this board.
//
// Known Bugs:
//
class BoardNode
{
public int board[][] =new int[puzzleSize][puzzleSize];
public BoardNode parent;
public int value, move, depth;
// Name: BoardNode
//
// Purpose: Constructor. It does nothing since for
// speed considerations was faster to do things in
// setBoard.
//
// Known Bugs:
//
public BoardNode() {}
// Name: setBoard
//
// Purpose: set the values of all the parameters of
// the BoardNode
//
// Known Bugs:
//
public void setBoard(int b[][],BoardNode par,
int val,int mv,int d)
{
copyBoard(b,board);
parent =par;
value =val;
depth =d;
move =mv;
}
// Name: path
//
// Purpose: Returns a Stack with the path of moves
// from puzzleArray to this board
//
// Known Bugs:
//
public Stack path()
{
Stack s =new Stack();
BoardNode tmp = this;
do{
s.push(new Integer(tmp.move));
tmp = tmp.parent;
} while (tmp != null);
s.pop(); //top element move doesn't count
return s;
}
}
}