Snippet #8330 (by Nathaniel, python)

  • #8330
Expires in: 0 minutes View Raw
  1. ''' A 8-puzzle grid is coded as a list of 3 lists of size 3, each sublist
  2. containing values from 0 to 8, 0 being the empty space'''
  3.  
  4. solved = [[1, 2, 3],
  5.          [4, 5, 6],
  6.          [7, 8, 0]]
  7.  
  8. from copy import deepcopy
  9. from collections import deque
  10.  
  11. def empty(grid):
  12.    '''Find the empty space in a grid.'''
  13.    for i in range(3):
  14.        for j in range(3):
  15.            if grid[i][j] == 0:
  16.                return (i, j)
  17.    assert False
  18.  
  19. def neighbors(grid):
  20.    '''Find the neighbors grids of a given grid.'''
  21.    (i, j) = empty(grid)
  22.    N = []
  23.    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
  24.        if 0 <= i+di <= 2 and 0 <= j+dj <= 2:
  25.            g = deepcopy(grid)
  26.            g[i+di][j+dj] = 0
  27.            g[i][j] = grid[i+di][j+dj]
  28.            N.append(g)
  29.    return N
  30.  
  31. def key(grid):
  32.    '''Convert a grid into a tuple of tuple to use an immutable key in
  33.    the hashtable.'''
  34.    return tuple(tuple(line) for line in grid)
  35.  
  36. def distance(grid):
  37.    '''Bread-First Search.'''
  38.    q = deque()
  39.    q.append(grid)
  40.    dist = {key(grid) : 0}
  41.    while len(q) > 0:
  42.        g = q.popleft()
  43.        k = key(g)
  44.        for gn in neighbors(g):
  45.            kn = key(gn)
  46.            if kn not in dist:
  47.                dist[kn] = dist[k] + 1
  48.                q.append(gn)
  49.    return dist

Reply to this snippet →

Honeypot, don't fill.
⌘+⏎ or Ctrl+⏎