The Circular Logic of Uniqueness

Advanced methods and approaches for solving Sudoku puzzles

Re: The Circular Logic of Uniqueness

Postby Mauriès Robert » Mon Nov 18, 2019 12:08 pm

Hi SpAce, Hi Mizziri,

I apologize for my bad copy/paste.

The puzzle I wanted to give as an example is this one where I voluntarily place the 6r2c5 in the original 7-solution puzzle.

.2159.6....5.6...186..........2......73..85.659.....2..5.63.8.23.9.24........5...

For this puzzle the basic techniques are enough.

I didn't want to complicate my explanations to Mizziri. It's a failure!

Sincerely
Robert
Mauriès Robert
 
Posts: 215
Joined: 07 November 2019
Location: France

Re: The Circular Logic of Uniqueness

Postby SpAce » Mon Nov 18, 2019 6:58 pm

Hi Robert,

Mauriès Robert wrote:The puzzle I wanted to give as an example is this one where I voluntarily place the 6r2c5 in the original 7-solution puzzle.

.2159.6....5.6...186..........2......73..85.659.....2..5.63.8.23.9.24........5...

For this puzzle the basic techniques are enough.

Actually they're not. You need at least one non-basic technique (Skyscraper, for example) to get to the point where advancement with logic is no longer possible. However, this can be used as a simple example of a safe uniqueness elimination mentioned by RW, i.e. one that doesn't depend on the assumption of a unique solution!

This is as far as we get with basics only:

Code: Select all
.----------.-----------------.-------------------.
| 4  2  1  |  5      9   37  |  6     378   378  |
| 9  3  5  |  8      6   27  |  247   47    1    |
| 8  6  7  | *14+3  *14  123 |  239   5     39   |
:----------+-----------------+-------------------:
| 1  4  68 |  2      5   369 |  379   3789  3789 |
| 2  7  3  | *14+9  *14  8   |  5    ^149   6    |
| 5  9  68 |  134    7   136 |  134   2     348  |
:----------+-----------------+-------------------:
| 7  5  4  |  6      3   19  |  8    ^19    2    |
| 3  8  9  | ^17     2   4   | ^17    6     5    |
| 6  1  2  |  79     8   5   |  3479  3479  3479 |
'----------'-----------------'-------------------'

Notice the tempting Unique Rectangle (*14) in r35c45 with two extra candidates (3 and 9), one of which must be true if uniqueness of the solution is guaranteed. Here it obviously isn't, but can we still use the UR without worrying about it? Yes, we can! The reason is that we can prove that it can't be a real deadly pattern, because we could easily kill a candidate from it (and thus one of its solutions) using normal techniques. For example:

2-String Kite (^): (1)r8c4 = r8c7 - r7c8 = (1)r5c8 => -1 r5c4

Because of that knowledge, we can safely use the UR (with or without taking the previous elimination first) for a simple elimination that reduces the puzzle to basics (until it gets stuck). First notice that the 3r3c4 is equivalent to the external candidate 1r3c6, the latter of which gives a simpler deduction:

