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