具有幾種可能性的單元格總和

Question

我正在Ruby編程一個Killer Sudoku求解器，我嘗試採取人爲策略並將它們放入代碼中。我已經實施了大約10個策略，但我在這個問題上遇到了問題。

在殺手數獨中，我們有細胞的「區域」，我們知道這些細胞的總和，我們知道每個細胞的可能性。

實施例：

• 小區1可以是1，3,4或9
• 小區2可以是2,4或5
• 細胞3可以是3,4或9
• 所有單元格的總和必須爲12

我希望我的程序嘗試一切可能性以消除可能性。例如，在這裏，單元格1不能爲9，因爲在單元格2和單元格3中添加兩個可能的數字不能生成3.

所以我希望對於任意數量的單元格，通過嘗試它們並看到它不起作用是不可能的。

我該如何得到這個工作？

Answer 1

有多種方式來處理遊戲解決的普遍問題，並模仿人類的策略並不總是最好的方法。這就是說，這裏是你如何能夠解決你的問題：

1路，蠻力forcy

基本上，我們想嘗試的細胞組合的所有可能性，並挑選具有正確的總和的人。

cell_1 = [1,3,4,9] 
cell_2 = [2,4,5] 
cell_3 = [3,4,9] 
all_valid_combinations = cell_1.product(cell_2,cell_3).select {|combo| combo.sum == 12} 
# => [[1, 2, 9], [3, 5, 4], [4, 4, 4], [4, 5, 3]] 
#.sum isn't a built-in function, it's just used here for convenience 

削下來單個單元格，你可以這樣做：

cell_1 = all_valid_combinations.map {|combo| combo[0]}.uniq 
# => [1, 3, 4] 
cell_2 = all_valid_combinations.map {|combo| combo[1]}.uniq 
# => [2, 5, 4] 
. . . 

，如果你沒有一個巨大的大組單元，這種方式更容易代碼。但它可能會有點低效。對於小問題，這是我使用的方式。

---

第二個方式，回溯搜索

另一個衆所周知的技術從其他方法利用的問題。基本上，對於每個細胞，問「這個細胞可以是這個數字，給其他細胞？」

所以，開始與小區1中，可以在數是1？檢查，我們看到如果單元格2和3可以和11。（12-1） *可以單元格2的值爲2？檢查，能小區3總和至9（11-1）

等。在非常大的情況下，你可以有許多有效的組合，這會稍微快一點，因爲你可以在第一次找到一個單元格的有效數字時返回'真'。但有些人發現遞歸算法有點難度，所以你的里程可能會有所不同。