"""

Python example for this Rosetta Code task:

http://rosettacode.org/wiki/15_puzzle_solver

Using A* Algorithm from Wikkipedia:

https://en.wikipedia.org/wiki/A*_search_algorithm

Need to use heuristic that guarantees a shortest path
solution.

"""

import heapq
import copy

# Hopefully this is larger than any fscore or gscore

integer_infinity = 1000000000

class Position(object):
    """Position class represents one position of a 15 puzzle"""

    def __init__(self, tiles):
        """
        Takes a tuple of tuples representing the tiles on a 4x4 puzzle board
        numbering 1-15 with 0 representing an empty square. For example:

        (( 1,  2,  3,  4),
         ( 5,  6,  7,  8),
         ( 9, 10, 11, 12),
         (13, 14, 15,  0))

        Converts list of lists representation into tuple of tuples.
        """
        if type(tiles) == type(list()):
            t = tiles
            self.tiles = ((t[0][0], t[0][1], t[0][2], t[0][3]),
                          (t[1][0], t[1][1], t[1][2], t[1][3]),
                          (t[2][0], t[2][1], t[2][2], t[2][3]),
                          (t[3][0], t[3][1], t[3][2], t[3][3]))
        else:
            self.tiles = tiles

        # fields for A* algorithm

        self.fscore = integer_infinity
        self.gscore = integer_infinity

        self.cameFrom = None

    def copy_tiles(self):
        """ returns list of lists version """
        t = self.tiles

        return [[t[0][0], t[0][1], t[0][2], t[0][3]],
                [t[1][0], t[1][1], t[1][2], t[1][3]],
                [t[2][0], t[2][1], t[2][2], t[2][3]],
                [t[3][0], t[3][1], t[3][2], t[3][3]]]


    def neighbors(self):
        """
        returns a list of neighbors
        returns a list position objects with their
        directiontomoveto set to the direction that the
        empty square moved.

        tiles is 4x4 tuple of tuples with
        0,0 as top left.

        tiles[y][x]

        """

        # find 0 - blank square

        x0 = None
        y0 = None

        for i in range(4):
            for j in range(4):
                if self.tiles[i][j] == 0:
                    y0 = i
                    x0 = j

        if x0 == None or y0 == None:
            return []

        neighbor_list = []

        # move 0 to the right
        if x0 < 3:
            new_tiles = self.copy_tiles()
            temp = new_tiles[y0][x0+1]
            new_tiles[y0][x0+1] = 0
            new_tiles[y0][x0] = temp
            new_pos = new_position(new_tiles)
            neighbor_list.append(new_pos)
        # move 0 to the left
        if x0 > 0:
            new_tiles = self.copy_tiles()
            temp = new_tiles[y0][x0-1]
            new_tiles[y0][x0-1] = 0
            new_tiles[y0][x0] = temp
            new_pos = new_position(new_tiles)
            neighbor_list.append(new_pos)
        # move 0 up
        if y0 > 0:
            new_tiles = self.copy_tiles()
            temp = new_tiles[y0-1][x0]
            new_tiles[y0-1][x0] = 0
            new_tiles[y0][x0] = temp
            new_pos = new_position(new_tiles)
            neighbor_list.append(new_pos)
        # move 0 down
        if y0 < 3:
            new_tiles = self.copy_tiles()
            temp = new_tiles[y0+1][x0]
            new_tiles[y0+1][x0] = 0
            new_tiles[y0][x0] = temp
            new_pos = new_position(new_tiles)
            neighbor_list.append(new_pos)

        return neighbor_list

    def __repr__(self):
        # printable version of self

        return str(self.tiles[0])+'\n'+str(self.tiles[1])+'\n'+str(self.tiles[2])+'\n'+str(self.tiles[3])+'\n'

# takes tuple of tuples tiles as key, Position object for that tiles as value

all_positions = dict()

def new_position(tiles):
    """ returns a new position or looks up existing one """
    global all_positions
    if type(tiles) == type(list()):
        t = tiles
        tuptiles =   ((t[0][0], t[0][1], t[0][2], t[0][3]),
                      (t[1][0], t[1][1], t[1][2], t[1][3]),
                      (t[2][0], t[2][1], t[2][2], t[2][3]),
                      (t[3][0], t[3][1], t[3][2], t[3][3]))
    else:
        tuptiles = tiles

    if tuptiles in all_positions:
        return 	all_positions[tuptiles]
    else:
        new_pos = Position(tiles)
        all_positions[tuptiles] = new_pos
        return new_pos

