#!/usr/bin/python

from copy import deepcopy

# State

start = [[4, 3, 0], [8, 1, 5], [2, 7, 6]]
goal  = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

def locate(state, n):
    for i in range(3):
        for j in range(3):
            if state[i][j] == n:
                return i, j


# Production rules

class Rule0():
    """Move left"""
    num = 0
    
    def apply(this, state):
        x, y = locate(state, 0)
        s = deepcopy(state)
        
        s[x][y] = s[x][y - 1]
        s[x][y - 1] = 0
        
        return s
    
    def can_apply(this, state):
        x, y = locate(state, 0)
        return y > 0

class Rule1():
    """Move up"""
    num = 1
    
    def apply(this, state):
        x, y = locate(state, 0)
        s = deepcopy(state)
        
        s[x][y] = s[x - 1][y]
        s[x - 1][y] = 0
        
        return s
    
    def can_apply(this, state):
        x, y = locate(state, 0)
        return x > 0

class Rule2():
    """Move right"""
    num = 2
    
    def apply(this, state):
        x, y = locate(state, 0)
        s = deepcopy(state)
        
        s[x][y] = s[x][y + 1]
        s[x][y + 1] = 0
        
        return s
    
    def can_apply(this, state):
        x, y = locate(state, 0)
        return y < 2

class Rule3():
    """Move down"""
    num = 3
    
    def apply(this, state):
        x, y = locate(state, 0)
        s = deepcopy(state)
        
        s[x][y] = s[x + 1][y]
        s[x + 1][y] = 0
        
        return s
    
    def can_apply(this, state):
        x, y = locate(state, 0)
        return x < 2
        
rules = [Rule0(), Rule1(), Rule2(), Rule3()]


# Heuristic function

def h(state):
    d = 0
    
    for n in range(9):
        x1, y1 = locate(state, n)
        x2, y2 = locate(goal, n)
        d += abs(x1 - x2) + abs(y1 - y2)
    
    return d

# h = lambda _: 0 # Uncomment for plain DFS


# Algorithm

queue = [([], start)]
visited = [start]
steps = 0

while len(queue) > 0:
    path, state = queue[0]
    new_nodes = []

    for rule in rules:
        if rule.can_apply(state):
            n_state, n_path = rule.apply(state), path + [rule.num]

            if n_state == goal:
                print "Solution found in %d iterations:" % steps, n_path
                exit(0)

            if not any([n_state == s for s in visited]):
                new_nodes.append((n_path, n_state))
                visited.append(n_state)

    queue = sorted(new_nodes, lambda a, b: h(a[1]) - h(b[1])) + queue[1:]
    
    steps += 1

print "No solution found!"