电弧一致性 (AC3) 和一项挑战

Question

在对一个约束满足问题应用弧一致性（AC3）算法时，如果一个变量的域为空，下一步是什么？

1) halt.
2) do backtrack.
3) start from another initial state.
4) it depends on that we are in which step.

解决方案 （4）。我认为（1）是正确的，因为这意味着我们找不到任何一致的分配和停止。任何人都可以描述为什么（4）是真的？

Answer 1

对于您正在使用的特定算法，如果变量的域收缩到为空，则意味着约束问题没有解决方案。 因此，算法应在失败状态下停止。