def reconstruct_path(current):
    """
    Uses the cameFrom members to follow the chain of moves backwards
    and then reverses the list to get the path in the correct order.
    """
    total_path = [current]

    while current.cameFrom != None:
        current = current.cameFrom
        total_path.append(current)

    total_path.reverse()

    return total_path

class PriorityQueue(object):
    """
    Priority queue using heapq.
    elements of queue are (fscore,tiles) for each position.
    If element is removed from queue and fscore doesn't match
    then that element is discarded.
    """

    def __init__(self, object_list):
        """
        Save a list in a heapq.
        Assume that each object only appears once
        in the list.
        """
        self.queue_length = 0
        self.qheap = []
        for e in object_list:
            self.qheap.append((e.fscore,e.tiles))
            self.queue_length += 1
        heapq.heapify(self.qheap)

    def push(self, new_object):
        """ save object in heapq """
        heapq.heappush(self.qheap,(new_object.fscore,new_object.tiles))
        self.queue_length += 1

    def pop(self):
        """ remove object from heap and return """
        if self.queue_length < 1:
            return None
        fscore, tiles = heapq.heappop(self.qheap)
        self.queue_length -= 1
        global all_positions
        pos = all_positions[tiles]
        if pos.fscore == fscore:
            return pos
        else:
            return self.pop()

    def __repr__(self):
        # printable version of self
        strrep = ""
        for e in self.qheap:
          fscore, tiles = e
          strrep += str(fscore)+":"+str(tiles)+"\n"

        return strrep

conflict_table = None

def build_conflict_table():
    global conflict_table
    conflict_table = dict()

    # assumes goal tuple has up to
    # for the given pattern it the start position
    # how much to add for linear conflicts
    # 2 per conflict - max of 6

    # goal tuple is ('g0', 'g1', 'g2', 'g3')

    conflict_table[('g0', 'g1', 'g2', 'g3')] = 0
    conflict_table[('g0', 'g1', 'g2', 'x')] = 0
    conflict_table[('g0', 'g1', 'g3', 'g2')] = 2
    conflict_table[('g0', 'g1', 'g3', 'x')] = 0
    conflict_table[('g0', 'g1', 'x', 'g2')] = 0
    conflict_table[('g0', 'g1', 'x', 'g3')] = 0
    conflict_table[('g0', 'g1', 'x', 'x')] = 0
    conflict_table[('g0', 'g2', 'g1', 'g3')] = 2
    conflict_table[('g0', 'g2', 'g1', 'x')] = 2
    conflict_table[('g0', 'g2', 'g3', 'g1')] = 4
    conflict_table[('g0', 'g2', 'g3', 'x')] = 0
    conflict_table[('g0', 'g2', 'x', 'g1')] = 2
    conflict_table[('g0', 'g2', 'x', 'g3')] = 0
    conflict_table[('g0', 'g2', 'x', 'x')] = 0
    conflict_table[('g0', 'g3', 'g1', 'g2')] = 4
    conflict_table[('g0', 'g3', 'g1', 'x')] = 2
    conflict_table[('g0', 'g3', 'g2', 'g1')] = 4
    conflict_table[('g0', 'g3', 'g2', 'x')] = 2
    conflict_table[('g0', 'g3', 'x', 'g1')] = 2
    conflict_table[('g0', 'g3', 'x', 'g2')] = 2
    conflict_table[('g0', 'g3', 'x', 'x')] = 0
    conflict_table[('g0', 'x', 'g1', 'g2')] = 0
    conflict_table[('g0', 'x', 'g1', 'g3')] = 0
    conflict_table[('g0', 'x', 'g1', 'x')] = 0
    conflict_table[('g0', 'x', 'g2', 'g1')] = 2
    conflict_table[('g0', 'x', 'g2', 'g3')] = 0
    conflict_table[('g0', 'x', 'g2', 'x')] = 0
    conflict_table[('g0', 'x', 'g3', 'g1')] = 2
    conflict_table[('g0', 'x', 'g3', 'g2')] = 2
    conflict_table[('g0', 'x', 'g3', 'x')] = 0
    conflict_table[('g0', 'x', 'x', 'g1')] = 0
    conflict_table[('g0', 'x', 'x', 'g2')] = 0
    conflict_table[('g0', 'x', 'x', 'g3')] = 0
    conflict_table[('g1', 'g0', 'g2', 'g3')] = 2
    conflict_table[('g1', 'g0', 'g2', 'x')] = 2
    conflict_table[('g1', 'g0', 'g3', 'g2')] = 4
    conflict_table[('g1', 'g0', 'g3', 'x')] = 2
    conflict_table[('g1', 'g0', 'x', 'g2')] = 2
    conflict_table[('g1', 'g0', 'x', 'g3')] = 2
    conflict_table[('g1', 'g0', 'x', 'x')] = 2
    conflict_table[('g1', 'g2', 'g0', 'g3')] = 4
    conflict_table[('g1', 'g2', 'g0', 'x')] = 4
    conflict_table[('g1', 'g2', 'g3', 'g0')] = 6
    conflict_table[('g1', 'g2', 'g3', 'x')] = 0
    conflict_table[('g1', 'g2', 'x', 'g0')] = 4
    conflict_table[('g1', 'g2', 'x', 'g3')] = 0
    conflict_table[('g1', 'g2', 'x', 'x')] = 0
    conflict_table[('g1', 'g3', 'g0', 'g2')] = 4
    conflict_table[('g1', 'g3', 'g0', 'x')] = 4
    conflict_table[('g1', 'g3', 'g2', 'g0')] = 6
    conflict_table[('g1', 'g3', 'g2', 'x')] = 0
    conflict_table[('g1', 'g3', 'x', 'g0')] = 4
    conflict_table[('g1', 'g3', 'x', 'g2')] = 2
    conflict_table[('g1', 'g3', 'x', 'x')] = 0
    conflict_table[('g1', 'x', 'g0', 'g2')] = 2
    conflict_table[('g1', 'x', 'g0', 'g3')] = 2
    conflict_table[('g1', 'x', 'g0', 'x')] = 2
    conflict_table[('g1', 'x', 'g2', 'g0')] = 4
    conflict_table[('g1', 'x', 'g2', 'g3')] = 0
    conflict_table[('g1', 'x', 'g2', 'x')] = 0
    conflict_table[('g1', 'x', 'g3', 'g0')] = 4
    conflict_table[('g1', 'x', 'g3', 'g2')] = 2
    conflict_table[('g1', 'x', 'g3', 'x')] = 0
    conflict_table[('g1', 'x', 'x', 'g0')] = 2
    conflict_table[('g1', 'x', 'x', 'g2')] = 0
    conflict_table[('g1', 'x', 'x', 'g3')] = 0
    conflict_table[('g2', 'g0', 'g1', 'g3')] = 4
    conflict_table[('g2', 'g0', 'g1', 'x')] = 4
    conflict_table[('g2', 'g0', 'g3', 'g1')] = 4
    conflict_table[('g2', 'g0', 'g3', 'x')] = 2
    conflict_table[('g2', 'g0', 'x', 'g1')] = 4
    conflict_table[('g2', 'g0', 'x', 'g3')] = 2
    conflict_table[('g2', 'g0', 'x', 'x')] = 2
    conflict_table[('g2', 'g1', 'g0', 'g3')] = 4
    conflict_table[('g2', 'g1', 'g0', 'x')] = 4
    conflict_table[('g2', 'g1', 'g3', 'g0')] = 6
    conflict_table[('g2', 'g1', 'g3', 'x')] = 2
    conflict_table[('g2', 'g1', 'x', 'g0')] = 4
    conflict_table[('g2', 'g1', 'x', 'g3')] = 2
    conflict_table[('g2', 'g1', 'x', 'x')] = 2
    conflict_table[('g2', 'g3', 'g0', 'g1')] = 4
    conflict_table[('g2', 'g3', 'g0', 'x')] = 4
    conflict_table[('g2', 'g3', 'g1', 'g0')] = 6
    conflict_table[('g2', 'g3', 'g1', 'x')] = 4
    conflict_table[('g2', 'g3', 'x', 'g0')] = 4
    conflict_table[('g2', 'g3', 'x', 'g1')] = 4
    conflict_table[('g2', 'g3', 'x', 'x')] = 0
    conflict_table[('g2', 'x', 'g0', 'g1')] = 4
    conflict_table[('g2', 'x', 'g0', 'g3')] = 2
    conflict_table[('g2', 'x', 'g0', 'x')] = 2
    conflict_table[('g2', 'x', 'g1', 'g0')] = 4
    conflict_table[('g2', 'x', 'g1', 'g3')] = 2
    conflict_table[('g2', 'x', 'g1', 'x')] = 2
    conflict_table[('g2', 'x', 'g3', 'g0')] = 4
    conflict_table[('g2', 'x', 'g3', 'g1')] = 4
    conflict_table[('g2', 'x', 'g3', 'x')] = 0
    conflict_table[('g2', 'x', 'x', 'g0')] = 2
    conflict_table[('g2', 'x', 'x', 'g1')] = 2
    conflict_table[('g2', 'x', 'x', 'g3')] = 0
    conflict_table[('g3', 'g0', 'g1', 'g2')] = 6
    conflict_table[('g3', 'g0', 'g1', 'x')] = 4
    conflict_table[('g3', 'g0', 'g2', 'g1')] = 6
    conflict_table[('g3', 'g0', 'g2', 'x')] = 4
    conflict_table[('g3', 'g0', 'x', 'g1')] = 4
    conflict_table[('g3', 'g0', 'x', 'g2')] = 4
    conflict_table[('g3', 'g0', 'x', 'x')] = 2
    conflict_table[('g3', 'g1', 'g0', 'g2')] = 6
    conflict_table[('g3', 'g1', 'g0', 'x')] = 4
    conflict_table[('g3', 'g1', 'g2', 'g0')] = 6
    conflict_table[('g3', 'g1', 'g2', 'x')] = 4
    conflict_table[('g3', 'g1', 'x', 'g0')] = 4
    conflict_table[('g3', 'g1', 'x', 'g2')] = 4
    conflict_table[('g3', 'g1', 'x', 'x')] = 2
    conflict_table[('g3', 'g2', 'g0', 'g1')] = 6
    conflict_table[('g3', 'g2', 'g0', 'x')] = 4
    conflict_table[('g3', 'g2', 'g1', 'g0')] = 6
    conflict_table[('g3', 'g2', 'g1', 'x')] = 4
    conflict_table[('g3', 'g2', 'x', 'g0')] = 4
    conflict_table[('g3', 'g2', 'x', 'g1')] = 4
    conflict_table[('g3', 'g2', 'x', 'x')] = 2
    conflict_table[('g3', 'x', 'g0', 'g1')] = 4
    conflict_table[('g3', 'x', 'g0', 'g2')] = 4
    conflict_table[('g3', 'x', 'g0', 'x')] = 2
    conflict_table[('g3', 'x', 'g1', 'g0')] = 4
    conflict_table[('g3', 'x', 'g1', 'g2')] = 4
    conflict_table[('g3', 'x', 'g1', 'x')] = 2
    conflict_table[('g3', 'x', 'g2', 'g0')] = 4
    conflict_table[('g3', 'x', 'g2', 'g1')] = 4
    conflict_table[('g3', 'x', 'g2', 'x')] = 2
    conflict_table[('g3', 'x', 'x', 'g0')] = 2
    conflict_table[('g3', 'x', 'x', 'g1')] = 2
    conflict_table[('g3', 'x', 'x', 'g2')] = 2
    conflict_table[('x', 'g0', 'g1', 'g2')] = 0
    conflict_table[('x', 'g0', 'g1', 'g3')] = 0
    conflict_table[('x', 'g0', 'g1', 'x')] = 0
    conflict_table[('x', 'g0', 'g2', 'g1')] = 2
    conflict_table[('x', 'g0', 'g2', 'g3')] = 0
    conflict_table[('x', 'g0', 'g2', 'x')] = 0
    conflict_table[('x', 'g0', 'g3', 'g1')] = 2
    conflict_table[('x', 'g0', 'g3', 'g2')] = 2
    conflict_table[('x', 'g0', 'g3', 'x')] = 0
    conflict_table[('x', 'g0', 'x', 'g1')] = 0
    conflict_table[('x', 'g0', 'x', 'g2')] = 0
    conflict_table[('x', 'g0', 'x', 'g3')] = 0
    conflict_table[('x', 'g1', 'g0', 'g2')] = 2
    conflict_table[('x', 'g1', 'g0', 'g3')] = 2
    conflict_table[('x', 'g1', 'g0', 'x')] = 2
    conflict_table[('x', 'g1', 'g2', 'g0')] = 4
    conflict_table[('x', 'g1', 'g2', 'g3')] = 0
    conflict_table[('x', 'g1', 'g2', 'x')] = 0
    conflict_table[('x', 'g1', 'g3', 'g0')] = 4
    conflict_table[('x', 'g1', 'g3', 'g2')] = 2
    conflict_table[('x', 'g1', 'g3', 'x')] = 0
    conflict_table[('x', 'g1', 'x', 'g0')] = 2
    conflict_table[('x', 'g1', 'x', 'g2')] = 0
    conflict_table[('x', 'g1', 'x', 'g3')] = 0
    conflict_table[('x', 'g2', 'g0', 'g1')] = 4
    conflict_table[('x', 'g2', 'g0', 'g3')] = 2
    conflict_table[('x', 'g2', 'g0', 'x')] = 2
    conflict_table[('x', 'g2', 'g1', 'g0')] = 4
    conflict_table[('x', 'g2', 'g1', 'g3')] = 2
    conflict_table[('x', 'g2', 'g1', 'x')] = 2
    conflict_table[('x', 'g2', 'g3', 'g0')] = 4
    conflict_table[('x', 'g2', 'g3', 'g1')] = 4
    conflict_table[('x', 'g2', 'g3', 'x')] = 0
    conflict_table[('x', 'g2', 'x', 'g0')] = 2
    conflict_table[('x', 'g2', 'x', 'g1')] = 2
    conflict_table[('x', 'g2', 'x', 'g3')] = 0
    conflict_table[('x', 'g3', 'g0', 'g1')] = 4
    conflict_table[('x', 'g3', 'g0', 'g2')] = 4
    conflict_table[('x', 'g3', 'g0', 'x')] = 2
    conflict_table[('x', 'g3', 'g1', 'g0')] = 4
    conflict_table[('x', 'g3', 'g1', 'g2')] = 4
    conflict_table[('x', 'g3', 'g1', 'x')] = 2
    conflict_table[('x', 'g3', 'g2', 'g0')] = 4
    conflict_table[('x', 'g3', 'g2', 'g1')] = 4
    conflict_table[('x', 'g3', 'g2', 'x')] = 2
    conflict_table[('x', 'g3', 'x', 'g0')] = 2
    conflict_table[('x', 'g3', 'x', 'g1')] = 2
    conflict_table[('x', 'g3', 'x', 'g2')] = 2
    conflict_table[('x', 'x', 'g0', 'g1')] = 0
    conflict_table[('x', 'x', 'g0', 'g2')] = 0
    conflict_table[('x', 'x', 'g0', 'g3')] = 0
    conflict_table[('x', 'x', 'g1', 'g0')] = 2
    conflict_table[('x', 'x', 'g1', 'g2')] = 0
    conflict_table[('x', 'x', 'g1', 'g3')] = 0
    conflict_table[('x', 'x', 'g2', 'g0')] = 2
    conflict_table[('x', 'x', 'g2', 'g1')] = 2
    conflict_table[('x', 'x', 'g2', 'g3')] = 0
    conflict_table[('x', 'x', 'g3', 'g0')] = 2
    conflict_table[('x', 'x', 'g3', 'g1')] = 2
    conflict_table[('x', 'x', 'g3', 'g2')] = 2

