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)

Search Strategies

• 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)?

Stupid Search

• One could build a sliding-tile puzzle solver the dumb way

• Walk the state space randomly until we run into the answer

• http://github.com/pdx-cs-ai/slider

Stop Lists

• 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

• Obvious choices:

  • Breadth-first search the state space

  • Depth-first search the state space