Code: Select all
.----------.-------------------------.-------------------.
| 4  2  1  |   5        9     37     |  6     378   378  |
| 9  3  5  |   8        6     27     |  247   47    1    |
| 8  6  7  |  *14+3    *14+  b23(#1) |  239   5     39   |
:----------+-------------------------+-------------------:
| 1  4  68 |   2        5     36-9   |  379   3789  3789 |
| 2  7  3  | a*14[+9]  *14+   8      |  5    ^149   6    |
| 5  9  68 |   134      7     136    |  134   2     348  |
:----------+-------------------------+-------------------:
| 7  5  4  |   6        3   b(19)    |  8    ^19    2    |
| 3  8  9  |  ^17       2     4      | ^17    6     5    |
| 6  1  2  |   79       8     5      |  3479  3479  3479 |
'----------'-------------------------'-------------------'

UR(14)r35c45 (safe) using mixed +internal / #external:

(9)r5c4 =UR= (19)r37c6 => -9 r4c6 (=> basics until stuck)

Of course that elimination is possible with a normal Skyscraper as well, but the point was to demonstrate RW's concept in practice. If it can be proved that a uniqueness pattern can't be truly deadly by being able to eliminate one of its solutions using normal logic, then it can be safely used for a "uniqueness" reduction without making any assumptions about uniqueness. It means that in a real multi-solution puzzle, like this, none of the solutions get destroyed. We still get stuck here with the three solutions, so no information was lost by applying the UR:

Code: Select all
.----------.----------.-------------.
| 4  2  1  | 5  9  7  | 6   38   38 |
| 9  3  5  | 8  6  2  | 4   7    1  |
| 8  6  7  | 3  4  1  | 2   5    9  |
:----------+----------+-------------:
| 1  4  68 | 2  5  36 | 39  389  7  |
| 2  7  3  | 9  1  8  | 5   4    6  |
| 5  9  68 | 4  7  36 | 1   2    38 |
:----------+----------+-------------:
| 7  5  4  | 6  3  9  | 8   1    2  |
| 3  8  9  | 1  2  4  | 7   6    5  |
| 6  1  2  | 7  8  5  | 39  39   4  |
'----------'----------'-------------'

At this point the puzzle could be "solved" with one of three possible uniqueness techniqes (UR Type 1, BUG-Lite+1, BUG+1) but each of them would produce a different solution:

UR Type 1 (39+8)r49c78 => +8 r4c8
BUG-Lite+1 (368+9)r146c3689 => +9 r4c8
BUG+1 => +3 r4c8

Thus, at this point it's not safe to use any uniqueness technique, because it would destroy possible solutions. The reason is simple: unlike in the previous example, there's no logical technique available that would also destroy those solutions. The remaining deadly pattern is thus real and can't be reduced any further with logic.

One last point. If you only use such safe uniqueness reductions in a normal single-solution puzzle, then you'll also prove the uniqueness of the solution -- despite using uniqueness techniques!

(Btw, sorry if all of this is self-explanatory to everyone else. I'm mainly teaching myself! If you find faults in my logic, please inform.)
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: The Circular Logic of Uniqueness

Postby Mauriès Robert » Mon Nov 18, 2019 7:34 pm

Hi SpAce,

You're right, you need the basic techniques + the elimination of 9r4c6, easy to see, to get to the final puzzle I gave.
I definitely wasn't very good at it :?

Sincerely
Robert
Mauriès Robert
 
Posts: 215
Joined: 07 November 2019
Location: France

Re: The Circular Logic of Uniqueness

Postby eleven » Mon Nov 18, 2019 9:13 pm

Mizziri wrote:Case 2 is not possible by definition. If there were some elimination, !X, caused by a uniqueness technique that resulted in no solutions for the puzzle, this technique would be simply be restated as a logical technique: If !X -> no solution, therefore X. This cannot happen, since we have defined our premise to be that there are no logical techniques which advance us in the puzzle.

Yes, this "logical technique" is eliminating all extra candidates (somehow, all leading to contradictions) - if there is a uniqueness pattern or not.
eleven
 
Posts: 2221
Joined: 10 February 2008

Re: The Circular Logic of Uniqueness

Postby eleven » Mon Nov 18, 2019 9:26 pm

SpAce wrote:However, this can be used as a simple example of a safe uniqueness elimination mentioned by RW, i.e. one that doesn't depend on the assumption of a unique solution!

Nice, that you not only found this good old observation by RW, but also an application.
A special type of it got some populartity, the so called UR1.1:
Code: Select all
.  .  1 | . . 2
.  .  2 | . . 13

(None was a given)
eleven
 
Posts: 2221
Joined: 10 February 2008

Re: The Circular Logic of Uniqueness

Postby SpAce » Tue Nov 19, 2019 12:44 am

eleven wrote:Nice, that you not only found this good old observation by RW, but also an application.

Yeah, that was lucky, thanks to Robert's puzzle! I'd read RW's explanation before but never really internalized it before. The best way to learn a concept is to apply it yourself and try to explain it.

A special type of it got some populartity, the so called UR1.1:
Code: Select all
.  .  1 | . . 2
.  .  2 | . . 13

(None was a given)

Thanks for that! I recalled seeing something like that long ago and tried to find those discussions, but couldn't because I didn't remember the "UR1.1" name. Now I relocated those interesting threads as well. Looks like my use of the Kite was unknowingly a text-book case of proving the pattern! Btw, funny how long it took Denis to accept that it really doesn't depend on a uniqueness assumption.

The old threads also talk about "UR1". Is that just the plain old variant?
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: The Circular Logic of Uniqueness

Postby Mauriès Robert » Tue Nov 19, 2019 10:42 am

Hi SpAce,
Who is RW ?

Here is an interesting puzzle that perhaps addresses Mizziri's concerns.
..8....4.249..86...6...35........4.6.7.634.954.68.2....2...1...6143.9.5.98..7....
It has several hidden URs, one of which is very visible in b1b4

I used it as an example in Part 5 of TDP.

Sincerely
Robert
Mauriès Robert
 
Posts: 215
Joined: 07 November 2019
Location: France

Re: The Circular Logic of Uniqueness

Postby Ajò Dimonios » Tue Nov 19, 2019 1:28 pm

Hi everyone

In my opinion the use of resolution techniques that have as a hypothetical basis that the solution is unique are comparable to the identification of a Backdoor. Both do not demonstrate the uniqueness of the solution. Perhaps the only difference is that identifying a backdoor is a fortunate operation while uniqueness techniques have their own logic.

Ciao a Tutti
Paolo
Ajò Dimonios
 
Posts: 55
Joined: 07 November 2019

Re: The Circular Logic of Uniqueness

Postby SpAce » Tue Nov 19, 2019 2:35 pm

Hi Robert,

Mauriès Robert wrote:Who is RW ?

A very smart former forum member (long before I joined). He used to solve even very difficult puzzles without pencilmarks, sometimes even without writing in any solved numbers until the whole thing was fully solved in his head. Among other things, he was an expert in uniqueness techniques and used them a lot, also inventing several new ways to do it. His solving process is explained here. Interestingly, what he calls "trails" are a bit like your "tracks".

Here's an example (using a backdoor, though, but there's also another version without it). That thread also includes an interesting discussion about T&E.
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: The Circular Logic of Uniqueness

Postby Mauriès Robert » Tue Nov 19, 2019 6:53 pm

Hi SpAce,
SpAce wrote: Interestingly, what he calls "trails" are a bit like your "tracks".


So yes, I believe that RW had invented the track technique before me. I recognize myself in the way he does things. But alas, I had never heard of it before. I must say that my disability in English did not encourage me to come to this forum!
For me, it remains the idea of giving a theoretical framework to the track technique.

Sincerely
Robert
Mauriès Robert
 
Posts: 215
Joined: 07 November 2019
Location: France

Re: The Circular Logic of Uniqueness

Postby SpAce » Tue Nov 19, 2019 8:21 pm

Mauriès Robert wrote:I must say that my disability in English did not encourage me to come to this forum!

Well, I'm glad you did! It's always good to try to see things from different perspectives.
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: The Circular Logic of Uniqueness

Postby eleven » Tue Nov 19, 2019 9:44 pm

SpAce wrote:The old threads also talk about "UR1". Is that just the plain old variant?

No, i think, UR1 is a hidden UR, which needs uniqueness.
Probably the origin of UR1.1 was lost with the forum crash.
eleven
 
Posts: 2221
Joined: 10 February 2008

Re: The Circular Logic of Uniqueness

Postby SpAce » Tue Nov 19, 2019 11:30 pm

eleven wrote:
SpAce wrote:The old threads also talk about "UR1". Is that just the plain old variant?

No, i think, UR1 is a hidden UR, which needs uniqueness.

Ok, thanks! Do you mean this? I consider it one of the "plain old variants". I've never understood why it has its own name and is not counted as just another UR Type like the others. Totally unnecessary complication, imho.
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

Re: The Circular Logic of Uniqueness

Postby StrmCkr » Thu Nov 21, 2019 7:36 pm

UR1.1
eleven wrote:
RedEd, please can you formulate another trivial proof to make Denis a believer this time also ?


RedEd wrote:
OK.

Definition: an a/b/b/a pattern in a solution grid is anything isomorphic to that shown below:

Code: Select all
     .  .  . | .
     a  .  . | b
     b  .  . | a
    ---------+---
     .  .  . | .



Fact: if a solution grid (not necessarily unique) contains an a/b/b/a pattern on four unclued cells, C, then C=b/a/a/b is also a solution.

Theorem: if a puzzle-in-progress (that does not necessarily have a unique solution) has pencilmarks as shown below on four unclued cells then the bottom right value resolves to '3':

Code: Select all
     .  .  . | .
     1  .  . | 2
     2  .  . | 13
    ---------+---
     .  .  . | .


Proof: suppose to the contrary the bottom right value resolves to '1'. Then (vacuously) the solution grid contains the 1/2/2/1 pattern on four unclued cells, C. So, by the Fact above, C=2/1/1/2 is also a solution. But wait! - the pencilmarks do not allow that other solution - contradiction.


which is serves as the bases for the Avoidable Rectangles
Last edited by StrmCkr on Mon Nov 25, 2019 11:52 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 1079
Joined: 05 September 2006

Re: The Circular Logic of Uniqueness

Postby SpAce » Thu Nov 21, 2019 8:05 pm

StrmCkr wrote:which is serves as the bases for the Hidden unique Rectangles

What do you mean? I don't see any resemblance between the UR1.1 and Hidden Rectangles.
User avatar
SpAce
 
Posts: 2016
Joined: 22 May 2017

PreviousNext

Return to Advanced solving techniques