# HG changeset patch
# User Eugen Sawin <sawine@me73.com>
# Date 1306445208 -7200
# Node ID 94fc07d1e2e16310cfa92787142e627fb8662d9e
# Parent  33930f88de07c244afb278bdf239a7afc9aa47e7
Added A* puzzle exercise.

diff -r 33930f88de07 -r 94fc07d1e2e1 8puzzle.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/8puzzle.py	Thu May 26 23:26:48 2011 +0200
@@ -0,0 +1,112 @@
+"""
+Name: A* on 8 puzzle
+Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>
+"""
+import heapq
+
+def main():    
+    goal = (1, 2, 3, 
+            8, 0, 4, 
+            7, 6, 5)
+    init = (2, 8, 3, 
+            1, 6, 4, 
+            7, 0, 5)
+    print "heuristic: none"
+    search(init, goal, Heuristic(goal))
+    print "\nheuristic: misplaced tiles"
+    search(init, goal, MisplacedTiles(goal))
+    print "\nheuristic: manhattan distance"
+    search(init, goal, ManhattanDist(goal))
+
+def search(init, goal, h): 
+    frontier = []
+    print init
+    print goal
+    heapq.heapify(frontier)
+    node = Node(init, None, 0, 0)
+    heapq.heappush(frontier, (0, node))
+    explored = set()   
+    while len(frontier):
+        k, node = heapq.heappop(frontier)
+        print k
+        explored.add(node.state) 
+        if node.state == goal:
+            print "goal found in %i steps" % len(explored)
+            break         
+        for child in expand(node, h):  
+            #print child
+            #print
+            heapq.heappush(frontier, (child.h_cost, child))
+        
+def expand(node, h):
+    def swap(i1, i2):
+        state = list(node.state)       
+        a = state[i1]
+        b = state[i2]
+        state[i1] = b
+        state[i2] = a
+        return tuple(state)  
+
+    children = []
+    cost = node.cost + 1
+    for i, v in enumerate(node.state):
+        if v == 0:
+            if i > 0:
+                s = swap(i, i-1)
+                children.append(Node(s, node, cost,  h(s) + 1))
+            if i < 8:
+                s = swap(i, i+1)               
+                children.append(Node(s, node, cost,  h(s) + 1)) 
+            if i > 2: 
+                s = swap(i, i-3)              
+                children.append(Node(s, node, cost,  h(s) + 1))  
+            if i < 6:
+                s = swap(i, i+3)
+                children.append(Node(s, node, cost,  h(s) + 1))             
+    return children      
+
+class Node(object):
+    def __init__(self, state, parent, cost, h_cost):
+        self.state = state
+        self.parent = parent
+        self.cost = cost 
+        self.h_cost = h_cost
+    def __less__(self, node):
+        return self.h_cost < node.h_cost
+    def __str__(self):
+        return "\n".join((str(self.state[:3]), 
+                          str(self.state[3:6]), 
+                          str(self.state[6:])))
+
+class Heuristic(object):
+    def __init__(self, goal):
+        self.goal = goal
+    def __call__(self, state):
+        return 0
+
+class MisplacedTiles(Heuristic):
+   def __call__(self, state):       
+       h = 0
+       for i, s in enumerate(state):
+           if self.goal[i] != s:
+               h += 1       
+       return h
+
+class ManhattanDist(Heuristic):
+   def __call__(self, state):       
+       h = 0
+       for i, s in enumerate(state):
+           for i2, s2 in enumerate(self.goal):
+               if s == s2:
+                   d = abs(i-i2)
+                   h += d%3 + int(d/3)      
+       return h
+    
+from argparse import ArgumentParser
+
+def parse_arguments():
+    parser = ArgumentParser(description="8 puzzle")   
+    return parser.parse_args()
+
+if __name__ == "__main__":
+    main()