Python Error Adding Node() To Priority Queue

I am coding an A* algorithm (using the Misplaced Tiles heuristic) to solve the 8 puzzle problem. When I try to add a Node() object to the priority queue it gives me a error of 'Typ

Solution 1:

I'd guess that you're pushing two nodes with the same priority. Since your PriorityQueue items are priority, Node tuples, a comparison of the tuple will first check the priority, and only if they are equal will it compare the Nodes.

A fix for this is to provide an additional tie-breaking value in the tuple. A steadily increasing counter is a common tie breaker (but consider a descreasing number if you want newer nodes to sort before older ones):

myPQ = queue.PriorityQueue()
count = 0

# later, when you add to the queue:
myPQ.put((priority_num, count, newChild))
count += 1

If you don't want to be manually incrementing the counter, you could use itertools.count which gives an infinite generator of increasing values. just use count = itertools.count() and then next(count) whenever you need a new value.

One final note: You're using the PriorityQueue class from the queue module. That module is designed for inter-thread communication, not really for general purpose data structures. It will be doing a bunch of locking stuff that you really don't care about. A better way is to use the heapq module to make a priority queue out of a list:

import heapq

# create the queue (a regular list)
my_queue = []

# push to the queue
heapq.heappush(my_queue, (priority, tie_breaker, value))

# pop from the queue
result_priority, _, result_value = heapq.heappop(my_queue)