Uniqueness

Advanced methods and approaches for solving Sudoku puzzles

Postby r.e.s. » Sun Sep 03, 2006 4:16 am

fermat wrote:
r.e.s. wrote:How could UR be "a shortcut to realizing an invalid puzzle"?

Well, if UR is valid, it is used and gets a grid with no solution, we are done, invalid puzzle.

I think that's what I just said (except for the "if UR is valid" part, which doesn't make sense -- it would be an invalid application of UR) ...
r.e.s. wrote:if UR produces a grid with no solution, then the puzzle doesn't have exactly one solution (is "invalid").


EDIT: Removed the extra "the" in my parenthetical reference to "if [the] UR is valid".
Last edited by r.e.s. on Sun Sep 03, 2006 1:25 am, edited 1 time in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby fermat » Sun Sep 03, 2006 4:38 am

r.e.s. wrote:
fermat wrote:
r.e.s. wrote:How could UR be "a shortcut to realizing an invalid puzzle"?

Well, if UR is valid, it is used and gets a grid with no solution, we are done, invalid puzzle.

I think that's what I just said (except for the "if the UR is valid" part, which doesn't make sense -- it would be an invalid application of UR) ...
r.e.s. wrote:if UR produces a grid with no solution, then the puzzle doesn't have exactly one solution (is "invalid").


Bad quote.

I said "if UR is valid".
fermat
 
Posts: 105
Joined: 29 March 2006

Postby r.e.s. » Sun Sep 03, 2006 5:26 am

fermat wrote:Bad quote.

I said "if UR is valid".

You mean the extra word "the" in my reference to "if the UR is valid"? If so, the quote has been corrected -- my comment applies either way.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby fermat » Sun Sep 03, 2006 5:29 am

r.e.s. wrote:
fermat wrote:Bad quote.

I said "if UR is valid".

You mean the extra word "the" in my reference to "if the UR is valid"? If so, the quote has been corrected -- my comment applies either way.


Not so, you are now stating that UR is always "lucky", when it works.
fermat
 
Posts: 105
Joined: 29 March 2006

Postby r.e.s. » Sun Sep 03, 2006 6:44 am

fermat wrote:
r.e.s. wrote:
fermat wrote:Bad quote.

I said "if UR is valid".

You mean the extra word "the" in my reference to "if the UR is valid"? If so, the quote has been corrected -- my comment applies either way.


Not so, you are now stating that UR is always "lucky", when it works.

That's incorrect. When you referred to these methods, in effect, as just picking one of multiple solutions, I pointed out that sometimes they will do so and sometimes they will not (and gave two examples where they do not) -- for a given puzzle with an unknown number of solutions, it would be only a guess as to whether such a method will or will not be consistent with a solution. I wrote ...
r.e.s. wrote:Just to dispel any notion that unique-solution strategies can be relied upon to "pick one of them" when there are multiple solutions ...
[...]
the blanket use of unique-solution strategies (i.e. when it isn't known whether there's a unique solution) is a kind of guessing -- it doesn't always lead to one of multiple solutions, even though it may just happen to do so for no legitimate reason.

"No legitimate reason" is of course a reference to not knowing (or it not being a given) whether there's exactly one solution -- a circumstance that prevents valid application of these methods in their standard form.

EDITS: Added the parenthetical reference to uniqueness as provisional information, as in what's given as part of the description of a puzzle.
Last edited by r.e.s. on Sun Sep 03, 2006 3:15 am, edited 2 times in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby fermat » Sun Sep 03, 2006 6:51 am

r.e.s. wrote:"No legitimate reason" is of course a reference to not knowing whether there's exactly one solution -- a circumstance that prevents valid application of these methods in their standard form.


OK, name any valid method when there is not exactly one solution.
fermat
 
Posts: 105
Joined: 29 March 2006

Postby RW » Sun Sep 03, 2006 6:57 am

Why is it so hard to understand there's no use even mentioning uniqueness technique in the same sentence as multiple solution puzzles? I repeat myself on the UR logic: If C = a then any solution must also have an alternate solution. In an unique puzzle - good, C<>a. If the puzzle potentially has multiple solution this is NO VALID LOGIC! The elimination may, or may not lead to a solution. Therefore it is just as good as any other guess or deduction based on the movement of the stars. If you get a solution, you don't know if it is unique (just as with any other guess), if you don't get a solution you don't know if the puzzle may have a solution (just as with any other guess). True, if you don't reach a solution, then you know that the puzzle cannot have an unique solution, but that is just in case the UR happens to lead to a contradiction. However, the UR can this way only prove the abscense of an unique solution, not that there is one, so you shouldn't use it anyway if that is your goal.

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby fermat » Sun Sep 03, 2006 7:00 am

If anyone still cares, I never thought that UR could always pick, or even suggest, one solution in a multiple solution puzzle, except the one I posted, which was asked for.

