Unique unique?

Interesting puzzles can be posted here
zoltag
Expert
Expert
Posts: 126
Joined: Sat Apr 01, 2006 10:57 pm

Unique unique?

Post by zoltag »

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

Code: Select all

.------------------.------------------.------------------.
| 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: Select all

2 . 5 | . . . | 6 . 1
3 . . | . 7 9 | . . 5
. . . | . . . | . . .
---------------------
. . 4 | 2 8 3 | 5 . .
7 . . | . . . | . . 8
. . . | . 9 . | . . .
---------------------
. . . | 5 . 8 | . . .
. . 1 | . . . | 7 . .
. 2 . | . . . | . 9 .
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

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.
zoltag
Expert
Expert
Posts: 126
Joined: Sat Apr 01, 2006 10:57 pm

Post by zoltag »

Hi Ruud,

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

(I already have "bug" turned off.)
keith
Hooked
Hooked
Posts: 35
Joined: Tue Feb 07, 2006 3:13 am
Location: near Detroit, Michigan, USA

Valid?

Post by keith »

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

Code: Select all



+----------------------+----------------------+----------------------+
| 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: Select all



+-------------------+-------------------+-------------------+
| 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
zoltag
Expert
Expert
Posts: 126
Joined: Sat Apr 01, 2006 10:57 pm

Re: Valid?

Post by zoltag »

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: Select all

.---------.---------.---------.
| 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!
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

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.
zoltag
Expert
Expert
Posts: 126
Joined: Sat Apr 01, 2006 10:57 pm

Post by zoltag »

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?
David Bryant
Gold Member
Gold Member
Posts: 86
Joined: Fri Jan 20, 2006 6:21 pm
Location: Denver, Colorado
Contact:

Maybe I can explain it

Post by David Bryant »

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: Select all

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: Select all

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: Select all

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
zoltag
Expert
Expert
Posts: 126
Joined: Sat Apr 01, 2006 10:57 pm

Re: Maybe I can explain it

Post by zoltag »

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

Code: Select all

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.
David Bryant
Gold Member
Gold Member
Posts: 86
Joined: Fri Jan 20, 2006 6:21 pm
Location: Denver, Colorado
Contact:

I can't spell it out any more clearly

Post by David Bryant »

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.
zoltag
Expert
Expert
Posts: 126
Joined: Sat Apr 01, 2006 10:57 pm

Re: I can't spell it out any more clearly

Post by zoltag »

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.
David Bryant
Gold Member
Gold Member
Posts: 86
Joined: Fri Jan 20, 2006 6:21 pm
Location: Denver, Colorado
Contact:

What people mean by "uniqueness"

Post by David Bryant »

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
zoltag
Expert
Expert
Posts: 126
Joined: Sat Apr 01, 2006 10:57 pm

Re: What people mean by "uniqueness"

Post by zoltag »

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.
David Bryant
Gold Member
Gold Member
Posts: 86
Joined: Fri Jan 20, 2006 6:21 pm
Location: Denver, Colorado
Contact:

Here's another example

Post by David Bryant »

zoltag wrote:Wow, thanks for the links.
You're welcome. I'm glad to help. :)

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: Select all

  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: Select all

  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
keith
Hooked
Hooked
Posts: 35
Joined: Tue Feb 07, 2006 3:13 am
Location: near Detroit, Michigan, USA

A swamp of semantics

Post by keith »

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.
Post Reply