Why are the items in my Lifo Queue changing without referring to them?

Question

I am working on a graph coloring problem and I have a dictionary of possible color values (0,1,2,3) each node can take. I am trying a bit of a brute force method here just to get an understanding of the algorithm. I'm running into a simple issue that I cannot correct. Basically, I need to keep track of each dictionary any time I make a color choice, so I can backtrack to that point if it doesn't end up working. Below is where the output goes wrong. I've inserted all of these print statements to try and diagnose the issue. I am setting node 9 equal to color 2, and queuing the alternative choice in case I have to backtrack to this choice.

Setting 9 equal to 2

Queuing alternative choice for 9 (below is alternative choice that is added to LifoQueue, THIS IS KEY)

 {0: [0], 1: [0], 2: [1], 3: [2], 4: [1], 5: [0], 6: [2], 7: [1], 8: [0], 9: [3], 10: [2, 3], 11: 
  [3], 12: [0, 2, 3], 13: [1, 3], 14: [0, 3], 15: [0, 3], 16: [0, 3], 17: [0, 1, 3], 18: [2, 3], 19: 
  [1, 3]}

The code then uses the choice to eliminate possible colors from other nodes based on pre-defined edges, with node 9 set as 2

Edge 9 to 10

 {0: [0], 1: [0], 2: [1], 3: [2], 4: [1], 5: [0], 6: [2], 7: [1], 8: [0], 9: [2], 10: [3], 11: [3], 
  12: [0, 2, 3], 13: [1, 3], 14: [0, 3], 15: [0, 3], 16: [0, 3], 17: [0, 1, 3], 18: [2, 3], 19: [1, 
  3]}

Edge 9 to 12

 {0: [0], 1: [0], 2: [1], 3: [2], 4: [1], 5: [0], 6: [2], 7: [1], 8: [0], 9: [2], 10: [3], 11: [3], 
  12: [0, 3], 13: [1, 3], 14: [0, 3], 15: [0, 3], 16: [0, 3], 17: [0, 1, 3], 18: [2, 3], 19: [1, 3]}

Setting 10 equal to 3 (no alternative to queue here since there was only one option for node 10)

Edge 10 to 11

 {0: [0], 1: [0], 2: [1], 3: [2], 4: [1], 5: [0], 6: [2], 7: [1], 8: [0], 9: [2], 10: [3], 11: [], 
  12: [0, 3], 13: [1, 3], 14: [0, 3], 15: [0, 3], 16: [0, 3], 17: [0, 1, 3], 18: [2, 3], 19: [1, 3]}

Here you can see than the options for node 11 are now blank, which tells me that -- at best -- the last choice I made was wrong, so this triggers backtracking to the last item put in the queue, which, as mentioned, was a dictionary with the value 3 for node 9. The problem is, when I do q.get() here, this is the output I get (COMPARE WITH WHAT I ADDED TO THE QUEUE ABOVE:

 {0: [0], 1: [0], 2: [1], 3: [2], 4: [1], 5: [0], 6: [2], 7: [1], 8: [0], 9: [3], 10: [3], 11: [], 
  12: [0, 3], 13: [1, 3], 14: [0, 3], 15: [0, 3], 16: [0, 3], 17: [0, 1, 3], 18: [2, 3], 19: [1, 3]}

How does a queue entry change without me touching the queue? Below is the relevant code.

'''

# edges are the constraint store (?)
edges = [some pre-defined list of tuples defining the edges]

# building a solution template
solution = [0]*node_count

# global constraint of four colors 
colors = [0,1,2,3]

# dictionary covering possible colors for each node
sols = {node:colors.copy() for node in range(0,node_count)}

#initiating a queue to store checkpoints for backtracking
q = queue.LifoQueue()


#placing the first entry in the queue
q.put((0,sols))

place = 0
while place < node_count:
    backtracked = False
    cursor = q.get()
    print('cursor is ', cursor)
    place = cursor[0]
    dic = cursor[1]
    val = dic[place][0]

    #any time a value is chosen from multiple, it needs to be queued
    if len(dic[place]) > 1:
        dic_copy = dic.copy()
        dic_copy[place].remove(val)
        q.put((place,dic_copy))
        
    #choosing a value
    solution[place] = val
    dic[place] = [solution[place]]
    
    print('Setting ',place,'equal to ',val)
    for edge in edges:
        if backtracked == False:
            if edge[0] == place:                
                if solution[place] in dic[edge[1]]:
                    #in case of failure, store copy
                    vals = dic[edge[1]].copy()
                    dic[edge[1]].remove(solution[place])
                    if len(dic[edge[1]]) == 0:
                        backtracked = True
                            
    if backtracked == False:
        q.put((place+1, dic))
    else:
        print('backtracking')

'''

Answer 1

Solved this using a deepcopy instead of the regular copy I was using.