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
_______________________________________________
use-revolution mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution
