Sliding Tile Puzzles
Combinatorial State Spaces
Consider a sliding tile puzzle: what is the state space?
State is particular puzzle configuration
Neighbors are states reachable by moving one tile: each state has 2-4 neighbors (corner, edge, central)
For an n × n puzzle, how many states? n^2! (Only half are reachable because parity.)
How big is this graph?
2 2.40e1 3 3.63e5 4 2.09e13 5 1.55e25 6 3.72e41 7 6.08e62
Won't be examining them all (or half of them)
Keyed off some questions
How big is the space?
Need a best solution or just a good one?
Willing to use heuristics?
Need guarantees on solution (quality, existence)?
One could build a sliding-tile puzzle solver the dumb way
Walk the state space randomly until we run into the answer
Avoid revisiting old states
Use a stop list / closed list / tabu list of states we've already visited
Actually sets, not lists, but hey
There will be a lot: memory is a problem
Sliding Tile Puzzles: Complete Search
Rather than running around randomly, want a solver that is guaranteed to
Return a shortest solution if one exists (unlike humans)
Say "no" otherwise
Given sufficient time and memory, of course
Breadth-first search the state space
Depth-first search the state space