NPuzzle.py

# Enter your code here. Read input from STDIN. Print output to STDOUT
class Node:
    def __init__(self,state,action):
        self.state = state
        self.action = action
        self.parent = None
        self.H = 0
        self.G = 0
    def move_cost(self,other):
        return 1
    def __eq__(self, other):
        return self.state == other.state
    def __hash__(self):
        return hash(self.state)
def row_col(i):
    return (i % k,i/k)

def manhattan(point,point2):
    return abs(point[0] - point2[0]) + abs(point[1]-point2[0])
def incorrect(m,c):
    result = 0
    for x in xrange(len(m)):
        if m[x] != c[x]:
            result += 1
    return result
def distance(m,c):
    result = 0
    idx = -1
    for x in xrange(len(c)):
        idx = c[x]
        result += manhattan(row_col(x),row_col(m.find(idx)))
    return result
    
def h_score(m,c):
    return max(distance(m,c),incorrect(m,c))

def actions(state):
    actions = [];
    idx = state.find('0')
    if idx > k - 1:
        actions.append("UP")
    if idx < k*(k-1):
        actions.append("DOWN")
    if idx % k != 0:
        actions.append("LEFT")
    if idx % k != (k - 1):
        actions.append("RIGHT")
    return actions 
def result(state,action):
    result = list(state)
    idx = result.index('0')
    tile_idx = -1
    if action == "UP": 
        tile_idx = idx - k
    elif action == "DOWN":
        tile_idx = idx + k
    elif action == "LEFT":
        tile_idx = idx - 1
    elif action == "RIGHT":
        tile_idx = idx + 1
    result[idx], result[tile_idx] = result[tile_idx], result[idx]
    return ''.join(result)
def aStar(start, goal):
    #The open and closed sets
    frontier = set()
    explored = set()
    #Current point is the starting point
    current = start
    #Add the starting point to the open set
    frontier.add(current)
    explored.add(current.state)
    #While the open set is not empty
    while frontier:
        #Find the item in the open set with the lowest G + H score
        current = min(frontier, key=lambda o:o.G + o.H)
        frontier.remove(current)
        #If it is the item we want, retrace the path and return it
        if current.state == goal:
            path = []
            while current.parent:
                path.append(current.action)
                current = current.parent
            path.append(current.action)
            return path[::-1]
        #Loop through the node's children/siblings
        for action in actions(current.state):
            state = result(current.state,action)
            #If it is already in the closed set, skip it
            if state in explored:
                continue
            explored.add(state)
            node = Node(state,action)
            #calculate the G and H score for the node
            node.G = current.G + current.move_cost(node)
            node.H = h_score(state, goal)
            #Set the parent to our current item
            node.parent = current
            #Add it to the set
            frontier.add(node)
    #Throw an exception if there is no path
    raise ValueError('No Path Found')
k = input()
m = ''
c = ''.join([str(i) for j in xrange(0,k**2,k) for i in range(j,j+k)])
for i in xrange(k):
    m += ''.join([raw_input().strip() for i in xrange(k)])

solution = aStar(Node(m,None),c)[1:]
print len(solution)
print '\n'.join(solution)