Just started it, and the point isn't much in trying to build together an algorithm, but rather in implementing one well. And we just started it (team of 3, hence the we).
The only problem is the lack of POO; as I'm first year into this the only language we can use is Javascool, which is a dumbed down Java without object programming.
I could get away with it by using two dimensional byte and boolean arrays to store the numbers and keep track of the non-changeable ones.
Here's what I would do:
1. Code up the forced simplification function first - i.e. eliminating any impossibilities for a guess-cell, setting any with just one possible answer, finding pairs, triples, etc with the same numbers (N in N possibilities) to eliminate those choices from other cells in the line or block. Make it return a "depth" value, saying how many cells it can complete with no guesses. (If it returns -1, then this path is a logical fallacy, so can be used to eliminate guesses later, or to reject the whole board if you have not yet guessed any at all).
2. From the first point where you now need to make a hypothetical move, you should calculate the highest depth for each possibility of a single guess, for each unknown cell (i.e. single recurse with the function from (1)). At this point, the top say 5 guesses are the ones to chase to the second recursion, and so on until you hit 81 (= solved). Obviously, each -1 you get back eliminates a guess from your unknown cell, and you should follow up with a run of your function again to see if it solves anything else for you.
I'm not sure if it applies perfectly, but I guess it should: have a look at Nelder Mead algorithm (that coincidentally, Enjo used in TransX for automin-finding). You want some flavor of this to hunt for the most promising depth holes to go investigate.
Now ... anti-patterns: you could conceive an initial problem that would be as hard as possible for your algorithm, and drive you close to a brute-force scan of every permutation. Have a think about how alternate search strategies (e.g. double guess, or triple random guess), might help break a pattern like that, rather than just going linearly into a worst-case scenario.
Damn ... this is almost tempting enough for me to go do another few hundred hours of coding, but I'd use C and 0MQ to parallelize it as hard as possible!
But I won't post any until I solve them. See if you are better than me (you probably are:lol
indeed.
