# jemdoc: addcss{rbh.css}, addcss{jacob.css}
= sliding tile puzzle
~~~
{}{raw}
puzzle
2 2
solv
space
exhaust
suffice
bfs
est
special
heuristic
Dij
A*
A*st
humans
also
~~~
~~~
{}{raw}
## sliding tile puzzle

~~~
~~~
- [https://en.wikipedia.org/wiki/Sliding_puzzle wiki]
- 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
- [http://www.murderousmaths.co.uk/games/loyd/loydfr.htm murderous maths loyd]
~~~
~~~
{warm up}{}
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
~~~
~~~
{}{raw}
## 2 2 sliding tile puzzle

~~~
~~~
{2x2 sliding tile states}{}
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
~~~
~~~
{}{raw}
## solvable?

~~~
~~~
{}
- 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 [https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html parity check]
tells whether an arbitrary state is solvable
~~~
~~~
{}{table}{}
column number | solvability condition ||
odd | even number inversions ||
even | blank's row-from-bottom parity != inversions parity
~~~
~~~
{examples}{}
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
~~~
~~~
{}{raw}
## search sliding tile space

~~~
~~~
{}{}
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
... ... ... ... ...
~~~
~~~
{}{raw}
## exhaustive search

~~~
~~~
{}
- 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
~~~
~~~
{}{table}{}
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
~~~
~~~
{}{raw}
## exhaustive search suffice?

~~~
~~~
{}
- 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
~~~
~~~
{}{raw}
## solving slide tile with bfs

~~~
~~~
{}
- 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
- [https://github.com/ryanbhayward/games-puzzles-algorithms/blob/master/simple/stile/stile_search.py stile_search.py]
-- my desktop: stile_search.py examines 70 000 states/s
-- 3 3 no problem
-- 4 4 intractable
- since bfs, solution found is shortest
~~~
~~~
{example 3 3 bfs diagnostics}{}
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
~~~
~~~
{}{raw}
## estimating next runtime

~~~
~~~
- 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 ?
~~~
~~~
{}{raw}
## special purpose algorithm

~~~
~~~
- 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
- [https://www.youtube.com/watch?v=NXRIrP1k4dE 4x4 example video]
~~~
~~~
{}{raw}
## heuristic search

~~~
~~~
{}
- heuristic search is guided search
- a heuristic function is used to decide which node
of the search tree to explore next
~~~
~~~
{}{raw}
## Dijkstra's single source shortest path algm

~~~
~~~
- solves *single source shortest path on weighted graphs*
- +weighted graph+ each edge has a weight (or cost, or length)
- [http://webdocs.cs.ualberta.ca/~hayward/204/jem/paths.html\#Dij D sssp]
- [https://en.wikipedia.org/wiki/Greedy_algorithm 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)
~~~
~~~
{}{raw}
## A*

~~~
~~~
- [https://en.wikipedia.org/wiki/Heuristic_(computer_science) heuristic]
- 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
- [http://www.redblobgames.com/pathfinding/a-star/introduction.html intro redblobgames Amit Patel]
- [https://www.ics.uci.edu/~welling/teaching/ICS175winter12/A-starSearch.pdf Welling example]
- [https://qiao.github.io/PathFinding.js/visual/ pathfinding viz]
~~~
~~~
{}{}
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
~~~
~~~
{}
{{}}
~~~
~~~
{A* example: Arad to Bucharest (above example)}{}
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)
~~~
~~~
{}{raw}
## A* sliding tile

~~~
~~~
- 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
[https://en.wiktionary.org/wiki/Manhattan_distance 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+
~~~
~~~
{}{raw}
## how humans solve sliding tile

~~~
~~~
- humans and computers often solve problems differently
~~~
~~~
{solving sliding tile by decomposition}
- 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
~~~
~~~
{Proof of claim A}{}
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 :)
~~~
~~~
{Proof of claim B}
- 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
~~~
~~~
{}{raw}
## also

~~~
~~~
- [https://www.cs.cmu.edu/~adamchik/15-121/labs/HW-7%20Slide%20Puzzle/lab.html cmu]
- [http://www.math.ubc.ca/~cass/courses/m308-02b/projects/grant/fifteen.html ubc 15puzzle]
- [https://cseweb.ucsd.edu/~ccalabro/essays/15_puzzle.pdf correctness]
- open problem: linear time?
~~~