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