def linear_conflicts(start_list,goal_list):
    """
    calculates number of moves to add to the estimate of
    the moves to get from start to goal based on the number
    of conflicts on a given row or column. start_list
    represents the current location and goal_list represnts
    the final goal.
    """

    # Find which of the tiles in start_list have their goals on this line
    # build a pattern to use in a lookup table of this form:
    # g0, g1, g3, g3 fill in x where there is no goal for this line

    # all 'x' until we file a tile whose goal is in this line

    goal_pattern = ['x', 'x', 'x', 'x']

    for g in range(4):
        for s in range(4):
            start_tile_num = start_list[s]
            if start_tile_num == goal_list[g] and start_tile_num != 0:
                goal_pattern[s] = 'g' + str(g) # i.e. g0

    global conflict_table

    tup_goal_pattern = tuple(goal_pattern)

    if tup_goal_pattern in conflict_table:
        return conflict_table[tuple(goal_pattern)]
    else:
        return 0

class lcmap(dict):
    """
    Lets you return 0 if you look for an object that
    is not in the dictionary.
    """
    def __missing__(self, key):
        return 0

def listconflicts(goal_list):
    """
    list all possible start lists that will have at least
    one linear conflict.

    Possible goal tile configurations

    g g g g
    g g g x
    g g x g
    g x g g
    x g g g
    g g x x
    g x g x
    g x x g
    x g g x
    x g x g
    x x g g

    """

    all_tiles = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

    non_goal_tiles = []

    for t in all_tiles:
        if t not in goal_list:
            non_goal_tiles.append(t)

    combinations = lcmap()

    # g g g g

    for i in goal_list:
        tile_list2 = goal_list[:]
        tile_list2.remove(i)
        for j in tile_list2:
            tile_list3 = tile_list2[:]
            tile_list3.remove(j)
            for k in tile_list3:
                tile_list4 = tile_list3[:]
                tile_list4.remove(k)
                for l in tile_list4:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # g g g x

    for i in goal_list:
        tile_list2 = goal_list[:]
        tile_list2.remove(i)
        for j in tile_list2:
            tile_list3 = tile_list2[:]
            tile_list3.remove(j)
            for k in tile_list3:
                for l in non_goal_tiles:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # g g x g

    for i in goal_list:
        tile_list2 = goal_list[:]
        tile_list2.remove(i)
        for j in tile_list2:
            tile_list3 = tile_list2[:]
            tile_list3.remove(j)
            for k in non_goal_tiles:
                for l in tile_list3:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd
    # g x g g

    for i in goal_list:
        tile_list2 = goal_list[:]
        tile_list2.remove(i)
        for j in non_goal_tiles:
            for k in tile_list2:
                tile_list3 = tile_list2[:]
                tile_list3.remove(k)
                for l in tile_list3:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # x g g g

    for i in non_goal_tiles:
        for j in goal_list:
            tile_list2 = goal_list[:]
            tile_list2.remove(j)
            for k in tile_list2:
                tile_list3 = tile_list2[:]
                tile_list3.remove(k)
                for l in tile_list3:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # g g x x

    for i in goal_list:
        tile_list2 = goal_list[:]
        tile_list2.remove(i)
        for j in tile_list2:
            tile_list3 = tile_list2[:]
            tile_list3.remove(j)
            for k in non_goal_tiles:
                tile_list4 = non_goal_tiles[:]
                tile_list4.remove(k)
                for l in tile_list4:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # g x g x

    for i in goal_list:
        tile_list2 = goal_list[:]
        tile_list2.remove(i)
        for j in non_goal_tiles:
            tile_list3 = non_goal_tiles[:]
            tile_list3.remove(j)
            for k in tile_list2:
                for l in tile_list3:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # g x x g

    for i in goal_list:
        tile_list2 = goal_list[:]
        tile_list2.remove(i)
        for j in non_goal_tiles:
            tile_list3 = non_goal_tiles[:]
            tile_list3.remove(j)
            for k in tile_list2:
                for l in tile_list3:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # x g g x

    for i in non_goal_tiles:
        tile_list2 = non_goal_tiles[:]
        tile_list2.remove(i)
        for j in goal_list:
            tile_list3 = goal_list[:]
            tile_list3.remove(j)
            for k in tile_list3:
                for l in tile_list2:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # x g x g

    for i in non_goal_tiles:
        tile_list2 = non_goal_tiles[:]
        tile_list2.remove(i)
        for j in goal_list:
            tile_list3 = goal_list[:]
            tile_list3.remove(j)
            for k in tile_list3:
                for l in tile_list2:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    # x x g g

    for i in non_goal_tiles:
        tile_list2 = non_goal_tiles[:]
        tile_list2.remove(i)
        for j in tile_list2:
            for k in goal_list:
                tile_list3 = goal_list[:]
                tile_list3.remove(k)
                for l in tile_list3:
                    start_list = (i, j, k, l)
                    conflictadd = linear_conflicts(start_list,goal_list)
                    if conflictadd > 0:
                        combinations[start_list]=conflictadd

    return combinations


