sliding tile puzzle

puzzle   2 2   solv   space   exhaust   suffice   bfs   est   special   heuristic   Dij   A*   A*st   humans   also  

sliding tile 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

  • 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

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

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

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

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

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

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

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

  • 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

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 ?

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

  • 4x4 example video

heuristic search

  • heuristic search is guided search

  • a heuristic function is used to decide which node of the search tree to explore next

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)

  • D sssp

  • 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)

A*

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 weighted digraph D

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)

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

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

also