The Times Su Doku, Book 1

Yes, I know this is a strange book for a book review! As usual, this review will be more about me than the book itself! I bought the book at an airport, on the outward leg of a holiday a few years ago ('95 at a guess, maybe '96) to fill in time. Since then it's languished on my bookshelf, and I decided it was time to polish it off.

I've no idea if Books 2 through n bother, but as this is the first in the series, it goes from mind-bendingly easy to 'fiendish'. I must admit that some of the fiendish ones are sufficiently tedious to solve that it's hardly any fun any more, and I only really attacked them for completeness's sake.

While Su Doku automated solvers are ten-a-penny, I've never written one myself, so I haven't really formalised my approach, but I'm not sure what 'valid' Su Doku tactics are. For example, some times, when I'm stuck, I notice that a particular set of numbers has three possible combinations, two of which are indistinguishable in the wider configuration, so that if one were allowed, so would the other. Hence the correct answer must be the third configuration, since the overall solution must be unique. This seems vaguely cheeky to me. Even worse, sometimes I go for a backtracking solution - something like a case split in Davis Putnam theorem provers - and just make a guess and see if it works out. Yuck.

Having a quick look at articles on the net, plenty discuss back-tracking in automated solvers, which makes the approach remarkably dull! I'm still intrigued as to a) whether backtracking is necessary in some sense - i.e. whether a set of simple tactics that don't rely on finding contradictions arbitrarily far down the line work (even if I'm being a bit dodgy by saying 'arbitrarily far down the line' on a finite-sized puzzle) and b) whether all the puzzles set for books and newspapers are designed to be soluble without backtracking - that is, brute force is not intended to be the answer!

The temptation is there to write a non-brute-forcing Su Doku solver, but... after wading through those 'fiendish' puzzles, I think I'd rather do something completely different for a while.

Posted 2009-03-15.