Solving Kakuro puzzles

Question

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.

Answer 1

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.

Answer 2

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