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]
  1. Use release mode rather than debug mode. This halfed the time.
  2. 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.
  3. 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
  4. 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