class HeuristicObj(object):
    """ Object used to preprocess goal position for heuristic function """

    def __init__(self, goal):
        """
        Preprocess goal position to setup internal data structures
        that can be used to speed up heuristic.
        """

        build_conflict_table()

        self.goal_map = []
        for i in range(16):
            self.goal_map.append(i)

        self.goal_lists = goal.tiles

        # preprocess for manhattan distance

        for row in range(4):
            for col in range(4):
                self.goal_map[goal.tiles[row][col]] = (row, col)

        # make access faster by changing to a tuple

        self.goal_map = tuple(self.goal_map)

        # preprocess for linear conflicts

        self.row_conflicts = []
        for row in range(4):
            t = goal.tiles[row]
            conf_dict = listconflicts([t[0],t[1],t[2],t[3]])
            self.row_conflicts.append(conf_dict)

        self.col_conflicts = []
        for col in range(4):
            col_list =[]
            for row in range(4):
                col_list.append(goal.tiles[row][col])
            conf_dict = listconflicts(col_list)
            self.col_conflicts.append(conf_dict)

    def heuristic(self, start):
        """

        Estimates the number of moves from start to goal.
        The goal was preprocessed in __init__.

        """

        distance = 0

        # local variables for instance variables

        t = start.tiles
        g = self.goal_map
        rc = self.row_conflicts
        cc = self.col_conflicts

        # calculate manhattan distance

        for row in range(4):
            for col in range(4):
                start_tilenum = t[row][col]
                if start_tilenum != 0:
                    (grow, gcol) = g[start_tilenum]
                    distance += abs(row - grow) + abs(col - gcol)

        # add linear conflicts

        for row in range(4):
            curr_row = t[row]
            distance += rc[row][curr_row]

        for col in range(4):
            col_tuple = (t[0][col], t[1][col], t[2][col], t[3][col])
            distance += cc[col][col_tuple]

        return distance

