1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/8puzzle.py	Thu May 26 23:26:48 2011 +0200
     1.3 @@ -0,0 +1,112 @@
     1.4 +"""
     1.5 +Name: A* on 8 puzzle
     1.6 +Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>
     1.7 +"""
     1.8 +import heapq
     1.9 +
    1.10 +def main():    
    1.11 +    goal = (1, 2, 3, 
    1.12 +            8, 0, 4, 
    1.13 +            7, 6, 5)
    1.14 +    init = (2, 8, 3, 
    1.15 +            1, 6, 4, 
    1.16 +            7, 0, 5)
    1.17 +    print "heuristic: none"
    1.18 +    search(init, goal, Heuristic(goal))
    1.19 +    print "\nheuristic: misplaced tiles"
    1.20 +    search(init, goal, MisplacedTiles(goal))
    1.21 +    print "\nheuristic: manhattan distance"
    1.22 +    search(init, goal, ManhattanDist(goal))
    1.23 +
    1.24 +def search(init, goal, h): 
    1.25 +    frontier = []
    1.26 +    print init
    1.27 +    print goal
    1.28 +    heapq.heapify(frontier)
    1.29 +    node = Node(init, None, 0, 0)
    1.30 +    heapq.heappush(frontier, (0, node))
    1.31 +    explored = set()   
    1.32 +    while len(frontier):
    1.33 +        k, node = heapq.heappop(frontier)
    1.34 +        print k
    1.35 +        explored.add(node.state) 
    1.36 +        if node.state == goal:
    1.37 +            print "goal found in %i steps" % len(explored)
    1.38 +            break         
    1.39 +        for child in expand(node, h):  
    1.40 +            #print child
    1.41 +            #print
    1.42 +            heapq.heappush(frontier, (child.h_cost, child))
    1.43 +        
    1.44 +def expand(node, h):
    1.45 +    def swap(i1, i2):
    1.46 +        state = list(node.state)       
    1.47 +        a = state[i1]
    1.48 +        b = state[i2]
    1.49 +        state[i1] = b
    1.50 +        state[i2] = a
    1.51 +        return tuple(state)  
    1.52 +
    1.53 +    children = []
    1.54 +    cost = node.cost + 1
    1.55 +    for i, v in enumerate(node.state):
    1.56 +        if v == 0:
    1.57 +            if i > 0:
    1.58 +                s = swap(i, i-1)
    1.59 +                children.append(Node(s, node, cost,  h(s) + 1))
    1.60 +            if i < 8:
    1.61 +                s = swap(i, i+1)               
    1.62 +                children.append(Node(s, node, cost,  h(s) + 1)) 
    1.63 +            if i > 2: 
    1.64 +                s = swap(i, i-3)              
    1.65 +                children.append(Node(s, node, cost,  h(s) + 1))  
    1.66 +            if i < 6:
    1.67 +                s = swap(i, i+3)
    1.68 +                children.append(Node(s, node, cost,  h(s) + 1))             
    1.69 +    return children      
    1.70 +
    1.71 +class Node(object):
    1.72 +    def __init__(self, state, parent, cost, h_cost):
    1.73 +        self.state = state
    1.74 +        self.parent = parent
    1.75 +        self.cost = cost 
    1.76 +        self.h_cost = h_cost
    1.77 +    def __less__(self, node):
    1.78 +        return self.h_cost < node.h_cost
    1.79 +    def __str__(self):
    1.80 +        return "\n".join((str(self.state[:3]), 
    1.81 +                          str(self.state[3:6]), 
    1.82 +                          str(self.state[6:])))
    1.83 +
    1.84 +class Heuristic(object):
    1.85 +    def __init__(self, goal):
    1.86 +        self.goal = goal
    1.87 +    def __call__(self, state):
    1.88 +        return 0
    1.89 +
    1.90 +class MisplacedTiles(Heuristic):
    1.91 +   def __call__(self, state):       
    1.92 +       h = 0
    1.93 +       for i, s in enumerate(state):
    1.94 +           if self.goal[i] != s:
    1.95 +               h += 1       
    1.96 +       return h
    1.97 +
    1.98 +class ManhattanDist(Heuristic):
    1.99 +   def __call__(self, state):       
   1.100 +       h = 0
   1.101 +       for i, s in enumerate(state):
   1.102 +           for i2, s2 in enumerate(self.goal):
   1.103 +               if s == s2:
   1.104 +                   d = abs(i-i2)
   1.105 +                   h += d%3 + int(d/3)      
   1.106 +       return h
   1.107 +    
   1.108 +from argparse import ArgumentParser
   1.109 +
   1.110 +def parse_arguments():
   1.111 +    parser = ArgumentParser(description="8 puzzle")   
   1.112 +    return parser.parse_args()
   1.113 +
   1.114 +if __name__ == "__main__":
   1.115 +    main()