How to check for unique solution in a kakuro puzzle?

For fans of Kakuro

How to check for unique solution in a kakuro puzzle?

Postby surendra.jain » Thu Mar 09, 2017 5:35 am

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

Thanks,
Surendra
surendra.jain
 
Posts: 16
Joined: 15 August 2015
Location: India

Re: How to check for unique solution in a kakuro puzzle?

Postby Mathimagics » Thu Mar 09, 2017 11:30 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015


Return to Kakuro