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; }

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.

Help is appreciated, have fun!

*EDIT: 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.

Regarding Constraint Programming: Here are some different implementations of how to solve a Kakuro puzzle with Constraint Programming (all using the same basic principle). The problem instance is fixed in the program.

• Google or-tools/Python: http://www.hakank.org/google_or_tools/kakuro.py
• Comet: 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 or-tools/C#: http://hakank.org/google_or_tools/kakuro.cs
• Answer Set Programming: http://hakank.org/asp/kakuro.lp

Edit: Added Google or-tools/C# and Answer Set Programming.

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).

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).

If your interest is ultimately in making a software solver for these games, but not getting into the algorithmic details, I recommend using a Constraint Programming (CP) engine. CP is a declarative programming paradigm that is very well suited to these sorts of problems. Several commercial and open source CP engines are available.

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

I would guess that Linear Programming can be easily used to solve this kind of game.. then this is an integer problem for which exact solutions does exist.. (branch and bound? cutting-plane?)

In any case using a table with the most certain combinations will be useful for sure (eg http://www.enigmoteka.com/Kakuro%20Cheatsheet.pdf)

I have found some nice bit-manipulation tricks that speed up Kakuro solving. You can pick up the source here.

This is straight-forward linear algebra, use vector/matrix manipulation techniques to solve.

[edit - answering the comments]

a + b + 0 + d + 0  = n1
0 + b + c + 0 + e  = n2
a + 0 + c + 0 + 0  = n3
a + b + c + 0 + e  = n4
a + 0 + c + d + 0  = n5

Above is converted to a matrix, and by adding and subtracting multiples of the rows, you end up with:

a 0 0 0 0 na
0 b 0 0 0 nb
0 0 c 0 0 nc
0 0 0 d 0 nd
0 0 0 0 e ne

No combinatorics, all remain integers.