Kakuro Solver - Performance Benchmarks

For fans of Kakuro

Kakuro Solver - Performance Benchmarks

Postby Mathimagics » Mon Sep 05, 2016 4:09 am

Prompted by recent discussion on the subject of Kakuro solver algorithms, I decided to conduct some comparative tests of currently available Kakuro solvers.

Sadly, the majority of offerings, as far as I can tell, fall into one of the following categories:

  • a player, not a solver
  • not available on Win32 platforms
  • no way to feed it my test puzzles
  • plays music! and/or chock-full of AdWare
  • not free, and not fully functional enough in demo mode

In fact I only found one program that could be considered useful for these purposes, and it's called Kakuro Nichiyou. Not only was it suitable for benchmark testing, but also it just happened to have this in its list of features:

  • A powerful and fast solver (the fastest in the world maybe)

Ok, I'm sold! Let's go! 8-)

On the plus side, it's custom-puzzle format was easy to deal with, so I was able to import selected puzzles from my system for testing quite easily. It also comes with source code, although MSVC++ is not something I can easily deal with - the exe comes pre-built, however.

My benchmark test set included 2 puzzles on 12x12 grid, and 3 puzzles on 18x18 grid. The test cases for both sizes included both a "computationally easy" (Rating = 1) and "computationally hard" (Rating > 4). See here for details of my rating system, it's quite simple.

For comparison, I created a standalone, stripped down portable (F90) version of my "KP" Solver, which is a straight-forward implementation of a DFS solver, based on the simple domain-shaving described at the above link location (rating system).

The test results:

Code: Select all
               White cell               K-N               KP
Puzzle   Size    Count     Rating    Time1(secs)      Time2(secs)      T1/T2   
----------------------------------------------------------------------------
12A      12x12    105      1          0.167             0.027            6
18A      18x18    250      1         18.5               0.120          154

12B      12x12    108      5.3       48.4               2.2             22
18B      18x18    250      4.1      675                 0.562         1200
18C      18x18    250      4.3     3465                 3.1           1120


As you can see, KN performance deteriorates markedly with grid size and puzzle complexity. Actually these figures flatter KN by a factor of 2, since I discovered that it assumes the puzzle has a unique solution, which ain't necessarily so, of course. My times are for verifying uniqueness, ie. exhaustive DFS.

I looked at his code, and can't really figure out what his method is, there's no mention of the words "hidden" and "naked" (nor is there in mine - these elementary Sudoku solving techniques are of marginal use in Kakuro, for computers anyway).

He has a list of "Solver options", about 10, none of which make any sense to me, and I ran without disturbing their default settings (all enabled).

The total size of the .cpp and .h files in his app is about 200Kb, of which perhaps half (?) is interface-related, compared to my 822 lines of f90 at 22Kb. My solver employs no lookup tables of any sort, other than the minimum and maximum sums possible for lengths 2 to 9. It's performance is very dependent on the order in which it chooses to solve free cells, but I have found a simple approach which seems to work nicely.

I wanted to contact the author (Joerg Sonntag, aka "theMk2k") to discuss, but he appears to exist only on twitter, and I don't do tweets. Also if you click on "How to Use the Solver", you are told "the theory behind the solver will be added at some future date". :?

If anyone knows of other software I can test, please let me know. 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro Solver - Performance Benchmarks

Postby Mathimagics » Mon Sep 05, 2016 5:23 am

I decided to re-introduce the one lookup table I had disabled (to prove that none were needed). This is the table SDOM(S, L, D) that says D can appear in runs with sum = S, len = L.

I'd convinced myself that it would only have a marginal effect, allowing more efficient operation of the initial domain shave only.

Silly me, by reducing extra initial domain values in some cells, this has a knock-on effect on throughout, reducing the DFS search tree by a significant factor.

Modified timings for KP:
Code: Select all
               White cell               K-N               KP
Puzzle   Size    Count     Rating    Time1(secs)      Time2(secs)      T1/T2   
----------------------------------------------------------------------------
12A      12x12    105      1          0.167             0.027            6
18A      18x18    250      1         18.5               0.070          264

12B      12x12    108      5.3       48.4               0.156          310
18B      18x18    250      4.1      675                 0.297         2273
18C      18x18    250      4.3     3465                 1.483         2336


My solver was built with Gnu Fortran (gfortran) compiled with -O3.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro Solver - Performance Benchmarks

