1

我正在用 Ruby 编写一个 Killer Sudoku Solver，我尝试采用人类策略并将它们放入代码中。我已经实施了大约 10 种策略，但我在这方面遇到了问题。

在杀手数独中，我们有细胞的“区域”，我们知道这些细胞的总和，我们知道每个细胞的可能性。

例子 ：

  • 单元格 1 可以是 1、3、4 或 9
  • 单元格 2 可以是 2、4 或 5
  • 单元格 3 可以是 3、4 或 9
  • 所有单元格的总和必须为 12

我希望我的程序尝试所有可能性以消除可能性。例如，在这里，单元格 1 不能是 9，因为您不能通过在单元格 2 和 3 中添加两个可能的数字来得到 3。

所以我希望对于任何数量的单元格，它通过尝试它们并看到它不起作用来删除那些不可能的单元格。

我怎样才能得到这个工作？

4

1 回答 1

1

有多种方法可以解决游戏解决的一般问题，而模仿人类策略并不总是最好的方法。也就是说，您可以通过以下方式解决您的问题：

第一种方式，蛮力

基本上，我们想尝试单元格组合的所有可能性，并选择具有正确总和的那些。

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)

等等。在非常大的情况下，您可以有许多有效组合，这会稍微快一些，因为您可以在第一次找到单元格的有效数字时返回“真”。但是，有些人发现递归算法有点难以理解，因此您的里程可能会有所不同。

于 2012-04-11T19:48:27.337 回答