15-puzzle dates from 1880, inventor Chapman, not Sam Lloyd (see Martin Gardner's column) source: wiki
we consider sliding tile puzzle with various dimensions
15 puzzle has 4 rows 4 columns
assume at least 2 rows (why?), similarly at least 2 columns
on 2x2, a slide is a rotation: from a b c . solvable a b a . . a c a c a c . c . c b c b . b b . b a . c b c b c b . . b a b b a . a a . a c a c . c not solvable a c a . . a b a b a b . b . b c b c . c c . c a . b c b c b c . . c a c c a . a a . a b a b . b
for r,c each at least 2, for any fixed final state, exactly .5 of the states can be transformed into the final state (proof ?)
call a state solvable if it can be transformed into the row-by-row sorted state (with blank last)
so .5 of all states are solvable
a parity check tells whether an arbitrary state is solvable
column number | solvability condition |
odd | even number inversions |
even | blank's row-from-bottom parity != inversions parity |
5 4 3 odd number cols, 4+3+2+1=10 inversions, solvable 2 1 0 7 6 5 0 even number cols, 6+5+4+3+2+1=21 inversions, 4 3 2 1 blank in row 2 from bottom, solvable 7 6 5 4 even number cols, 6+5+4+3+2+1=21 inversions, 3 2 1 0 blank in row 1 from bottom, unsolvable
children ordered by blank-mv: U D L R 235 41* U L / \ / \ / \ 23* 235 415 4*1 L U L | / \ | / \ 2*3 2*5 235 415 431 *41 D L L R U / \ / \ | / \ / \ | 213 *23 *25 25* *35 4*5 415 431 431 241 ... ... ... ... ...
search algorithms so far random walk, bfs, dfs
each exhaustive
pro: will solve problem
con: maybe take too long
which to use?
before choosing, estimate state space size
(r,c) puzzle has (r*c)! states (why?)
state space adjacency graph has 2 components
solvable states, (rc)!/2 nodes
unsolvable states, (rc)!/2 nodes
so starting from a fixed state, worst case examine (rc)!/2 nodes
dimension | number of states |
2 2 | 4! = 24 |
2 3 | 6! = 720 |
2 4 | 8! = 40 320 |
3 3 | 9! = 362 880 |
2 5 | 10! = 3.6 e 6 |
2 6 3 4 | 12! = 4.8 e 8 |
2 7 | 14! = .87 e 11 |
3 5 | 15! = 1.3 e 12 |
4 4 | 16! = 2.1 e 13 |
random walk much slower than bfs, dfs, so ignore for this problem
bfs and dfs each take time proportional to the number of edges in the underlying graph
e.g. if on a graph with 1 000 000 edges bfs takes 1 hour, then on a graph with 2 000 000 edges we expect it to take about 2 hours
the sliding-tile puzzle state transition graph (nodes are states, 2 nodes are adjacent if we can slide between them) has average degree (number of neighbors) under 4, so a constant
so bfs runtime proportional to number of states
so bfs or iterative dfs (recursive dfs will probably have stack size too large) should work on 3x3
might also work for 4x4
for 4x4 there is another algorithm (A*) that works well, like bfs finds a shortest solution
for 4x4, if we do not care about shortest solution, we can use above special-purpose algorithm
because bfs finds a shortest solution, let us try a bfs approach rather than dfs
in maze traversal
we consider adjacency graph of cells
use bfs to traverse this graph
what is the associated graph with sliding tile puzzle?
each node in graph is a sliding tile state
two nodes are adjacent if can single-slide between states
with this graph, we just use bfs as before
to implement sliding tile bfs in python
how will we record, for each state, whether we have seen it?
answer: use python dictionary of parents
each time we see a new state, add it to the dictionary
we have seen a state iff it is in the dictionary
my desktop: stile_search.py examines 70 000 states/s
3 3 no problem
4 4 intractable
since bfs, solution found is shortest
simple/stile/stile_search.py, input unsolvable 3 3 no solution found 181440 iterations 2.5 seconds 72900 iterations/sec nodes by level 0 1 1 2 2 4 3 8 4 16 5 20 6 39 7 62 8 116 9 152 10 286 11 396 12 748 13 1024 14 1893 15 2512 16 4485 17 5638 18 9529 19 10878 20 16993 21 17110 22 23952 23 20224 24 24047 25 15578 26 14560 27 6274 28 3910 29 760 30 221 31 2 32 0
special purpose algorithms for sliding tile exist
no search: repeatedly find next move
need to prove correctness
usually, solution not shortest
one algorithm:
in sorted order (so, left to right, row by row) move next element into position while avoiding elements already placed
last 2 elements of each row need special technique
last 2 rows need special technique
final 2x2 grid (last 2 rows, last 2 columns) rotate into solution if and only if original state is solvable
heuristic search is guided search
a heuristic function is used to decide which node of the search tree to explore next
weighted graph each edge has a weight (or cost, or length)
Dijkstra's algorithm solves single source shortest path on weighted graphs
uses priority queue: PQ.remove() returns node with max priority
heuristic: an estimation
A* finds path from start to target on a weighted graph with the help of a heuristic that estimates the cost from a node to the target
if heuristic always less/equal actual cost, then A* finds shortest path
usually considers fewer nodes than Dijkstra
fringe = PQ() fringe.add(start, 0) parent, cost, done = {}, {}, [] parent[start], cost[start] = None, 0 while not fringe.empty(): current = fringe.remove() # min priority done.add(current) if current == target: break for next in nbrs(current): if next not in done: new_cost = cost[current] + wt(current, next) if next not in cost or new_cost < cost[next]: cost[next] = new_cost priority = new_cost + heuristic(target, next) fringe.add(next, priority) parent[next] = current
heuristic: straight line dist to B A C D F L M O P R S T Z 366 160 242 176 244 241 380 10 193 253 329 374 initialize: (other costs initially infinite) A cost 0 priority 366 * current A cost 0 --------------------------------- A nbrs: S newcost 0 + 140 T newcost 0 + 118 Z newcost 0 + 75 S T Z cost 140 118 75 heur 253 329 374 pri 393 447 449 * current S cost 140 -------------------------------- S nbrs: A done F newcost 140 + 99 239 update O newcost 140 + 151 291 update R newcost 140 + 80 220 update S T Z F O R cost 140 118 75 239 291 220 heur 253 329 374 176 380 193 pri 393 447 449 415 671 413 * current R cost 220 -------------------------------- ... (exercise: do the next step)
usual state space adjacency graph
node: sliding tile state
edge: a pair of states, can single-slide from one to other
cost of a path: sum of number of edges from start (unit-cost weights)
choice of heuristic function:
number of misplaced tiles
sum, over all tiles, of taxicab distance from current to final location
run simple/play_stile.py to see these heuristic values
each of these heuristic function always less/equal to number of moves to solve, so with A* each yields shortest solution
to execute A* sliding tile in our code base
install VM and follow instructions, or download code from github, run make in /lib
run bin/gpa_puzzles-cli -h
run bin/gpa-puzzles-cli solvable_sliding_tile A*
now type help
open problem: linear time?