Postby SudoKai » Thu Sep 08, 2016 12:36 pm

I stumbled upon this site yesterday searching for Sudoku variants.

https://sites.google.com/site/mircorosarisolutori/kakuro

It is not in English, but I thought you might be interested in checking it out.
SudoKai
 
Posts: 16
Joined: 07 June 2014
Location: South-Africa

Re: Kakuro Solver - Performance Benchmarks

Postby Mathimagics » Thu Sep 08, 2016 2:11 pm

OK, I looked at that site - sadly Italian is all Greek to me. The "app" appears to be a player interface, implemented in Excel of all things! Probably not a candidate for a testworthy "Solver" app, however.

Thanks anyway! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro Solver - Performance Benchmarks

Postby Mathimagics » Sun Sep 18, 2016 11:26 am

I have now got a benchmark list of hard puzzles against which to test solver performance.

I have compared versions (on my Win7 platform) written in:

  • VB6 (the orginal devt language)
  • PB (PowerBasic, a very old copy, v7)
  • F90 (Gnu Compile Collection, v5.3)
  • C (Gnu Compile Collection, v5.3)

The test results:
Code: Select all
                  Rating     DFS       VB       PB      F-O3     C-O3     C-NoOpt
 KP1818_Hard       4.092    1257     1.089    0.643    0.183    0.162   
 KP1818_Harder     4.324   10461     6.769    4.132    1.248    1.205
 KP2424_Hard       4.077   70745    20.951   13.954    4.974    4.622    16.116
 KP2424_Harder     4.235   91274    41.762   26.015    8.656    8.300    27.136
 KP2424_XHard      4.130  290853   266.735  157.172   50.839   49.154   144.929
 KP2424_Killer     4.267 2229694  1123.824  700.226  247.378  229.261
 KP2424_Diabolical 4.406 5310008  3002.179 1858.347  659.236  624.777


Notes:
  • F-O3, C-03 are indicators that the program was built with -O3, ie. max optimisation. This is important, as you can see from the column marked "C-NoOpt", which is the C program compiled without optimisation
  • these times are by no means the best achievable. In all cases the solver uses a naive next cell selection strategy, ie "select cell with least number of possible values". I am still trying to develop alternate strategies.
  • optimised GCC versions win by a country mile, all hail the folks at Gnu
Last edited by Mathimagics on Sun Sep 18, 2016 8:49 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kakuro as a Constraint Satisfaction Problem

Postby Mathimagics » Sun Sep 18, 2016 1:02 pm

I came across this article by Helmut Simonis (2007): "Kakuro as a Constraint Problem".

The paper itself is perhaps unremarkable, in that he spends a lot of time banging on about constraint propagation, and his tests only involve computationally simple cases, ie: cases with Complexity rating close to 1.

But it made me wonder how a CSP-solver would go at solving my harder examples. So I downloaded and installed Eclipse (6.1), which was a fairly simple process, and set about teaching myself how to deploy it to solve Kakuro.

The model I used is a simple one, I generate variables X11, X12, ... to represent unsolved grid cells, then it's just a matter of setting the cell domains, applying the "alldifferent([X])" and "sum([X])=N" constraints, and invoking the "search" function.

An example of the ECL code to solve a simple example:
Hidden Text: Show
Code: Select all
/* Kakuro puzzle: Sample
   Soln:
      7291
      9786
      215.
*/
:-lib(fd).
:-lib(fd_search).
:-lib(listut).

csum(L,N):-
   (sum(L)#= N,
    alldifferent(L)).

solve :-
   print('Kakuro puzzle: KT0405\n'),

   term_variables([
      X11,X12,X13,X14,
      X21,X22,X23,X24,
      X31,X32,X33]
      , Xlist),

   % black cells
   X34 :: 0,
   
   %domains (naive settings)
   Xlist :: 1..9,

   % constraints
   csum([X11,X12,X13,X14], 19),
   csum([X21,X22,X23,X24], 30),
   csum([X31,X32,X33],      8),

   csum([X11,X21,X31],     18),
   csum([X12,X22,X32],     10),
   csum([X13,X23,X33],     22),
   csum([X14,X24],          7),

   search(Xlist, 0, first_fail, indomain_min, complete, []),

   print('\nSolution:\n'),
   writeln([X11,X12,X13,X14]),
   writeln([X21,X22,X23,X24]),
   writeln([X31,X32,X33,X34]).


