Geek Answers Handbook

Kakuro Puzzle Solution

Here is a good thing to think about:

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

I am trying to make a solver for this game. Documents are executed (reading the source file with a variable number of columns and rows. It is assumed that the input file complies with the rules of the game, so the game is always solvable. Do not rush to read the rules of the game.

I took care of the data structure, which, in my opinion, would best fit:

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

And made an "array" of these dynamically to work. I made the black squares have a value of -1 and the white squares (the actual squares of the solution) were initialized to 0. You can also easily get the position of each aSquare structure from an array, you do not need to create additional structure fields for it.

Now the algorithm ... How in the world can I reconcile all these amounts and find a common way that solves all types of grids. I struggled with this all day to no avail.

Help is appreciated, have fun!

* EDIT: I just realized that the actual link that I posted has some tips regarding the solution methods. Anyway, I will keep track of what people come up with.

+7
c algorithm
source share
6 answers

A simple brute force solution for sudoku takes milliseconds, so you don't need to worry about implementing any special tactics. I think that in the case of Kakuro it will be the same. 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 may work better if you find a better order for filling in the fields. Try to select the fields that will be the most restricted (as in: there are not many values ​​that are legal).

In any case, this will probably be the easiest to implement, so try it and find more complex solvers only if this one does not work. (Actually, this is one of the simplest constraint programming solvers, and, of course, real CP solvers are much more complicated).

+5
source share

Regarding the programming of the constraint: here are a few different implementations of how to solve the Kakuro puzzle with the Constraint Program (everyone uses the same basic principle). The problem instance is fixed in the program.

Edit: Added programming on Google or-tools / C # and the answer.

+6
source share

If your interest ultimately lies in creating a software solution for these games, but without going into the algorithmic details, I recommend using the Constraint Programming (CP) engine. CP is a declarative programming paradigm that is very well suited for such problems. Several commercial and open CP engines are available.

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

+2
source share

I would suggest that Linear programming can be easily used to solve this kind of games .. then this is an integer problem for which there are exact solutions .. ( branch and connected ? Cutting plane ?)

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

+1
source share

This is a linear linear algebra that uses vector / matrix manipulation methods to solve.

[edit - response to 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 multiple lines, you get:

 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.

0
source share

I found some good hit manipulations that speed up Kakuro's decision. You can find the source here .

0
source share

More articles:


All Articles