Friday, 29th March 2024
Puzzles Solved Yesterday: 131
Forum Index
 
uniqueness
kiwigeek
Kwon-Tom Noob
Puzzles: 4
Posted - 2006.06.01 04:48:59
I've been going through the archives looking at patterns, because I have two puzzles from other sources I'm really stuck on. Correct me if I'm wrong, but I think the "uniqueness argument" or "highlander" is that if a configuration could result in two possible solutions, it must be wrong, because every puzzle has only one solution.

So one pattern I saw was


According to one discussion, there can't be Xs on the inside of both 1s, because there's no information to determine whether the 2 had lines on the south and west, or north and east.

So therefore the 1s must both have a line toward the 2, and Xs on the outside corners. However, now I see no information on whether the lines on the 2 are parallel or perpendicular, or which sides they go on. Can somebody give me a hint? I must be really dense, because everybody else seems to get this...
prj
Kwon-Tom Obsessive
Puzzles: 2356
Best Total: 18m 20s
Posted - 2006.06.01 05:35:23
Quote:
Originally Posted by kiwigeek
Correct me if I'm wrong, but I think the "uniqueness argument" or "highlander" is that if a configuration could result in two possible solutions, it must be wrong, because every puzzle has only one solution.

Right.  More precisely: if two solutions are guaranteed to be possible, so there's no way you could ever rule out just one, then something previous must be wrong.

Quote:
Originally Posted by kiwigeek
According to one discussion, there can't be Xs on the inside of both 1s, because there's no information to determine whether the 2 had lines on the south and west, or north and east.

That's right, if the four cells surrounding the 2 are empty.  If any of them have numbers, then those numbers could make one solution possible and the other not.

Quote:
Originally Posted by kiwigeek
So therefore the 1s must both have a line toward the 2, and Xs on the outside corners. However, now I see no information on whether the lines on the 2 are parallel or perpendicular, or which sides they go on.

Sometimes it depends on what other information you can get from the rest of the puzzle.  For perpendicular vs. parallel, one rule that may help is that if you draw a (not necessarily straight) line that starts and ends outside the puzzle (or that is a closed loop itself), it must cross the puzzle loop an even number of times.  So if you draw a line that goes through the 2 horizontally, through the two vertical sides of the 2, and if that is the only spot where you don't know whether your line is crossing the puzzle loop, then based on the number of crossings you have elsewhere, you'll know whether the two vertical sides are the same (because you already have an even number of crossings) or odd (because you have an odd number so far, and you need exactly one more to make the total even).
kiwigeek
Kwon-Tom Noob
Puzzles: 4
Posted - 2006.06.01 05:47:41
This "drawing a loop" is interesting, but I'm having trouble getting my brain around it. Could you give an example where you could use this to solve a puzzle, or to place some lines/Xs? Thanks.
Last edited by kiwigeek - 2006.06.01 05:48:32
PuzzleLover
Kwon-Tom Obsessive
Puzzles: 1033
Best Total: 38m 17s
Posted - 2006.06.02 07:05:25
ONLY if a unique solution is guaranteed can you use a Highlander argument.  This is true of foilman's puzzles and a couple of other sites.

But I don't know that basic slither link offers any guarantee of uniqueness.  In the initial example in this thread, I bet one could desing a puzzle with exactly two solutions, using the non-Highlander choices in this example.  In such a puzzle, applying a Highlander deduction would lead to a nonsolution of a solvable puzzle.

Sudoku has the same issues with using deductions from uniqueness.
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s
Posted - 2006.06.02 10:40:40
Quote:
Originally Posted by puzzlelover
ONLY if a unique solution is guaranteed can you use a Highlander argument.  This is true of foilman's puzzles and a couple of other sites.  But I don't know that basic slither link offers any guarantee of uniqueness.

I've never seen a non-unique slither-link, and I hope I never do. You couldn't solve such a beast logically if the two solutions had enough differences that you couldn't read one possibility all the way to the end - you'd be forced to guess!
kiwigeek
Kwon-Tom Noob
Puzzles: 4
Posted - 2006.06.03 06:43:57
I agree with Procrastinator; I wouldn't even bother with any logic puzzle that didn't guarantee uniqueness.
PuzzleLover
Kwon-Tom Obsessive
Puzzles: 1033
Best Total: 38m 17s
Posted - 2006.06.03 08:49:55
A non-unique slither link puzzle with wildly different solutions would be a poor puzzle indeed.  But one with only local differences would mke a nice puzzle and would be quite readable.

