ANN: Sudoku Assistant

Alex Tweedly alex at tweedly.net
Sun Jul 31 13:11:58 EDT 2005


Jim Hurley wrote:

>>>
>>>  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.
>>
>>  Alex,
>>
>> 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 used the wrong word when I said "deterministic." What I should have 
> said was that puzzle 4 requires a *two* stage decision making process. 
> In the simpler puzzles at each step there is always one square in 
> which there is obviously only one possibility--a one stage decision 
> making process.
>
> In the fourth puzzle I reach a point where there is no square which 
> would allow only one character. But if I put one character in this 
> square then I will run into a contraction at a later stage. But if I 
> put another character into the square, I will be able to obtain a 
> unique solution. As you say, this is still a deterministic solution, 
> but a two stage deterministic process. Sorry for the poor description 
> of what I was trying to say.
>
But my (perhaps hard to follow) description at the tail end of the other 
email shows that you don't need to try one then the other - you can use 
the knowledge from two squares to eliminate a possibility from a third 
square. It's kind of a two-stage deduction - but you don't need to try 
one thing and then another.

>>  > (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.
>
>
>
> Yes. In fact I copied the puzzle to Photoshop  and erased all the 
> labels and printed the image. Maybe this would be a possible preference?
>
Rather than a preference, I made it a button "Hide uncompleted" or "Show 
uncompleted" so you can toggle between the two modes while working 
through a puzzle.

Now available on RevOnline (ver 1.2)

>>
>>>  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.
>
> I'll have to look at this again. It doesn't seem to complete all one 
> stage decisions. For example, after completing the Auto, it is clear 
> that the box in the second row, fifth column must be a 1. I suspect my 
> problem is that I don't understand the significance of the labels. 
> Life is full of things I don't understand.
>
It doesn't do all "one-stage" decisions. In each square it has a list of 
possible values - so for a blank puzzle, each square can still have any 
of the 9 digits. When you load a puzzle, some squares are changed to 
have a single digit. Clicking on such a square (or specifying a value 
for another square) causes the specified digit to be removed from all 
"peers" of the square (i.e. in the same row, col or 3x3). Auto simply 
applies that to all squares in turn.

The fact that square 5,2 "must" be a one (because there are no other 
squares in its 3x3 which still have one as a possible value) would 
require deduction - and my idea for the assistant was that it can do the 
"mechanical" part for you, and leave the user to do the deductions. 

Anyway - that's *why* it doesn't do that particular square for you. 
Would be easy enough to add a button to do that kind of simple deduction 
... be my guest :-)

The scripting for this puzzle isn't great (when I wrote it I didn't 
intend to give it to anyone else, so it's certainly not carefully 
written as I would do for a tutorial, or a product), but it's not 
terrible either. Dive in ....



-- 
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




More information about the use-livecode mailing list