我正在研究图形着色问题，并且我有一个每个节点可以采用的可能颜色值（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 只有一个选项）
边缘 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')
'''