Martin Gardner SciAm Aug 1957 Sam Loyd, America's Greatest Puzzlist
15-puzzle dates from 1880, inventor Chapman, not Sam Loyd
MG book 5 Klein bottle, op-art and sliding block puzzles chapter 20
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
rip paper, make cells 1 2 3 4 5 goal state 1 2 3 4 5 solve from this? 5 4 3 2 1 solve from this? 4 2 5 1 3 solve from this? 4 2 5 3 1
observe: on 2x2, a slide is a rotation goal state 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 (nodes and) 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
how can we predict runtime on larger size inputs?
use 3x3 runtime data to estimate 2x5 runtime data
eg. st.33.4no: 181440 iterations 2.2 sec 82600 itn/sec
average degree in 3x3 tile search space?
4/9 of positions have empty tile in corner, so 2 nbrs
4/9 of position have empty tile middle-edge, so 3 nbrs
1/9 of positions have empty tile in center, so 4 nbrs
so average degree is 2 * 4/9 + 3 * 4/9 + 4 * 1/9 = 24/9 = 2 2/3 = 2.67
so number of edges in 3x3-tile search space equals 9! * 2.67 /2 (we counted each edge 2 times)
show number of edges in 2x5-tile search space equals 10! * 2.6
so we expect worst-case (no solution) runtime for 2x5-tile search to take about 10 * 2.6 / 2.67 = 9.75 times as long
1814400 iterations 21.5 seconds 84400 itn/s
experimental ratio close to what was expected,
how long to solve 4x4 tile puzzle?
to get a lower bound, just compare sizes of search spaces
4x4 search space 16 * 15 * 14 * 13 * 12 * 11 = R times size of 2x5 search space
so expect 4x4 no-solution runtime at least R * 21.5 seconds = about 2.3 years
bfs takes too long to solve 4x4: we need a faster algorithm
algorithm that explores search space in best-first order ?
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
solves single source shortest path on weighted graphs
weighted graph each edge has a weight (or cost, or length)
greedy: at each step remove fringe node with min distance-so-far
optimal on graphs (or acyclic digraphs) with non-negative edge weights: d-s-f of fringe node with min d-s-f is length of shortest path from start to that node
efficient Dijkstra implementation uses priority queue: PQ.remove() returns node with max priority (here, min distance-so-far)
solves single-source single-target problem
A* uses heuristic to estimate remaining dist to 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 #cost[v] will be min dist-so-far from start to v #if heuristic(target, v) is always less/equal than min dist(target,v), #then final cost[v] will be min dist from start to v 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 (easy to compute using latitute/longitude coordinates) A C D F L M O P R S T Z 366 160 242 176 244 241 380 100 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)
how can we use A* for sliding tile problem?
usual state space adjacency graph
node: sliding tile state (position)
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 Manhattan distance (a.k.a. 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 sliding_tile A*
now type help
humans and computers often solve problems differently
solve 2x3 sliding tile puzzle by reducing it to a 2x2 puzzle
consider any 2x3 puzzle with tiles 1-5
claim A: we can always get to position with numbers in left column correct (1, 4)
claim B: after getting to that position, original problem solvable if and only if solving remaining 2x2 problem (while leaving left column in place) solvable
get to 1 * * [ how ? ] * * now where is 4? two cases case 1: 1 * * done :) 4 * case 2: 1 * * 1 4 * 1 * 4 * 4 * * * * in each of these cases 1 * * get to this * 4 then ... * * ... * * * ... 1 * * 1 * 4 1 4 4 * end of proof :)
each tile move preserves the solvability condition
e.g. assume number of rows is odd
solvability condition: number of inversions is even
each tile move preserves parity of number of inversions (why?)
so original 2x3 position solvable if and only if position with 1,4 in place solvable
two cases
case: clockwise cyclic order of other three tiles is (2,3,5)
subproblem solvable (why?), original position solvable (why?), original position had even number of inversions (why?)
case: clockwise cyclic order of other three tiles is (2,5,3)
subproblem unsolvable (why?), original position has odd number inversions (why?) so unsolvable
open problem: linear time?