<TeePuzzleSolver.java>=
class TeePuzzleSolver
implements TeePuzzle
public Jump []
solve(int size, TeePuzzle.Coordinate holes[], StateGraph g)
final Frontier frontier =
new Frontier(new Path(new TeePuzzleInstance(size, holes)))
do
final Path path = frontier.pick()
final TeePuzzleInstance endState = path.endState()
if endState.isGoalState()
return path.asJumpArray()
for TeePuzzleInstance neighbor : endState.neighbors()
frontier.add(path.extend(neighbor))
while (!frontier.isEmpty())
return null
DefinesTeePuzzleSolver,TeePuzzleSolver.java(links are to index).
The Frontier
Poole and Mackworth define a frontier as a set of paths, and there's no reason
to contradict that definition.
<Frontier.java>=
import java.util.HashSet
class Frontier
extends HashSet<Path>
/**
Create a frontier containing a path.
path: The path in the new frontier.
*/
Frontier(Path path)
add(path)
/**
Pick a path from this frontier.
Returns: The path picked from this frontier. The path is removed from this
frontier.
@exception NoSuchElementException if this frontier is empty.
*/
Path
pick()
final Path path = iterator().next()
remove(path)
return path
DefinesFrontier,Frontier.java(links are to index).
<Path.java>=
class Path
/**
Find the array of jumps that created this path.
Returns: The array of jumps that created this path.
*/
TeePuzzle.Jump []
asJumpArray()
final TeePuzzle.Jump jumps[] = new TeePuzzle.Jump [length - 1]
for Path a = this; a.length > 1; a = a.ancestors
jumps[a.length - 2] = a.state.creatorJump()
return jumps
/**
Create a new path by adding a state to the end of this path.
state: The state to be appended.
Returns: A new path that has this path as the prefix and the given state as
the suffix.
*/
Path
extend(TeePuzzleInstance state)
return new Path(this, state, length + 1)
/**
Find the end state on this path.
Returns: The end state on this path.
*/
TeePuzzleInstance
endState()
return state
/**
Create a empty path.
*/
Path(TeePuzzleInstance s)
state = s
ancestors = null
length = 1
private
Path(Path a, TeePuzzleInstance s, int l)
state = s
ancestors = a
length = l
private final TeePuzzleInstance state
private final Path ancestors
private final int length
DefinesPath,Path.java(links are to index).
Tee-Puzzle Instances
A straight-forward implementation of an instance of the tee puzzle.
<TeePuzzleInstance.java>=
import java.util.Set
import java.util.HashSet
class
TeePuzzleInstance
/**
Add a peg to this tee-puzzle instance.
peg: The peg to add.
*/
private void
add(TeePuzzle.Coordinate peg)
assert (0 ≤ peg.x) : "0 <= peg.x = " + peg.x + " failed"
assert (0 ≤ peg.y) : "0 <= peg.y = " + peg.y + " failed"
assert peg.x + peg.y < holesPerSide
: peg.x + " + " + peg.y + " < " + holesPerSide + " failed"
assert !pegs.contains(peg) : "!pegs.contains(" + peg + ") failed"
pegs.add(peg)
/**
Find the move that created this tee-puzzle instance.
Returns: The move that created this tee-puzzle instance.
*/
TeePuzzle.Jump
creatorJump()
return move
/**
Determine if this tee-puzzle instance is a solution.
Returns: true iff this tee-puzzle instance is a solution.
*/
boolean
isGoalState()
return pegs.size() ≡ 1
/**
Find pegs suitable for jumping.
jumpingPeg: The peg that will be doing the jumping.
Returns: The set of pegs adjacent to the given peg that are suitable for
jumping by the given peg; that is, the adjacent pegs that have empty holes
on the side opposite the jumping peg.
*/
private Set<TeePuzzle.Coordinate>
jumpablePegs(TeePuzzle.Coordinate jumpingPeg)
final Set<TeePuzzle.Coordinate> jumpable =
new HashSet<TeePuzzle.Coordinate>()
final int
deltaXs [] = new int [] { -1, 0, -1, 1, 0, 1 },
deltaYs [] = new int [] { 1, 1, 0, 0, -1, -1 }
for int i = 0; i < deltaXs.length; ++i
final int
deltaX = deltaXs[i],
deltaY = deltaYs[i]
final TeePuzzle.Coordinate jumped =
new TeePuzzle.Coordinate(jumpingPeg.x + deltaX, jumpingPeg.y + deltaY)
if pegs.contains(jumped)
final int
landingX = jumpingPeg.x + 2*deltaX,
landingY = jumpingPeg.y + 2*deltaY
if (0 ≤ landingX
∧ (0 ≤ landingY)
∧ (landingX + landingY < holesPerSide))
if !pegs.contains(new TeePuzzle.Coordinate(landingX, landingY))
jumpable.add(jumped)
return jumpable
/**
Make a move in this tee-puzzle instance.
jumpingPeg: The peg making the jump.
jumpedPeg: The peg being jumped.
Returns: The tee-puzzle instance resulting fron the move.
*/
private TeePuzzleInstance
jumpPeg(TeePuzzle.Coordinate jumpingPeg, TeePuzzle.Coordinate jumpedPeg)
return new TeePuzzleInstance(this, jumpingPeg, jumpedPeg)
/**
Find this tee-puzzle instance's children.
Returns: The set of tee-puzzle instances that result from legal moves made
in this instance.
*/
Set<TeePuzzleInstance>
neighbors()
final Set<TeePuzzleInstance> children = new HashSet<TeePuzzleInstance>()
for TeePuzzle.Coordinate jumping : pegs
for TeePuzzle.Coordinate jumped : jumpablePegs(jumping)
children.add(jumpPeg(jumping, jumped))
return children
/**
Remove a peg from this tee-puzzle instance.
peg: The peg to remove.
*/
private void
remove(TeePuzzle.Coordinate peg)
assert pegs.contains(peg) : "pegs.contains(" + peg + ") failed"
pegs.remove(peg)
/**
Create a new tee-puzzle instance.
size: The number of holes on a side of the puzzle.
holes: Which holes in the puzzle are empty; all others are assumed
to contain pegs.
*/
TeePuzzleInstance(int size, TeePuzzle.Coordinate holes[])
assert size > 0 : size + " > 0 failed"
move = null
holesPerSide = size
pegs = new HashSet<TeePuzzle.Coordinate>()
for int x = 0; x < size; ++x
for int y = 0 ; y < size - x; ++y
add(new TeePuzzle.Coordinate(x, y))
for TeePuzzle.Coordinate hole : holes
remove(hole)
/**
Create a new tee-puzzle instance by making a move on an old tee-puzzle
instance.
parent: The tee-puzzle instance within which the jump is being made.
jumpingPeg: The peg that is doing the jumping.
jumpedPeg: The peg that is being jumped and removed from the puzzle.
*/
private
TeePuzzleInstance(
TeePuzzleInstance parent,
TeePuzzle.Coordinate jumpingPeg,
TeePuzzle.Coordinate jumpedPeg)
holesPerSide = parent.holesPerSide
pegs = new HashSet<TeePuzzle.Coordinate>(parent.pegs)
final TeePuzzle.Coordinate newPeg =
new TeePuzzle.Coordinate(
jumpedPeg.x + (jumpedPeg.x - jumpingPeg.x),
jumpedPeg.y + (jumpedPeg.y - jumpingPeg.y))
move = new TeePuzzle.Jump(jumpingPeg, newPeg)
remove(jumpingPeg)
remove(jumpedPeg)
add(newPeg)
@Override
public String
toString()
final StringBuffer stringBuffer = new StringBuffer()
for int y = holesPerSide - 1; -1 < y ; --y
for int i = 0; i < y; ++i
stringBuffer.append(" ")
for int x = 0; x < holesPerSide - y; ++x
final TeePuzzle.Coordinate hole = new TeePuzzle.Coordinate(x, y)
stringBuffer.append(pegs.contains(hole) ? " *" : " o")
stringBuffer.append("\n")
return stringBuffer.toString()
/**
The move that created this tee-puzzle instance.
*/
private final TeePuzzle.Jump move
/**
The tee-puzzle instance size.
*/
private final int holesPerSide
/**
The holes in this tee-puzzle instance that contain pegs.
*/
private final Set<TeePuzzle.Coordinate> pegs
DefinesTeePuzzleInstance,TeePuzzleInstance.java(links are to index).