I've used uniqueness deductions on occasion.  But it always feels like cheating, and they shouldn't be neccesary.
Last edited by PuzzleLover - 2006.06.03 08:50:16
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s
Posted - 2006.06.20 08:10:37
Quote:
Originally Posted by puzzlelover
A non-unique slither link puzzle with wildly different solutions would be a poor puzzle indeed.  But one with only local differences would mke a nice puzzle and would be quite readable.

This discussion has come up again, and we've seen a non-unique puzzle posted for the first time, so I'm wondering what you made of it?
kiwigeek
Kwon-Tom Noob
Puzzles: 4
Posted - 2006.06.20 08:25:00
Which puzzle is non-unique?? There should be a warning...
PuzzleLover
Kwon-Tom Obsessive
Puzzles: 1033
Best Total: 38m 17s
Posted - 2006.06.20 09:00:57
Quote:
Originally Posted by procrastinator
Quote:
Originally Posted by puzzlelover
A non-unique slither link puzzle with wildly different solutions would be a poor puzzle indeed.  But one with only local differences would mke a nice puzzle and would be quite readable.
This discussion has come up again, and we've seen a non-unique puzzle posted for the first time, so I'm wondering what you made of it?
I think I know the thread you're referring to.  There are several puzzles there.  Which one did you have in mind?

FWIW, http://www.puzzle-loop.com/ does NOT specify uniqueness in their slither link rules.  I believe the puzzles they generate happen to be unique, but that's not given.  I also looked for a unique solution rule in the home page of this site.  I didn't see one mentioned in either the Tutorial or the FAQ.  Of course foilman has assured uniqueness in the forum discussions.

It's interesting the "rules" that some people assume but that don't exist.  E.g., many players of dots and boxes assume that if you can take a box, you must.  This isn't really a rule of dots and boxes, and players that blindly follow this non-rule can be slaughtered by players that don't.  Imperfect analogy for solitaire puzzles, but a good analogy for possiblities that can be ruled out by too narrow a viewpoint.

I've thought a bit more on viable non-unique slither link puzzles.  A slither link puzzle with a "globally unique" solution but with local non-unique variations would make a very nice type of puzzle.  I don't have a general definition of "globally unique", but if the "local variation" a puzzle allows is well defined, that gives a subset of puzzles with globally unique solutions.  This would open up an interesting new set of challenges for both puzzle generators and solvers.

Some example tractable limits on local variation:
A.  Consider any paths that connect opposite corners of a 1x1 box with 2 sides of the box as equivalent (whether or not the box has 2 as a clue).
B.  For some N and all M <= N, consider any path connecting opposite corners of a 1xM box with a path in the box or its edges as equivalent.
m2e
Kwon-Tom Obsessive
Puzzles: 607
Best Total: 16m 43s
Posted - 2006.06.20 09:19:42
Quote:
Originally Posted by puzzlelover
FWIW, http://www.puzzle-loop.com/ does NOT specify uniqueness in their slither link rules.
on a side note, www.puzzle-nonograms.com (a sister site) doesnt completely explain the rules either (which kept stuffing me up)
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s
Posted - 2006.06.20 09:42:46
Quote:
Originally Posted by puzzlelover

Quote:
Originally Posted by procrastinator
we've seen a non-unique puzzle posted for the first time, so I'm wondering what you made of it?

I think I know the thread you're referring to.  There are several puzzles there.  Which one did you have in mind?

It's the only one in the "Hi, I'm your new member" thread. But it's 6x6, so it was posted in the format of the loopy program to read the format.

Quote:
Originally Posted by puzzlelover

FWIW, http://www.puzzle-loop.com/ does NOT specify uniqueness in their slither link rules.  I believe the puzzles they generate happen to be unique, but that's not given. 

You never need the uniqueness rule to solve the puzzle, so I guess that's a way of simplifying what the solver has to read before getting started?

Quote:
Originally Posted by puzzlelover

I don't have a general definition of "globally unique", but if the "local variation" a puzzle allows is well defined, that gives a subset of puzzles with globally unique solutions.  This would open up an interesting new set of challenges for both puzzle generators and solvers.

Hmmm, I guess we'd develop patterns based on not violating the new "global uniqueness" rules. Sorry, but I think such a relaxation would sacrifice the elegance of the puzzle (the emergence of complex patterns from such simple rules is what makes it compelling to me) for no real reward.
procrastinator
Kwon-Tom Obsessive
Puzzles: 1083
Best Total: 12m 56s
Posted - 2006.06.20 09:44:52
Quote:
Originally Posted by kiwigeek
Which puzzle is non-unique?? There should be a warning...

Relax, it wasn't a daily puzzle. It was posted by Jankonyex in a forum thread, and there was a warning.

Forum Index