解决Kakuro难题

Question

这是一个很好的反思:

http://en.wikipedia.org/wiki/Kakuro

我正试图为这个游戏做一个解算器.文书工作是做(读列和行的可变数量的初始文件.它假定输入文件遵循的游戏规则,使游戏总是可以解决的.把你的时间来阅读比赛规则.

我已经处理了我认为最适合的数据结构:

struct aSquare { int verticalSum; int horizontalSum; int value; }

并动态制作了这些"阵列".我做了这样,黑色方块的值为-1,白色方块(实际解方块)初始化为0.您还可以轻松地从数组中获取每个aSquare结构的位置,无需为其创建其他结构字段.

现在算法......我将如何调和所有这些总和并找到解决所有类型网格的一般方法.我整个下午一直在苦苦挣扎,但无济于事.

感谢帮助,玩得开心!

*编辑:我刚刚意识到我发布的实际链接有一些关于解决技术的提示.我仍然会保持这一点,看看人们想出了什么.

Answer 1

关于约束规划:以下是如何使用约束规划解决Kakuro拼图的一些不同实现(所有这些都使用相同的基本原理).问题实例已在程序中修复.

• Google或工具/ Python:http://www.hakank.org/google_or_tools/kakuro.py
• 彗星:http://www.hakank.org/comet/kakuro.co
• MiniZinc:http://www.hakank.org/minizinc/kakuro.mzn
• SICStus:http://www.hakank.org/sicstus/kakuro.pl
• ECLiPSe:http://www.hakank.org/eclipse/kakuro.ecl
• Gecode:http://www.hakank.org/gecode/kakuro.cpp
• Google或-tools/C#:http://hakank.org/google_or_tools/kakuro.cs
• 答案集编程:http://hakank.org/asp/kakuro.lp

编辑:添加了Google或-tools/C#和答案集编程.

Answer 2

一个简单的数独蛮力解算器需要几毫秒才能运行,所以你不必费心实施任何特殊的策略.我认为,就Kakuro而言,这将是相同的.一个简单的算法:

def solve(kakuro):
    if kakuro has no empty fields:
        print kakuro
        stop.
    else:
        position = pick a position
        values = [calculate possible legal values for that field]
        for value in values:
            kakuro[position] = value
            solve(kakuro)
        kakuro[position] = None # unset after trying all possibilities

如果您找到要填充的最佳字段顺序,此算法可能会更好.尝试选择最受约束的字段(如:没有多少合法的值).

无论如何,这可能是最简单的实现,所以尝试它并寻找更复杂的求解器,只有当这个不能工作时.(实际上,这是最简单的约束编程求解器之一;当然,真正的CP求解器要复杂得多).