## 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