SudoCue Users Forum Index SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Unique unique?
Goto page 1, 2  Next
 
Post new topic   Reply to topic    SudoCue Users Forum Index -> Puzzles
View previous topic :: View next topic  
Author Message
zoltag
Expert
Expert


Joined: 01 Apr 2006
Posts: 126

PostPosted: Sun Apr 30, 2006 12:56 pm    Post subject: Unique unique? Reply with quote

I used optimize on a puzzle and came up with this unique puzzle that has 3 patterns hitting on a single square!

Code:

.------------------.------------------.------------------.
| 2     9     5    | 8     3     4    | 6     7     1    |
| 3     16    8    | 16    7     9    | 24    24    5    |
| 16    4     7    | 16    5     2    | 3     8     9    |
:------------------+------------------+------------------:
| 9     16    4    | 2     8     3    | 5     16    7    |
| 7     5     23   | 4     6     1    | 9     23    8    |
| 16    8     23   | 7     9     5    | 24    12346 36   |
:------------------+------------------+------------------:
| 4     7     9    | 5     2     8    | 1     36    36   |
| 8     3     1    | 9     4     6    | 7     5     2    |
| 5     2     6    | 3     1     7    | 8     9     4    |
'------------------'------------------'------------------'


Here is the puzzle before any solving.
Code:
2 . 5 | . . . | 6 . 1
3 . . | . 7 9 | . . 5
. . . | . . . | . . .
---------------------
. . 4 | 2 8 3 | 5 . .
7 . . | . . . | . . 8
. . . | . 9 . | . . .
---------------------
. . . | 5 . 8 | . . .
. . 1 | . . . | 7 . .
. 2 . | . . . | . 9 .
Back to top
View user's profile Send private message
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Sun Apr 30, 2006 1:52 pm    Post subject: Reply with quote

Hi zoltag,

when you use the "Optimize" function, first disable the "BUG" and "Uniqueness Test" solving techniques. These techniques lead to false results. I will put this on the list to be corrected in the next release.

Ruud.
Back to top
View user's profile Send private message Send e-mail
zoltag
Expert
Expert


Joined: 01 Apr 2006
Posts: 126

PostPosted: Sun Apr 30, 2006 2:31 pm    Post subject: Reply with quote

Hi Ruud,

I don't understand why the uniqueness isn't valid here.

(I already have "bug" turned off.)
Back to top
View user's profile Send private message
keith
Hooked
Hooked


Joined: 07 Feb 2006
Posts: 35
Location: near Detroit, Michigan, USA

PostPosted: Sun Apr 30, 2006 5:02 pm    Post subject: Valid? Reply with quote

According to Sudoku Susser, this is not a valid puzzle (it does not have a unique solution):
Code:



+----------------------+----------------------+----------------------+
| 2      4789   5      | 348    34     4      | 6      3478   1      |
| 3      1468   68     | 1468   7      9      | 248    248    5      |
| 14689  146789 6789   | 13468  123456 12456  | 23489  23478  23479  |
+----------------------+----------------------+----------------------+
| 169    169    4      | 2      8      3      | 5      167    679    |
| 7      13569  2369   | 146    1456   1456   | 12349  12346  8      |
| 1568   13568  2368   | 1467   9      14567  | 1234   123467 23467  |
+----------------------+----------------------+----------------------+
| 469    34679  3679   | 5      12346  8      | 1234   12346  2346   |
| 45689  345689 1      | 3469   2346   246    | 7      234568 2346   |
| 4568   2      3678   | 13467  1346   1467   | 1348   9      346    |
+----------------------+----------------------+----------------------+



I got this far without using uniqueness:

Code:



+-------------------+-------------------+-------------------+
| 2     9     5     | 8     3     4     | 6     7     1     |
| 3     16    8     | 16    7     9     | 24    24    5     |
| 16    4     7     | 16    5     2     | 3     8     9     |
+-------------------+-------------------+-------------------+
| 9     16    4     | 2     8     3     | 5     16    7     |
| 7     5     23    | 4     6     1     | 9     23    8     |
| 16    8     23    | 7     9     5     | 24    12346 36    |
+-------------------+-------------------+-------------------+
| 4     7     9     | 5     2     8     | 1     36    36    |
| 8     3     1     | 9     4     6     | 7     5     2     |
| 5     2     6     | 3     1     7     | 8     9     4     |
+-------------------+-------------------+-------------------+



Keith
Back to top
View user's profile Send private message
zoltag
Expert
Expert


Joined: 01 Apr 2006
Posts: 126

PostPosted: Sun Apr 30, 2006 5:15 pm    Post subject: Re: Valid? Reply with quote

keith wrote:
According to Sudoku Susser, this is not a valid puzzle (it does not have a unique solution).
Keith


From where you got to, applying uniqueness to R6 C8 you get
Code:
.---------.---------.---------.
| 2  9  5 | 8  3  4 | 6  7  1 |
| 3  16 8 | 16 7  9 | 24 24 5 |
| 16 4  7 | 16 5  2 | 3  8  9 |
:---------+---------+---------:
| 9  16 4 | 2  8  3 | 5  6  7 |
| 7  5  23| 4  6  1 | 9  23 8 |
| 6  8  23| 7  9  5 | 24 1  36|
:---------+---------+---------:
| 4  7  9 | 5  2  8 | 1  36 36|
| 8  3  1 | 9  4  6 | 7  5  2 |
| 5  2  6 | 3  1  7 | 8  9  4 |
'---------'---------'---------'


Which is trivial to solve. I think Ruud may mean that optimizing can be invalid, or else I have found a new case of uniqueness!
Back to top
View user's profile Send private message
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Sun Apr 30, 2006 6:20 pm    Post subject: Reply with quote

zoltag wrote:
Hi Ruud,

I don't understand why the uniqueness isn't valid here.

(I already have "bug" turned off.)


Optimize works as follows:

1. Remove a given number.
2. Solve the puzzle.
3. While the puzzle has a unique solution, continue at 1. (remove more clues)
4. With multiple solutions, restore the last number and remove another given number.
5. Continue until all possible reductions have been tested.
6. Select the puzzle with the lowest number of clues.

Step 2. is the problem when uniqueness test is enabled. This solving method only works when we know for sure that a unique solution is present. If not, the test can give a false positive. This happened here.

I had a similar problem when I first implemented uniqueness tests. When I had the solver active while the clues were entered, it could also return a false positive before all clues were processed.

Ruud.
Back to top
View user's profile Send private message Send e-mail
zoltag
Expert
Expert


Joined: 01 Apr 2006
Posts: 126

PostPosted: Sun Apr 30, 2006 6:25 pm    Post subject: Reply with quote

Ruud wrote:
[


Step 2. is the problem when uniqueness test is enabled. This solving method only works when we know for sure that a unique solution is present. If not, the test can give a false positive. This happened here.


Ruud.


I'm still puzzled, this is not a false positive. Is it?

Edited to add:

I did start from a puzzle with one solution.

As long as I do that I can optimize with uniquenees on?
Back to top
View user's profile Send private message
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Tue May 02, 2006 1:30 pm    Post subject: Maybe I can explain it Reply with quote

zoltag wrote:
I'm still puzzled, this is not a false positive. Is it?

Yes, you obtained a "false positive" when you tried to optimize the puzzle with "uniqueness" turned on.

The puzzle you posted has at least five "solutions", as follows.
Code:
Case 1A -- assume "uniqueness" at r6c8.
+-------------------+-------------------+-------------------+
| 2     9     5     | 8     3     4     | 6     7     1     |
| 3     1*    8     | 6*    7     9     | 2*    4*    5     |
| 6*    4     7     | 1     5     2     | 3     8     9     |
+-------------------+-------------------+-------------------+
| 9     6*    4     | 2     8     3     | 5     1*    7     |
| 7     5     3*    | 4     6     1     | 9     2*    8     |
| 1*    8     2*    | 7     9     5     | 4*    36    36    |
+-------------------+-------------------+-------------------+
| 4     7     9     | 5     2     8     | 1     36    36    |
| 8     3     1     | 9     4     6     | 7     5     2     |
| 5     2     6     | 3     1     7     | 8     9     4     |
+-------------------+-------------------+-------------------+

This grid represents two different solutions, since we can clearly permute the digits "3" and "6" in r6&7c8&9. I obtained these by assuming that the pair {2, 4} is excluded at r6c8, and then arbitrarily setting r6c1 = 1.
Code:
Case 1B -- assume "uniqueness" at r6c8
+-------------------+-------------------+-------------------+
| 2     9     5     | 8     3     4     | 6     7     1     |
| 3     6*    8     | 1*    7     9     | 2     4     5     |
| 1*    4     7     | 6*    5     2     | 3     8     9     |
+-------------------+-------------------+-------------------+
| 9     1*    4     | 2     8     3     | 5     6*    7     |
| 7     5     3*    | 4     6     1     | 9     2     8     |
| 6*    8     2*    | 7     9     5     | 4     1*    3*    |
+-------------------+-------------------+-------------------+
| 4     7     9     | 5     2     8     | 1     3*    6*    |
| 8     3     1     | 9     4     6     | 7     5     2     |
| 5     2     6     | 3     1     7     | 8     9     4     |
+-------------------+-------------------+-------------------+

This grid represents a third "solution" -- it's exactly like 1A above, except that I arbitrarily set r6c1 = 6. Notice that this eliminated the duplicative rectangle in r6&7c8&9.
Code:
Case 2 -- Do not assume uniqueness at r6c8
+-------------------+-------------------+-------------------+
| 2     9     5     | 8     3     4     | 6     7     1     |
| 3     1*    8     | 6*    7     9     | 24    24    5     |
| 6*    4     7     | 1*    5     2     | 3     8     9     |
+-------------------+-------------------+-------------------+
| 9     6*    4     | 2     8     3     | 5     1*    7     |
| 7     5     2*    | 4     6     1     | 9     3*    8     |
| 1*    8     3*    | 7     9     5     | 24    24    6*    |
+-------------------+-------------------+-------------------+
| 4     7     9     | 5     2     8     | 1     6*    3*    |
| 8     3     1     | 9     4     6     | 7     5     2     |
| 5     2     6     | 3     1     7     | 8     9     4     |
+-------------------+-------------------+-------------------+

Here is another pair of "solutions", which I obtained by eliminating the possibilities {1, 3, 6} from r6c8 and then resolving the rest of the squares. Clearly we can permute the values "2" and "4" around the corners of r2&6c7&8.

zoltag wrote:
I did start from a puzzle with one solution.

As long as I do that I can optimize with uniqueness on?

No. You must turn "uniqueness" off before you run the optimize function.

The problem is not with the puzzle you started with, zoltag. The problem is in the SudoCue program, which doesn't know when to stop optimizing a particular puzzle if the "uniqueness" test is turned on. Clearly any puzzle can be rendered invalid by removing too many clues -- after all, if we removed all the clues the puzzle would certainly be indeterminate! dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
zoltag
Expert
Expert


Joined: 01 Apr 2006
Posts: 126

PostPosted: Tue May 02, 2006 3:47 pm    Post subject: Re: Maybe I can explain it Reply with quote

David Bryant wrote:
zoltag wrote:
I'm still puzzled, this is not a false positive. Is it?


Code:
Case 1B -- assume "uniqueness" at r6c8
+-------------------+-------------------+-------------------+
| 2     9     5     | 8     3     4     | 6     7     1     |
| 3     6*    8     | 1*    7     9     | 2     4     5     |
| 1*    4     7     | 6*    5     2     | 3     8     9     |
+-------------------+-------------------+-------------------+
| 9     1*    4     | 2     8     3     | 5     6*    7     |
| 7     5     3*    | 4     6     1     | 9     2     8     |
| 6*    8     2*    | 7     9     5     | 4     1*    3*    |
+-------------------+-------------------+-------------------+
| 4     7     9     | 5     2     8     | 1     3*    6*    |
| 8     3     1     | 9     4     6     | 7     5     2     |
| 5     2     6     | 3     1     7     | 8     9     4     |
+-------------------+-------------------+-------------------+

This grid represents a third "solution" -- it's exactly like 1A above, except that I arbitrarily set r6c1 = 6. Notice that this eliminated the duplicative rectangle in r6&7c8&9.


r6c1 must be 6 since uniqueness made r6c8 a 1. The puzzle is trivial, with one solution, at that point.
Back to top
View user's profile Send private message
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Tue May 02, 2006 5:37 pm    Post subject: I can't spell it out any more clearly Reply with quote

zoltag wrote:
r6c1 must be 6 since uniqueness made r6c8 a 1. The puzzle is trivial, with one solution, at that point.

I'm not sure how to say this. You're wrong, zoltag. The "uniqueness" technique can only be used if the puzzle has a unique solution.

This puzzle has five solutions, so simple logic tells us that the "uniqueness" technique cannot be applied. I've displayed all five of the solutions for you. You can check them yourself and see that all five of them satisfy the initial set of clues and also satisfy the rules of Sudoku. I really can't spell it out any more clearly than that. dcb

PS The "uniqueness" technique operates by saying "if the solution is unique, then this value must go here." Logic says that if the premise is false, then the conclusion is not reliably true. In other words, if you just assume that 1 = 2, then you can "prove" any other nonsensical arithmetical statement you care to cook up.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
zoltag
Expert
Expert


Joined: 01 Apr 2006
Posts: 126

PostPosted: Tue May 02, 2006 5:50 pm    Post subject: Re: I can't spell it out any more clearly Reply with quote

David Bryant wrote:


This puzzle has five solutions, so simple logic tells us that the "uniqueness" technique cannot be applied. I've displayed all five of the solutions for you. You can check them yourself and see that all five of them satisfy the initial set of clues and also satisfy the rules of Sudoku. I really can't spell it out any more clearly than that. dcb


I guess I truly don't understand the technique. I had assumed that all puzzles requiring uniqueness do have more than one solution and that you used uniqueness to eliminate all but one of those.
Back to top
View user's profile Send private message
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Tue May 02, 2006 10:37 pm    Post subject: What people mean by "uniqueness" Reply with quote

zoltag wrote:
I guess I truly don't understand the technique. I had assumed that all puzzles requiring uniqueness do have more than one solution and that you used uniqueness to eliminate all but one of those.

You're right, zoltag. You don't quite understand what Sudoku authors mean by the "uniqueness technique." Maybe this explanation will be helpful.

A well-formed Sudoku puzzle has exactly one solution. Sometimes a position will arise (usually involving a rectangle) that allows one to reason as follows.

-- I know the solution is unique (basically, because the author of this puzzle says the solution is unique, and I trust him to be right about that).

-- If I place a particular value right here (at one corner of the rectangle, say) then the resulting solution would not be unique (because I could place the values abab around the corners of the rectangle, but baba would also fit).

-- Therefore I can't place this particular value right here, and I can eliminate it from the list of candidates for this cell.

There are a couple of interesting discussions of this technique in another forum -- here and also over here. Then, if you really want to get sick of the topic, you can read even longer and more pretentious arguments right here and also over here.

I'll try to scare up a useful example sometime soon and use it to illustrate how one arrives at a contradiction by assuming that more than one solution exists (in a well-formed puzzle that includes a "uniqueness" pattern). dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
zoltag
Expert
Expert


Joined: 01 Apr 2006
Posts: 126

PostPosted: Tue May 02, 2006 11:54 pm    Post subject: Re: What people mean by "uniqueness" Reply with quote

David Bryant wrote:

There are a couple of interesting discussions of this technique in another forum -- here and also over here. Then, if you really want to get sick of the topic, you can read even longer and more pretentious arguments right here and also over here.


Wow, thanks for the links. The last one pretty much covers this puzzle the best. I was cheered, somewhat, to see that I am not alone in stumbling at this sort of erroneous puzzle.

There were examples in the thread that show "broken" puzzles like the above and proper puzzles in which there is always just one solution.
Back to top
View user's profile Send private message
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Wed May 03, 2006 4:50 pm    Post subject: Here's another example Reply with quote

zoltag wrote:
Wow, thanks for the links.

You're welcome. I'm glad to help. Smile

This example may be redundant, but I said I'd post something, so here it is. This is drawn from Ruud's "nightmare" puzzle for Wednesday, 3 May, 2006.
Code:
  9     3    246    7    25     1    58    24    268
  1     5    26     3     8     4     7     9    26
 24     8     7     9    25     6    135   124   23
  3     7    28     6     1    289   89     5     4
 25     9   1258    4     7    28    138    6    238
  6     4    128    5     3    289   189   12     7
  7     1     9     2     6     3     4     8     5
 45     2    45     8     9     7     6     3     1
  8     6     3     1     4     5     2     7     9

This is the position I reached after working on the puzzle for a while. A "non-unique rectangle" is beginning to take shape in r1&2, c3&9. We can eliminate the "4" at r1c3 with a simple forcing chain.

A. r1c3 = 4 ==> r1c8 = 2 ==> r2c9 = 6 ==> r1c9 = 8
B. r1c3 = 4 ==> r1c8 = 2 ==> r1c5 = 5 ==> r1c7 = 8

But we can't have two "8"s in row 1, so r1c3 <> 4. Now the grid looks like this.
Code:
  9     3    26     7    25     1    58    24    268
  1     5    26     3     8     4     7     9    26
 24     8     7     9    25     6    135   124   23
  3     7    28     6     1    289   89     5     4
 25     9   1258    4     7    28    138    6    238
  6     4    128    5     3    289   189   12     7
  7     1     9     2     6     3     4     8     5
 45     2    45     8     9     7     6     3     1
  8     6     3     1     4     5     2     7     9

To avoid the "deadly pattern" we must set r1c9 = 8, and the rest of the puzzle falls out pretty quickly. But since the solution to the puzzle is unique, there must be another way to solve it. In this case we can make the eliminations resulting from the {2, 6} pair in column 3, and the puzzle is a piece of cake. But I'd like to illustrate one other principle here.

We can usually avoid making the "uniqueness" assumption by picking one of the cells that's "conjugate" to the "unique" corner of the rectangle and reasoning our way to a contradiction. In this case the "unique" corner is r1c9, and the two "conjugate" cells (which might also contain the digit 8) are r1c7 and r5c9. Notice how assuming that either one of these is "8" leads to a contradiction.

A. r1c7 = 8 ==> r4c7 = 9 ==> r6c7 = 1
B. {2, 6} in c3r1&2 ==> r4c3 = 8 ==> r6c3 = 1

There can't be two "1"s in row 6, so r1c7 <> 8.

C. r5c9 = 8 ==> r5c7 = 3 ==> r5c3 = 1 (only spots left for "3", then "1", in row 5).
D. {2, 6} in c3r1&2 ==> r4c3 = 8 ==> r6c3 = 1

There can't be two "1"s in column 3, so r5c9 <> 8.

The logic for contradictions connected with "non-unique rectangles" isn't always as clean as in this example. But I've had a lot of fun with Ruud's puzzles (where these rectangles pop up pretty frequently) by consciously trying to avoid making the "uniqueness" assumption, and using the conjugate cells to reach the same conclusion (e.g., r1c9 = 8) via the back door. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
keith
Hooked
Hooked


Joined: 07 Feb 2006
Posts: 35
Location: near Detroit, Michigan, USA

PostPosted: Wed May 03, 2006 10:47 pm    Post subject: A swamp of semantics Reply with quote

David,

So, we recognize a UR (and its result) and then we find another way to reason the same result.

This is logically defensible as not using Uniqueness?

Actually, it seems to me: Assume the deadly pattern, if it is a unique puzzle, you should pretty soon find a contradiction.

(And then we'll have to counsel you about using T&E on UR's*. Can there be a greater sin?)

Best wishes,
Keith

* Trial and Error on Unique Rectangles.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    SudoCue Users Forum Index -> Puzzles All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group