解決不平等數獨的策略？

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以添加這些約束。