解决数谜谜题 [英] Solving Kakuro puzzles

问题描述

下面是一个很好的反思：

Here's a good one to reflect on:

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

我试图做一个解答者为这场比赛。该文书是做（读有不同数量的行和列的初始文件。它假定输入文件遵循游戏让游戏始终是可解的规则。把你的时间来阅读游戏规则。

I'm attempting to make a solver for this game. The paperwork is done (reading an initial file with a variable number of columns and rows. It's assumed the input file follows the rules of the game so the game is always solvable. Take your time to read the game rules.

我照顾的数据结构，我认为将适合最好的：

I've taken care of the data structure which I think will suit best:

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

和由这些阵列动态地去努力。 我做了这样的黑色方格为-1白格子值（实际的解决方案正方形）初始化为0。您也可以从阵列中的每个aSquare结构的位置容易，没必要为这额外的结构域

And made an "array" of these dynamically to work on. I made it so that the black squares have value of -1 and white squares (the actual solution squares) initialize at 0. You can also get the position of each aSquare struct from the array easily, no need to make additional struct fields for it.

现在的算法......如何在世界上，我会调解这些款项，并找到解决所有类型网格的一般方法。我一直在整个下午都在努力与此无济于事。

Now the algorithm ... How in the world will I conciliate all these sums and find a general way that will solve all types of grids. I been struggling with this all afternoon to no avail.

帮助是AP preciated，玩得开心！

Help is appreciated, have fun!

*编辑：我只是意识到我张贴的实际链路有一些提示有关问题的技巧。我仍然会保持这种积极的，看看有什么人来了。

* I just realized the actual link I posted has some tips regarding solving techniques. I will still keep this up to see what people come up with.

推荐答案

一个简单的蛮力解算器数独取毫秒为单位来运行，所以你不必理会实施任何特殊的战术。我认为，如果数谜这将是相同的。一个简单的算法：

A simple brute-force solver for Sudoku takes miliseconds to run, so you don't need to bother implementing any special tactics. I think that in case of Kakuro this will be the same. A simple algorithm:

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

此算法可能更好地工作，如果发现场的最佳顺序填写。尽量选择这将是最受限制的领域。（如：不会有太多的值是合法的​​）

This algorithm might work better if you find the best order of fields to fill. Try to choose fields which will be the most constrained (as in: there are not many values that are legal).

无论如何，这将是可能是最容易实现，所以尝试它，寻找更复杂的解算器仅在这一项将无法正常工作。 （其实这是最简单的约束规划求解器之一，真正的CP求解器要复杂得多，当然）。

Anyway, this will be probably the simplest to implement, so try it and look for more sophisticated solvers only if this one will not work. (Actually this is one of the simplest constraint programming solvers; real CP solvers are much more complicated, of course).

这篇关于解决数谜谜题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！