Now I want to test puzzles from my benchmark set (see above), for which my solver requires DFS searching. I generate ECL for the reduced puzzle - ie. we only specify unresolved cells, and these with reduced domains that my solver has already calculated (through domain shaving).

To my delight, a preliminary test case, KP1212_Hard, was solved in less than 0.2s. Here's a competitive solver,I thought.

But sadly, KP1818_Hard, which is only the first of my benchmark test suite, has been running for over 8 hours with no result. Compare this with just 0.16s for the C DFS solver. :(
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Improved Kakuro Solver

Postby Mathimagics » Wed Sep 21, 2016 8:52 am

I took the C version of my solver, and produced a modified version, CM, in which I introduced the following optimisations:

  • a compact grid representation - the Domain(R,C,D) table is eliminated, with domains stored in situ, ie: if Grid(R,C) is negative (hi-bit on), the cell is free, and the low-order bits are a domain mask. This reduces the size of the DFS stack and makes PUSH/POP operatons faster

  • all Grid traversals are done via pointers where possible

This improves the solver performance in all benchmark tests:
Code: Select all
                  Rating       DFS       C          CM
 KP1818_Hard       4.092      1257     0.162      0.131
 KP1818_Harder     4.324     10461     1.205      0.940
 KP2424_Hard       4.077     70745     4.622      3.302
 KP2424_Harder     4.235     91274     8.300      6.121
 KP2424_XHard      4.130    290853    49.154     37.686
 KP2424_Killer     4.267   2229694   229.261    169.816
 KP2424_Diabolical 4.406   5310008   624.777    487.315
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Improved Kakuro Solver

Postby Mathimagics » Wed Sep 21, 2016 9:21 am

Next I looked at ways to reduce the size of the DFS search tree. This boils down to finding a better "next cell" selection strategy than the naive model, which just selects the cell with the smallest NPV (number of possible values).

In all of the benchmark test cases, there are several cells with NPV = 2 initially, so the naive approach selects the first one encountered. This is not always the best choice.

I introduced an option to "look ahead" - a limited form of BFS (breadth-first search). We test all NPV = 2 candidates and see which one leads to the most cells solved. Solver version CMB applies this only at the top 2 levels, ie first and second cell selection.

Code: Select all
                  Rating       DFS       C          CM         CMB       DFS
 KP1818_Hard       4.092      1257     0.162      0.131      0.174      1311
 KP1818_Harder     4.324     10461     1.205      0.940      0.991     10337
 KP2424_Hard       4.077     70745     4.622      3.302      3.352     70693   
 KP2424_Harder     4.235     91274     8.300      6.121      4.617     79556   
 KP2424_XHard      4.130    290853    49.154     37.686      1.159     15779   !!
 KP2424_Killer     4.267   2229694   229.261    169.816     91.180   1692519 
 KP2424_Diabolical 4.406   5310008   624.777    487.315    199.237   3451440 


This option works well for the 4 hardest cases, dramatically so in the case of KP2424_XHard. This case was anomalous, in that its complexity rating seemed to indicate it might not be that hard, and this was indeed the case.

But attempts to further reduce the DFS counts for KP2424_Killer and KP2424_Diabolical, by increasing the depth at which BFS is performed, failed to produce any further DFS reductions.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro Solver - Performance Benchmarks

Postby JasonLion » Wed Sep 21, 2016 1:52 pm

One tactic used in some of the fast regular Sudoku solvers is to create a pseudo random ordering of the cells and to checks the next sequential cell in the pseudo random order where NPV = 2, remembering the next sequential cell across calls to the routine. This can be implemented very inexpensively and spreads the guesses out across the board, which can often help. By spreading the guesses out spatially you tend to run into a cell that disproves the guess more quickly.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Kakuro Solver - Performance Benchmarks

Postby Mathimagics » Wed Sep 21, 2016 2:07 pm

Thanks Jason, I will have to experiment with that method ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro Solver - Performance Benchmarks

Postby Mathimagics » Wed Sep 21, 2016 7:19 pm

No luck with that approach, I'm afraid!

It is probably down to the fact that any cell with NPV = 2 in Sudoku is going to be a fairly good cell to check in any case, but in Kakuro it might be a good choice, or might be a downright terrible one.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Greatly Improved Kakuro Solver!

Postby Mathimagics » Mon Sep 26, 2016 8:06 am

I had an idea, can we learn more from doing a partial BFS? It turns out we can indeed!

If we use the "look ahead" (BFS) function to test all possible values for a cell (R, C), then we can often draw an inference based on the set of snapshots produced for each test.

If some other free cell, (RR, CC) becomes set to the same value, D, in EVERY case tested for (R, C), then we know (RR, CC) must be D in the current context.

If (RR,CC) isn't set, then we can check its domain, and see whether for any D in that domain, EVERY test on (R, C) removes D from Domain(RR,CC). In that case we know that (RR, CC) is not D in the current context.

By collecting and applying these inferences, we can reduce the search tree, sometimes dramatically. Here are my new results, with the new version labelled CM-B*:

Code: Select all
                  Rating       DFS       CM   |   CM-B        DFS  |   CM-B*     DFS
 ---------------------------------------------|--------------------|----------------               
 KP1010_Killer     5.878   1184177   319.353  |  90.146    220066  |   0.290     196
 KP1212_Hard       5.306       128     0.075  |   0.123       129  |   0.363       7
 KP1818_Hard       4.092      1257     0.131  |   0.174      1311  |   0.927     378
 KP1818_Harder     4.324     10461     0.940  |   0.991     10337  |   0.991    3897
 KP2424_Hard       4.077     70745     3.302  |   3.352     70693  |   3.131   51760
 KP2424_Harder     4.235     91274     6.121  |   4.617     79556  |   5.692   73639
 KP2424_XHard      4.130    290853    37.686  |   1.159     15779  |   2.766    6076
 KP2424_Killer     4.267   2229694   169.816  |  91.180   1692519  |   6.248   50091
 KP2424_Diabolical 4.406   5310008   487.315  | 199.237   3451440  |   9.645   46639


I have added to the benchmark suite a recent discovery, KP1010_Killer, which has the highest complexity rating I have yet encountered for a puzzle with a unique solution, but reduces very nicely with the new solver.

The new solver tests were all done with BFS performed at the top 5 levels of the search tree. This was found by experimentation to be the best setting overall. It increases the time for some tests, but this is more than compensated for by the reductions in time for the most expensive cases.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Further Improvements

Postby Mathimagics » Sat Oct 01, 2016 8:18 am

I have improved version CM-B* by:

  • improving the valid-sum check functions. This is used by the domain-shaver to check validity of domain settings, and is where most of the time is spent. By sorting the free cells in NPV order, the results are in general obtained more quickly

  • fixing a bug in the BFS look-ahead checker. This bug did not affect overall outcome, but was failing to detect dead-ends in some cases, resulting in wasted DFS calls
.

The new results are given below:

Code: Select all
                  Rating       DFS       CM   |   CM-B        DFS  |   CM-B*    DFS
 ---------------------------------------------|--------------------|----------------
 KP1010_Killer     5.878   1184177   319.353  |  90.146    220066  |   0.146      7
 KP1212_Hard       5.306       128     0.075  |   0.123       129  |   0.115      1
 KP1818_Hard       4.092      1257     0.131  |   0.174      1311  |   0.451    147
 KP1818_Harder     4.324     10461     0.940  |   0.991     10337  |   0.580   3859
 KP2424_Hard       4.077     70745     3.302  |   3.352     70693  |   0.546   7750
 KP2424_Harder     4.235     91274     6.121  |   4.617     79556  |   4.392  73187
 KP2424_XHard      4.130    290853    37.686  |   1.159     15779  |   1.331   5928
 KP2424_Killer     4.267   2229694   169.816  |  91.180   1692519  |   3.844  50041
 KP2424_Diabolical 4.406   5310008   487.315  | 199.237   3451440  |   4.392  43069


All test cases are now solved in less than 4.5s. 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro Solver - Performance Benchmarks

Postby janho » Thu Nov 10, 2016 8:47 pm

Hi,

I am currently looking for hard Kakuro puzzles and stumbled upon this thread. Mathimagics, would you mind sharing your hard instances in an easy-to-parse format?

Background: I am working in improving constraint programming solvers (like the one used by Helmut Simonis, whom you cite) and I seem to be unable to find instances that would take more than a fraction of second to solve. So I would very much be interested if I could try my hands on your instances, especially because they seem to pose difficulty to the constraint solver you tried.

Thanks in advance!
janho
 
Posts: 2
Joined: 10 November 2016

Re: Kakuro Solver - Performance Benchmarks

Postby Mathimagics » Mon Nov 21, 2016 6:43 pm

Hello janho!

My apologies for being slow to respond - I've been away for the past few weeks.

The easiest format for puzzle test cases is given by the solutions. Here are some of the cases mentioned above:

Hidden Text: Show
KP1212_Hard

342.2687435
421.5496213
6542.379528
895472631..
78964132.95
96312.54378
51.78615243
..689521437
678954.8769
9653127.124
8245319.586



KP1818_Hard

4123.35621874.371
7241.82913765.687
8452397.879.21463
..6457.896.213798
54761.157.21345..
76982134.21386974
6587432.213465897
12.962731485.2135
312.8796.3461.241
4312.954376821.12
895324617.7945286
97863542.45782369
..91768.189.34158
937548.129.8976..
72481.123.5376412
413.61435897.8531
856.95247136.9875


KP1818_Harder

9123.35621874.321
7241.82913765.687
8652397.379.21453
..6457.198.213598
54761.124.21347..
76982135.21386974
6587432.213465897
12.962731485.2135
312.8796.3461.241
4312.954376821.12
895324617.7945286
97863542.45782369
..91768.189.34158
937548.129.8975..
52481.123.5376412
713.61435897.8691
856.95287134.9875


KP2424_Hard

7985.79.7698..86927.986
6794.14.65879.98516.697
85369271.47136.37.39875
53426.58436219.78916532
98.98615324.5879.845.53
..93586471.9475.142.914
.687.4231.64251987.4321
146.398.5982.43756982..
657123.4285163.43586.12
48.56798.51.12764.61235
314.1582.743819.2173546
8976.231..967..798.2867
5294817.542136.1635.124
23816.56987.27.27698.78
97.37125.6379854.243189
..52934867.8491.798.251
8975.81973645.6987.349.
321.576.8579.82134956..
68.962.6918.97462531.86
56983412.94862351.68712
94871.73.23541.76284953
735.82697.97856.41.7634
251.91845..9768.97.9875


KP2424_Harder

7985.79.4798..86937.948
6794.14.15839.98516.697
85369271.47136.37.39875
53126.58436219.78916532
98.98615324.5769.845.53
..93586471.9485.142.914
.687.4231.64251987.4321
146.398.5682.43756981..
657123.4285163.43586.12
48.56798.71.21764.61235
314.1582.543829.2173546
8976.231..967..798.2867
5294817.542136.1635.123
23814.56987.17.27698.78
97.35124.6379854.243189
..52934867.8491.798.254
8975.81973645.6987.249.
351.576.8579.82134956..
68.962.6918.97862531.86
56983412.94862351.63712
94871.73.23541.76284953
475.82697.97834.41.7634
724.91845..9758.94.9875


KP2424_Killer

7985.79.6798..86937.948
6794.14.95837.98516.697
85369271.47136.37.39875
53126.58436219.78916532
98.98615324.5769.845.53
..93586471.5482.142.914
.687.4231.64251987.4321
146.498.5682.43756981..
657123.4285163.43586.12
48.56798.71.21764.61235
316.1586.543829.2173546
8976.231..967..798.2867
5294817.542137.1635.123
23814.56987.16.47698.78
97.37124.6379852.243189
..52934861.6491.798.254
8975.81973645.6987.249.
351.576.8579.82134956..
68.962.6978.97862531.86
56983412.94862351.68712
94871.73.23541.76284953
475.82697.97834.41.7634
724.91845..9758.94.9875


KP2424_Diabolical

7985.69.7698..86957.948
6794.14.95837.98526.697
85369271.47136.37.39875
53126.58436219.78916532
98.98615324.5849.845.53
..93586471.5476.142.914
.687.4231.64251987.4321
146.598.5682.43756981..
657123.4285163.43586.12
48.46798.71.21764.61235
316.1536.543829.2173546
8976.281..967..798.2867
5294817.542136.1635.123
23814.46987.12.47698.78
97.37124.6379852.243189
..42935861.6491.798.254
8975.81973645.6987.249.
351.576.8579.82134956..
68.962.6978.97862531.86
56983412.94862351.68712
94871.73.23541.76284953
475.82697.97863.41.7624
724.91845..9758.94.9875
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Next

Return to Kakuro