解决不平等数独的策略？

Question

我最近碰到的经典数独解算器的一个转折是（相当疯狂）inequality sudoku，这是你的经典数独谜题与添加扭曲，有不平等条件添加到每个盒子。

现在，我设法在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) 

这不语tic实际使用约束求解器。在现实生活中，不是单独指定！= s，而是使用“所有这些都是不同的”约束，AllDiff等等。但你明白了。

Answer 2

您可以修改Peter Norvig的solver以添加这些约束。