python - 解决不平等数独的策略？

Question

我最近遇到的经典数独求解器的一个转折是（相当疯狂的）不等式数独，这是你的经典数独难题，其中增加了每个盒子添加不等式条件的转折。

现在，我已经设法在 Python 中创建了一个常规的数独求解器（使用蛮力方法），但我无法掌握我将使用什么方法来解决这个问题。我是不是想多了，还是这比普通的谜题复杂得多？

Answer 1

这只是约束解决。

如果您有数独板，那么对于每个单元格 (i, j)，您都有以下约束：

board[i, j] in [1, 2, 3, 4, 5, 6, 7, 8, 9]
for each cell (a, j) where i != a: board[a, j] != board[i, j]
for each cell (i, b) where j != b: board[i, b] != board[i, j]

对于特定的单元格，您已经知道它们的值是什么。这实际上只是一个不同的约束：

board[c1, c2] == 7

就是这样。蛮力检查器可以简单地通过所有可能的方式来填充板单元（特别是注意第一个约束），并检查这些约束是否成立。如果他们都坚持填写，那么它可以输出板。否则，它会继续进行。

如果您现在允许特定位置的不等式，您可以使用完全相同的蛮力算法。这只是在说明板已正确填写之前必须做的一项新检查：

2 <= board[c3, c4] < 8

---

使用蛮力很容易，但使用 Prolog 之类的逻辑编程语言或Numberjack 之类的约束编程库也很容易

以下是上述所有约束的 Numberjack 版本（按出现顺序）：

board[i, j] = Variable(1, 9)
# ... need to define all the board before you execute the following:
for a in xrange(1, 10):
    model.add(board[a, j] != board[i, j])
    model.add(board[i, a] != board[i, j])
model.add(board[c1, c2] == 7)
    model.add(board[c3, c4] < 8)
model.add(board[c3, c4] >= 2)

对于约束求解器的实际使用，这不是惯用的。在现实生活中，您可以使用“所有这些都是不同的”约束、AllDiff 等等，而不是单独指定 !=s。但你明白了。

Answer 2

您可能可以修改 Peter Norvig 的求解器以添加这些约束。