[LRUG] Continuations

[Piers Cawley]

Andrew Stewart <boss at airbladesoftware.com> writes:

> Hello,
>
> On 15 Mar 2007, at 13:27, Piers Cawley wrote:
>> That too. Again, having my grid reset its state a branch fails is very
>> useful here. Before I implemented that I was pretty much restricted to
>> going through the grid in a fixed order; switching to a 'pick the most
>> constrained cell and try and give it a value' strategy substantially
>> improved the solver's speed. The current 'example' sudoku I'm solving
>> only calls the failure continuation six times.
>
> In a slightly mischievious way, I was under the impression that true  
> sudokus could always be solved by logic alone and never needed  
> guesswork.
>
> Am I misinformed* or have you exhausted all the logical attacks you  
> can think of?(!)

I decided to see how far I could get with brute force. It has the
advantage of working over an entire class of puzzles without having
to do too much in the way of adding per puzzle type strategies beyond
simply working out how to represent said puzzle type's
constraints. So, for instance, the same basic solver solves Sudoku,
Killer, and Kakuro simply by changing my grid parser and the
'initialize_constraints' method[1].

I really should properly write this solver up as a talk or something
shouldn't I?

1. Admittedly, the Killer version does take advantage of a 'meta'
   constraint (any row, column or nonet in a Killer puzzle must add up
   to 45 so if you have a nonet in which whole contains 3 constraints
   such that 4 cells must add to 23, another 2 must add to 12 and 2
   more must add to 4, then you know that your remaining cell has to
   take the value 45 - 23 - 12 - 4 = 6. Just implementing a simple
   minded version of this derived rule meant the solver went from
   taking minutes to solve my sample grid to taking seconds (I can't
   remember the failure counts I'm afraid).

-- 
Piers Cawley <pdcawley at bofh.org.uk>
http://www.bofh.org.uk/