"Ian"  wrote in message
news:1110227357.499288.54450{at}f14g2000cwb.googlegroups.com...
> However it won't solve last Friday's telegraph. I managed to solve
> Thursday's by hand, using a series of set conversions intersection and
> union (after I'd spent about half an hour on it,) but then I couldn't
> remember what I did to put the rule in to the code.
>
> Also Friday's was excellent, I managed to invent a rule using
> exclusions to solve it, but it required a lot of paper and about two
> hours, in a semi-intelligent brute force way. Unfortunately the rule
> doesn't translate well to SQL. I'm so happy, because my father in law
> couldn't solve it, and he's a seriously bright bloke.
>
> As for an array based system, they work quite well, because the further
> down the array you go, the more hits you get to prove a failure,
> because the rows and boxes counter possibilities.
>
> I still have several simple rules to add, such as "when there are two
> boxes in a row with the same two digits as their only possibilities,
> then there can be no other entries in the row with those digits" etc,
> and quite a few simple but deep logical exclusions.

Yes that was an exact example of the kind of logic I was considering. I was
hoping to get down to some experimentation over the weekend just passed -
but unfortunately for the last few days I have been laid low by a 'tummy
bug' (allegedlly a virus that apparently showed itself first in our local
hospital (where else!!) and ended up with the whole ward involved being
closed down).
I am working on the theory that it may be possible to solve a soduko by
relentless application of the basic soduko rules starting at the first
'cell' (uppermost left hand side of grid) and 'interrogating' the cell to
see if:
a: is it blank -> if so check each number 1-9 so that said candidate is not
already in the current column,row or box - whichever number passes the tests
becomes 'it' for that cell.
b: is it occupied by a valid number (1-9) -> if so create 'pointer' so that
it does not become a 'candidate' in the execution of logic as described in
the above described tests.
Of course designing the traversal routines so that the arrays are correctly
checked and populated is a little tricky especially if you want to create
code that is easy to read! Having said that your remarks below have given me
pause for thought - having not even yet tried to solve a soduko manually I
can now see that I have being making a perhaps erroneous assumption.


>
> I ultimately believe that the majority of these can be constructed to
> force some kind of brute force solution, (it's just a guess of course,)
> but I can envisage cases where, 20 odd numbers remaining, there are
> multiple possibilities where you don't know you've failed until you're
> on the last two digits.
>
My idea was that it may not matter what numbers are already in the grid when
it comes to solving the puzzle (i.e. they would be just taken by case b
logic) and that logical traversal of the grid applying the rules from the
perspective of every cell visited would always result (quite swiftly) in a
solution. I can see where I could be wrong - i.e. in cases where a cell
could be filled by more than one candidate that passes the rules test and my
'logic' would simply take the first one it found and use it!! I noted that
some already written 'solvers' allegedly can take several minutes to solve
some puzzles - now either they have written some very inefficient code OR
like you suspect there is a strong element of 'placement' that complicates
things somewhat!




--- UseNet To RIME Gateway {at} 3/8/05 4:08:10 AM ---