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

Last modified: Monday, 5 October 2020, 9:21 PM