class PuzzleState: closed = 0 def __init__(self, width=4, height=4, state=None, gap=-1, depth=0, parent=None): self.width = width self.height = height if state is None: state = range(width * height) self._state = tuple(state) self._gap = gap < 0 and len(state) + gap or gap self.depth = depth self.parent = parent def __cmp__(self, other): return cmp(self._state, other._state) def __hash__(self): return hash(self._state) def __str__(self): w = self.width digitsize = len('%d' % ((w * self.height) - 1)) result = '+' + ((w * (digitsize + 1)) - 1) * '-' + '+\n' pos = 0 gap = self._gap for tile in self._state: if not pos % w: result += '|' tile = tile < gap and tile + 1 or tile > gap and tile or None result += tile and ('%*d' % (digitsize, tile)) or (digitsize * ' ') pos += 1 result += (pos % w) and ' ' or '|\n' return result + '+' + ((w * (digitsize + 1)) - 1) * '-' + '+\n' def __repr__(self): state = [] g = self._gap for s in self._state: s.append(s < g and str(s + 1) or s > g and str(s) or ' ') return "" % ''.join(state) def _calculateDistance(self): distance = 0 pos = 0 w = self.width h = self.height s = self._state g = self._gap # Moving distance for tile in s: if tile != g and tile != pos: distance += abs(pos % w - tile % w) + abs(pos / w - tile / w) # Two to switch places adds another 1 distance per tile if (# this should be up and up should be this (pos / w and tile == (pos - w) and s[tile] == pos) or # this should be down and down should be this ((pos / w) < (h - 1) and tile == (pos + w) and s[tile] == pos) or # this should be left and left should be this (pos % w and tile == (pos - 1) and s[tile] == pos) or # this should be right and right should be this ((pos % w) < (w - 1) and tile == (pos + 1) and s[tile] == pos)): distance += 1 pos += 1 return distance _distance = None def getDistance(self): if self._distance is None: self._distance = self._calculateDistance() return self._distance def createChildren(self, UP=1, DOWN=2, RIGHT=4, LEFT=8): state = list(self._state) blank = state.index(self._gap) moves = UP | DOWN | LEFT | RIGHT w = self.width # Determine possible moves if not blank / w: # top row moves ^= UP elif blank / w == self.height - 1: # bottom row moves ^= DOWN if not blank % w: # left column moves ^= LEFT elif blank % w == w - 1: # right column moves ^= RIGHT # Generate new states with possible moves applied children = [] if moves & UP: new = state[:] new[blank - w], new[blank] = new[blank], new[blank - w] children.append(self.__class__(w, self.height, new, self._gap, self.depth + 1, self)) if moves & DOWN: new = state[:] new[blank + w], new[blank] = new[blank], new[blank + w] children.append(self.__class__(w, self.height, new, self._gap, self.depth + 1, self)) if moves & LEFT: new = state[:] new[blank - 1], new[blank] = new[blank], new[blank - 1] children.append(self.__class__(w, self.height, new, self._gap, self.depth + 1, self)) if moves & RIGHT: new = state[:] new[blank + 1], new[blank] = new[blank], new[blank + 1] children.append(self.__class__(w, self.height, new, self._gap, self.depth + 1, self)) return children from pqueue import PQueue def searchBestFirst(start): goal = start.__class__(start.width, start.height, gap=start._gap) open = PQueue() open.insert(start.getDistance(), start) seen = {start: start} while open: # Find lowest score and remove from open priority, current = open.pop() # Give an indication of the progress so far: # print 79 * '\r', # print "Searching, depth = %2d, f() = %2d" % (current.depth, priority), if current == goal: print "\nCreated %d states, %d states left on open." % ( len(seen), len(open)) return make_path(current, seen) children = [(c.getDistance() + c.depth, c) for c in current.createChildren()] for priority, child in children: if not seen.has_key(child): seen[child] = child open.insert(priority, child) else: oldchild = seen[child] if oldchild.depth > child.depth: if not oldchild.closed: del open[oldchild] open.insert(priority, child) else: child.closed = 1 seen[child] = child seen[current].closed = 1 print "\nSearched all %d states, through %d levels." % ( len(seen), max(map(lambda s: s.depth, seen.keys()))) return None import psyco psyco.bind(searchBestFirst) def make_path(end, seen): path = [end] while seen[path[-1]].parent: path += [seen[path[-1]].parent] path.reverse() return path def createRandomPuzzle(width=4, height=4, gap=-1): import random moves = width * height * 4 start = state = PuzzleState(width, height, gap=gap) for i in range(moves): state = random.choice(state.createChildren()) state.parent = None state.depth = 0 return state if __name__ == '__main__': size = (4, 4) # 5 by 5 gets too big. Some problems will take days to solve. start = createRandomPuzzle(*size) # Unsolvable, used for benchmarking: # start = PuzzleState(3, 3, range(6) + [7, 6, 8]) # Classic 8-puzzle with gap in middle, worst case scenario. # start = PuzzleState(3, 3, range(8, -1, -1), 4) # Resonably difficult 15 puzzle, for benchmarking # start = PuzzleState(4, 4, [4, 1, 5, 3, 6, 15, 2, 7, 12, 8, 10, 11, 0, 9, # 13, 14]) # Psyco segfault: start = PuzzleState(4, 4, [1, 4, 2, 3, 0, 6, 10, 7, 8, 12, 15, 11, 9, 5, 13, 14]) width = len(str(start).splitlines()[0]) print "Start:" + width * ' ' + "Goal:" goal = start.__class__(start.width, start.height, gap=start._gap) for line1, line2 in zip(str(start).splitlines(), str(goal).splitlines()): print line1 + ' ' + line2 print path = searchBestFirst(start) if path: print "Path:" fit = 80 / (width + 6) middle = ((start.height + 2) / 2) for startpos in range(0, len(path), fit): line = 0 elems = path[startpos:startpos + fit] for lines in apply(zip, map(lambda e: str(e).splitlines(), elems)): joiner = (line == middle) and ' -> ' or ' ' if (startpos + fit) < len(path): lines += ('',) # Print an arrow at the end if needed print joiner.join(lines) line += 1 print print "Number of steps: %d" % (len(path) - 1) else: print "No path found" # vim:ts=8:sts=4:et:sw=4:sr:tw=80