I am surprised that UR may be ever used to ruin a "good" puzzle.

If it ruins "bad" puzzles quickly it may be a tool for checking puzzle validity.
Last edited by fermat on Sun Sep 03, 2006 3:09 am, edited 1 time in total.
fermat
 
Posts: 105
Joined: 29 March 2006

Postby fermat » Sun Sep 03, 2006 7:05 am

RW wrote:Why is it so hard to understand there's no use even mentioning uniqueness technique in the same sentence as multiple solution puzzles? I repeat myself on the UR logic: If C = a then any solution must also have an alternate solution. In an unique puzzle - good, C<>a. If the puzzle potentially has multiple solution this is NO VALID LOGIC! The elimination may, or may not lead to a solution. Therefore it is just as good as any other guess or deduction based on the movement of the stars. If you get a solution, you don't know if it is unique (just as with any other guess), if you don't get a solution you don't know if the puzzle may have a solution (just as with any other guess). True, if you don't reach a solution, then you know that the puzzle cannot have an unique solution, but that is just in case the UR happens to lead to a contradiction. However, the UR can this way only prove the abscense of an unique solution, not that there is one, so you shouldn't use it anyway if that is your goal.

RW


To me UR is simply a pattern. X wing, swordfish, etc.

I never wonder whether the puzzle is valid. I should take exception for UR?

It is often a shortcut, it gets around (sometimes) techniques I don't know.)


You did not answer, RW, can it make a puzzle worse?
fermat
 
Posts: 105
Joined: 29 March 2006

Postby unkx80 » Sun Sep 03, 2006 7:45 am

According to this:
http://homepages.cwi.nl/~aeb/games/sudoku/solving18.html
"Every application of the above uniqueness argument discards an even number of solutions." (see bottom of page, and depending on how you interpret uniqueness arguments)
Therefore, if the sudoku has two solutions, then after applying the unique rectangle technique, you are left with no solutions.
unkx80
 
Posts: 7
Joined: 26 August 2006

Postby udosuk » Sun Sep 03, 2006 8:07 am

Ruud wrote:#1 is indeed a Sudoku-X
#3 is a DG Sudoku
#4 is a Windoku

These can all be solved by my program.

#2 could be a non-consecutive Sudoku, but I cannot fully solve it.

Well done Ruud!:)

Here is a link on how to solve #2...


I've never seen heated discussion between 2 persons take up 2 whole pages overnight...:!:

fermat wrote:OK, name any valid method when there is not exactly one solution.

Singles, pairs, triples, quads, locked candidates, all fishes, ...

Say the goal is to find all solutions to a multiple-solutional puzzle. I could safely apply the above techniques to help reaching that goal. They would never ruin the puzzle. But I would never apply any UR methods cause they could lead to no solution.

fermat wrote:If it ruins "bad" puzzles quickly it may be a tool for checking puzzle validity.

If UR tells you it is a bad puzzle, it must be a bad puzzle...
If UR tells you it is a good puzzle, you cannot trust it because it could be wrong - the puzzle could have other solutions...
I wonder how useful such a "tool" would be...:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ravel » Sun Sep 03, 2006 10:30 am

I am admiring your patience, r.e.s.:)

fermat wrote:OK, name any valid method when there is not exactly one solution.

It is easier to list the techniques, that are not valid, when the puzzle does not have a unique solution. The ones i know of are UR (all types), BUG, BUG lite, reversed BUG and Gurths symmetrical placement.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby RW » Sun Sep 03, 2006 9:40 pm

fermat wrote:I never wonder whether the puzzle is valid. I should take exception for UR?

It is often a shortcut, it gets around (sometimes) techniques I don't know.)

You did not answer, RW, can it make a puzzle worse?


I usually don't wonder either, if I find a non valid puzzle I don't bother to solve puzzles from the same source anymore.

It is indeed often a shortcut, URs and the other more advanced applications of uniqueness technique can usually be used to make eliminations in almost any puzzle.

As for if an UR can make a puzzle worse...? No. If the puzzle is valid, then the UR elimination brings you closer to the unique solution. If it isn't valid, then I don't see how you could make it any worse...

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Postby fermat » Sun Sep 03, 2006 10:20 pm

RW wrote:As for if an UR can make a puzzle worse...? No. If the puzzle is valid, then the UR elimination brings you closer to the unique solution. If it isn't valid, then I don't see how you could make it any worse...

RW


Thank you RW.
fermat
 
Posts: 105
Joined: 29 March 2006

Postby fermat » Sun Sep 03, 2006 10:22 pm

ravel wrote:It is easier to list the techniques, that are not valid, when the puzzle does not have a unique solution. The ones i know of are UR (all types), BUG, BUG lite, reversed BUG and Gurths symmetrical placement.


Thanks ravel, usefull info.
fermat
 
Posts: 105
Joined: 29 March 2006

PreviousNext

Return to Advanced solving techniques