# global variable for heuristic object

hob = None

def a_star(start_tiles, goal_tiles):
    """ Based on https://en.wikipedia.org/wiki/A*_search_algorithm """

    start = new_position(start_tiles)
    goal = new_position(goal_tiles)

    # Process goal position for use in heuristic

    global hob
    hob = HeuristicObj(goal)

    # The set of currently discovered nodes that are not evaluated yet.
    # Initially, only the start node is known.
    # For the first node, the fscore is completely heuristic.

    start.fscore = hob.heuristic(start)
    openSet = PriorityQueue([start])

    # The cost of going from start to start is zero.

    start.gscore = 0

    num_popped = 0

    while openSet.queue_length > 0:
        current = openSet.pop()
        if current == None: # tried to pop but only found old fscore values
            break
        num_popped += 1
        if num_popped % 100000 == 0:
            print(str(num_popped)+" positions examined")

        if current == goal:
            return reconstruct_path(current)

        for neighbor in current.neighbors():

            # The distance from start to a neighbor
            # All nodes are 1 move from their neighbors

            tentative_gScore = current.gscore + 1

            # update gscore and fscore if this is shorter path
            # to the neighbor node

            if tentative_gScore < neighbor.gscore:
                neighbor.cameFrom = current
                neighbor.gscore = tentative_gScore
                neighbor.fscore = neighbor.gscore + hob.heuristic(neighbor)
                openSet.push(neighbor) # add to open set every time


def find_zero(tiles):
    """ file the 0 tile """
    for row in range(4):
        for col in range(4):
            if tiles[row][col] == 0:
                return (row, col)

def path_as_0_moves(path):
    """
    Takes the path which is a list of Position
    objects and outputs it as a string of rlud
    directions to match output desired by
    Rosetta Code task.
    """
    strpath = ""
    if len(path) < 1:
        return ""
    prev_pos = path[0]
    p_row, p_col = find_zero(prev_pos.tiles)
    for i in range(1,len(path)):
        curr_pos = path[i]
        c_row, c_col = find_zero(curr_pos.tiles)
        if c_row > p_row:
            strpath += 'd'
        elif c_row < p_row:
            strpath += 'u'
        elif c_col > p_col:
            strpath += 'r'
        elif c_col < p_col:
            strpath += 'l'
        # reset for next loop
        prev_pos = curr_pos
        p_row = c_row
        p_col = c_col
    return strpath