Quote:
Use release mode rather than debug mode. This halfed the time.
Pretty much what I found also.
Quote:
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.
Actually that's not something I did, and I'm not sure it would help in my case.
Quote:
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].
I don't copy the board on recursion, I only copy the array of possible moves, which is just 162 bytes. So I'm quite happy leaving mine performing the check for needing to backtrack upon the next call. I consider it essential to abort as soon as you detect that there are no possible moves for a cell though.
Quote:
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.
Yeah I used the bitflags approach, as did the other guy who got a fast solver in that last thread.
Quote:
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.
Yup, at some point it's speed over convenience. Bitflags work fine for me, as it feels like I've got the best of both.
I uploaded my solver to my site a few days ago. You can find it at the bottom of the page here.