In response to my posts here:
http://cboard.cprogramming.com/showthread.php?t=109951
where I "bragged" about my 3+s solver.
I'm not quite down to single millisecond solution, but I'm quite pleased with my 100x speed improvement for my particular test-case - currently solved in 31 ms on my rather ancient machine with rather slow memory.
Steps to improve it:
[list]
- Use release mode rather than debug mode. This halfed the time.
- Keep track of the count of candidates for each cell, instead of counting them. Not much gain, but made some of the logic simpler, so worth having anyways.
- Do not use recursion unless there's a multiple candidates for this cell (so, if we are just following up on the consequence of a move that leaves us with single digit candidates in some other places, just continue filling those in). Since recursion also means copying the board and solution details, it's a good save. This got me to sub half a second for my benchmark casse
- Check if there is a possible solution, and abort immediately if we have cells with no candidates [so the 1234 down the bottom right and 56789 across the bottom posted by anon is solved in "0" time].
Using a linked list for candidates was done to make the code simple - I can most likely gain quite a bit by having a more compact storage of candidates - e.g. a bitmap.
Some of the code is also "neat but not fast", e.g. I have accessor functions to get to CandidateList(x, y) that returns a reference to that candidate list. There may be better ways to do that.
But I still feel quite chuffed, it only took a few hours.
--
Mats