The New Sudoku Players' Forum

[surendra.jain]

Can someone tell me how to check for unique solution in a kakuro puzzle without doing brute force backtracking.

Thanks,
Surendra

[Mathimagics]

I beleieve that the short answer is, no, there is no alternative of which I am aware that offers any shortcut to testing the property "unique solution" (or US).

Some observations are in order:

• Kakuro differs fundamentally from Latin Square puzzles, such as Sudoku. While every value in a "run" must be different, the fact that the set of numbers required is not fixed, as it is in Sudoku, has a severe restricting effect on solver approaches.

• for that reason, many the alternative approaches to logic problem solving are not available

• DLX is out because it only applies to exact cover problems, and Kakuro is not one of these

• SAT is out, as far as I can tell, because there appears to be no way to encode Kakuro in CNF

• That leaves CSP (Constraint Satisfaction Problem) solvers. This method is certainly usable, but I believe I have demonstrated elsewhere in this forum (search Kakuro for "Eclipse") that it is hopeless at solving moderately difficult Kakuro puzzles

That leaves us with good old DFS, brute force - we just have to pull out all the stops to make it relatively efficient. Even so, there are Kakuro puzzles that can take even the fastest solver (um, that would be mine, I guess ) an hour or even more to solve (ie proove uniqueness).

One way to speed it up is to throw away the classic "choose cell with the least number of possible values" model. Think of a large puzzle with a 2-cell sum of 4 or 17 in opposite corners of the grid. The naive "min NPV" approach would be bound to pick these early, but would then waste time solving for totally disconnected areas of the grid, a sure-fire killer for a DFS solver.

It's better to consider whole runs as units, choosing the run with the least possible set of values, then restricting the next level to runs that intersect with these, thus increasing the chances of a reasonably trimmed search tree at any stage.

I'd like to add that for all the above reasons, Kakuro is a real challenge, whether solving by hand, or by computer. The generation problem is similarly unique. I knocked up a reasonable Sudoku Jigsaw solver in a few days, but it has taken me nearly 2 years to get a Kakuro system up and running.

[crabmouse]

Contrary to the above assertion, Kakuro can be solved using the DLX algorithm.
The modification is to add some extra columns and rows to the ExactCover boolean matrix.

The exact cover boolean starts with columns for each square in the puzzle and for each {constraint, value }.
This is sufficient if the clue can be satisfied with only one combination. For example 3:7 can only have the combination 1,2,4.

If there is more than one combination, then an extra column must be added to specify which combination of numbers was used.
One extra row per possible pattern must also be provided.
For example, suppose that there are three points A,B,C and their total is 8. This can be satisfied either by 1,2,5 or 1,3,4.

The relevant parts of the Exact cover boolean are:
A B C 1 2 3 4 5 *
A=1 1 0 0 1 0 0 0 0 0
A=2 1 0 0 0 1 0 0 0 0
A=3 1 0 0 0 0 1 0 0 0
A=4 1 0 0 0 0 0 1 0 0
A=5 1 0 0 0 0 0 0 1 0
B=1 0 1 0 1 0 0 0 0 0
B=2 0 1 0 0 1 0 0 0 0
B=3 0 1 0 0 0 1 0 0 0
B=4 0 1 0 0 0 0 1 0 0
B=5 0 1 0 0 0 0 0 1 0
C=1 0 0 1 1 0 0 0 0 0
C=2 0 0 1 0 1 0 0 0 0
C=3 0 0 1 0 0 1 0 0 0
C=4 0 0 1 0 0 0 1 0 0
C=5 0 0 1 0 0 0 0 1 0
125 0 0 0 0 0 1 1 0 1
134 0 0 0 0 1 0 0 1 1

Now the exact cover algorithm can be employed.

[Mathimagics]

Hi crabmouse,

You could be right, perhaps Kakuro can be expressed as an exact cover problem.

But I am not totally convinced by your proposed model. How do you handle the dual (vertical/horizonal) constraint interactions?

Cheers
MM

[crabmouse]

Hi MM,

The fact that that each point in the Kakuro grid has two constraints, one vertical and one horizontal, is not a problem. In fact, it is perfectly normal.
In both Sudoku and Kakuro, each point belongs to multiple constraints.
Each constraint has its own independent columns in the Exact Cover matrix which are not shared by other constraints. There is one column for each value that can appear in the constraint. Suduko is more simple because each of the values appears exactly once in a constraint.
In Sudoku each point is shared by three constraints, one for the row, one for the column and one for the 3x3 box that contents it. Each row represents the assignment of a particular value to a particular square in the grid. The row will have 4 ones in the Exact Cover matrix. One for the column that relates to the point and ensures that only one value is assigned to the point. The second is one of the nine columns for the row constraint, which ensures that the value appears exactly once in the row. Similarly, the other values lie in one of the nine columns for the column constraint and in one of the nine columns for the relevant box constraint.

In Kakuro as well, the main rows each deal with the assignment of a specific value to a specific point. The row will have three ones in the Exact Cover matrix, one in the column that ensures that the point is assigned only one value, one to ensure that its value appears exactly once in the horizontal clue and one column that ensures that its value appears only once in the vertical clue. The complication with Kakuro is that, unlike Sudoku, values sometimes do not appear in the answer. That is why we have to add extra rows to the Exact Cover matrix to supply the missing 1's so that the column has a total of one when the correct rows are selected.

For example, if a clue has three elements totalling 8 it can be satisfied by {1,3,4} or {1,2,5) and it will have five columns for each of the values 1,2,3,4,5 and one column to indicate which of the two solution sets was used. We have to add two rows to the Exact Cover matrix, one for {1,2,5} and one for {1,3,4}.
The row for {1,3,4} will have 1's in the columns representing 2 and 5. If the solution for the problem uses the values {1,3,4} the columns for the values 1, 3, 4 will be satisfied by the rows that assigned 1,3,4 to the specific points. The columns for values 2, 5 will be satisfied by the extra row for {1,3,4} which supplies the missing ones.

I have written a program to solve and compose Kakuro problems and I use this exact cover to check problems as they are entered. It runs instantaneously on smaller Kakuro problems, but the Exact Cover DLX algorithm doesn't scale well for larger problems. Problems of the size 24x14 are around the critical size. Sometimes they are solved quickly, but sometimes they use so much time that I lose patience.

[Mathimagics]

Thanks, crabmouse, for clarifying your model!

And congratulations, this demonstrates (for the first time that I am aware of) that Kakuro puzzles can be expressed as exact cover problems.

So not only DLX, but SAT too, can be used to solve.

As you have found, DLX has problems with large and/or difficult grids ... the simple "choose column with least one's" approach is not particularly well suited in these cases. (SAT will also not scale well, so is unlikely to be efficient).

Cheers
MM