ANN: Sudoku Assistant

[Alex Tweedly]

Jim Hurley wrote:

> Alex,
>
> Thanks for the puzzle. Lots of fun. Dell Crosswords has a full page of 
> these every month, though none as tough a your last. They generally 
> are deterministic all the way to the end. Your number four requires 
> assuming a solution at one point near the end and discovering a 
> contradiction if the guess was wrong--proof by contradiction.

No, it doesn't require that. There's a perfectly deterministic technique 
that can solve puzzle #4 - I'll append a brief description of  it to the 
end of this message - but beware it uses puzzle #4 to demonstrate it, so 
don't read all the way to the end unless you want to read that ...

> (I must confess that the labels make it more difficult for me--harder 
> to see what is filled in and what isn't.)
>
Sorry Jim I'm not sure I follow - do you mean you'd prefer to have blank 
squares for every space that has not yet been determined (rather than 
the set of possible values) ?   That would seem to me much less helpful 
- but I'll try it and see how it looks.

> I am interested in what algorithm is used under the "Auto" button.
>
Code is all there for you to look at :-)
But all it does is look at each square in turn, and if it already knows 
that there is only a single value possible, then it removes that value 
from the rest of the square's row,col and 3x3 square.   It could repeat 
that scan (very occasionally you can find a case where a square has been 
already examined while multiple values were possible, and which reduces 
to a single one, and is required to complete the puzzle) - but it 
doesn't even do that.

> If you also enjoy Cryptogram puzzles, I have one which retrieves 4 
> quotes from the web every day and encodes them for your decoding 
> pleasure. It is my daily diagnostic tool to reveal the onset of 
> senility. You can take a look at:
>
>      go stack url 
> "http://home.infostations.net/jhurley/DailyCryptoquote.rev"
>
> It's a 450k file. It contains a dictionary for a decoder utility.

Thanks Jim. I'll take a look at that - though I'm more likely to write a 
stack to solve them than I am to do it myself.

I have not yet found any "puzzle" that is more challenging or 
stimulating that programming.







scroll beyond here only if you want to read solving techniques  ....








In Puzzle #4, assuming you've hit the "Auto" button (or worked through 
yourself to the point where all single-valued squares have been used to 
eliminate their peers), you are left with a number of possibilities.

Look at squares 8,7 and 8,9. They both contain only two possibilities 1 
and 6. And they are both in the same column.
One of them must contain one of the two values, and the other must 
contain the other value.

Therefore no other square in column 8 can contain either 1 or 6.

This allows us to (deterministically - no guessing) eliminate "6" from 
the set of possible values for square 8,2 - leaving only a single value 
of 8.   Fill that in and you're done.

There is another such "common pair" in squares 9,2 and 9,3 - which 
allows you to eliminate the value 5 from 9,7  - but there are still 
multiple values left.

However - this allows yet another technique.  The bottom right square 
now has only two places were the 5 can go - 7,7 and 7,9; since they are 
both in col 7, we know that the 5 in col 7 is in one or other of those 
places - i.e. it is in the lower, right 3x3 square. Therefore, it can be 
eliminated from 7,2 - leaving only 6 or 8 to go there.

That is now a common pair 7,2 and 8,2 have either 6 or 8.  So eliminate 
the 8 from 6,2 leaving only 5 to go there, and you make a substantial 
step forward. Although you're not yet done, it's straight forward from 
then on.

-- 
Alex Tweedly       http://www.tweedly.net



-- 
No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.338 / Virus Database: 267.9.6/59 - Release Date: 27/07/2005