sliding tile puzzle

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

sliding tile puzzle

  • 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

2 2 sliding tile puzzle

2x2 sliding tile states
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

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

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

Dijstra's single source shortest path algm

A*

  • 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

  • intro redblobgames Amit Patel

  • Welling example

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

a weighted digraph D

A* example: Arad to Bucharest (above example)
      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)

A* sliding tile

  • 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

also