解决不等式数独的策略？

Question

最近我遇到了一种经典数独解法的新变种，叫做不等式数独。它和普通的数独很像，但每个小方格里还加了一些不等式的条件。

我之前用Python写过一个普通数独的解法，方法是用暴力破解的方式，但现在我对如何解决这个新问题有点困惑。我是在想太多，还是说这个问题比普通数独要复杂得多呢？

Answer 1

你可以尝试修改彼得·诺维格的解题器，来添加这些限制条件。

Answer 2

这其实就是在解决约束问题。

如果你有一个数独棋盘，那么对于每个格子 (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，等等。但你明白这个意思就好。