python - Lifo Queue の項目が参照せずに変更されるのはなぜですか?

Question

私はグラフの色付けの問題に取り組んでおり、各ノードが取り得る可能な色の値 (0,1,2,3) の辞書を持っています。ここでは、アルゴリズムを理解するためだけに、ちょっとした力ずくの方法を試しています。修正できない単純な問題が発生しています。基本的に、色を選択するたびに各辞書を追跡する必要があるため、うまくいかない場合はその時点まで戻ることができます。以下は、出力が間違っている場所です。これらの印刷ステートメントをすべて挿入して、問題を診断してみました。ノード 9 を色 2 に設定し、この選択に戻る必要がある場合に備えて、別の選択をキューに入れています。

9 を 2 に設定

9 のキューイング代替選択肢 (以下は、LifoQueue に追加される代替選択肢です。これがキーです)

 {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]}

次に、コードは選択を使用して、ノード 9 を 2 に設定して、事前定義されたエッジに基づいて他のノードから可能な色を排除します。

エッジ 9 ～ 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]}

エッジ 9 ～ 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]}

10 を 3 に設定 (ノード 10 のオプションは 1 つしかないため、ここでキューに入れる代わりはありません)

エッジ 10 ～ 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]}

ここで、ノード 11 のオプションが空白になっていることがわかります。これは、せいぜい、最後の選択が間違っていたことを示しているため、キューに入れられた最後の項目へのバックトラックがトリガーされます。これは、前述のように、ノード 9 の値が 3 のディクショナリでした。問題は、ここで q.get() を実行すると、これが出力されることです (上のキューに追加したものと比較してください:

 {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]}

キューに触れずにキュー エントリを変更するにはどうすればよいですか? 以下は関連するコードです。

'''

# 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')

'''