New Unique pattern trick?

Advanced methods and approaches for solving Sudoku puzzles

New Unique pattern trick?

Postby vidarino » Thu Mar 02, 2006 1:47 pm

I can't recall having read about this before, so I'm taking my chances on calling it new. ;-)

While studying the grid from this thread, I stumbled across a potentially useful little trick.

The original grid;
Code: Select all
      3      6     14 |      14      7      9 |       2      8      5
      7     29      8 |       3     24      5 |     469     46      1
     49     12      5 |       8      6     12 |     479      3    479
----------------------+-----------------------+----------------------
     28      5      9 |     147      3    246 |      18    467    478
     28      4     67 |       5    129    126 |       3    167    789
      1      3     67 |      47     49      8 |    4679      5      2
----------------------+-----------------------+----------------------
      6      7    134 |       9      5     34 |      18      2     48
     49    189*     2 |       6     18*    47 |       5    147      3
      5     18*    34 |       2    148*  1347 |      47      9      6


As mentioned in the other thread, it can be advanced with this loop, taking advantage of an Almost Unique Rect at R89C25;
Code: Select all
 R8C5=8={Almost Unique Rectangle:R8C2=9|4=R9C5}=8=R8C5  ->  R8C5=8


Then basic techniques and an XY-Wing take us here;
Code: Select all
      3      6     14 |      14      7      9 |       2      8      5
      7     29      8 |       3     24      5 |     469     46      1
     49     12      5 |       8      6     12 |     479      3    479
----------------------+-----------------------+----------------------
     28      5      9 |     147      3     26 |      18    467    478
     28      4     67 |       5     29    126 |       3    167    789
      1      3     67 |      47     49      8 |    4679      5      2
----------------------+-----------------------+----------------------
      6      7    134 |       9      5     34 |      18      2     48
     49     19*     2 |       6      8*    47 |       5    147      3
      5      8*    34 |       2      1*   347 |      47      9      6


Now look at our Almost Unique Rectangle. It's almost completely solved.

BUT! Since we know that none of the four corners were part of the initial set of clues, R8C2 can not be 1, or we would have a two-solution grid where we could swap the 1s and the 8s in the rectangle. In other words, the strong link from before, R8C2=9|4=R9C5, still holds.So, since the 4 in R9C5 has been wiped out, so we can happily fix R8C2=9.

Conclusion; We can actually look for remnants of unique patterns even among the solved cells, and react accordingly, if-and-only-if none of the corners were part of the initial set of clues (which of course would avoid the two-solution potential).

So there you have it. I just thought it was an interesting twist on solving, since it either relies on knowing the starting position of the puzzle, or that the solver "remembers" strong links, even after the pattern from which they were formed has been partially solved.:)

Vidar
Last edited by vidarino on Thu Mar 02, 2006 11:21 am, edited 1 time in total.
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ravel » Thu Mar 02, 2006 3:11 pm

Strange, that meens that sometimes you can only make an elimination, when you know the "history" of a candidate grid (or the original clues). In other words, the sudoku becomes harder in some way, when one of the 3 derived clues is added.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Carcul » Thu Mar 02, 2006 3:58 pm

Hi Vidarino.

Vidarino wrote:Since we know that none of the four corners were part of the initial set of clues, R8C2 can not be 1,...


Your reasoning looks interesting, but I don't understand it. Could you explain a little further, specially the sentence of yours that I have quoted?
Another comment: an AUR can often be used in several ways, and most of the times one of them solve the puzzle in a not very complicated way. This is also the case for your puzzle. Regarding your first grid above, check this:

[r8c2]=9|4=[r9c5](-4-[r6c5]-9-[r5c5])-4-[r2c5](-2-[r5c5])=4=[r1c4]=1=[r4c4]-1-[r5c5],

This argument means that, if r8c2 is not "9" then r5c5 would be an empty cell. So, r8c2=9 and it solve the puzzle.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby vidarino » Thu Mar 02, 2006 4:14 pm

Carcul wrote:Hi Vidarino.

Vidarino wrote:Since we know that none of the four corners were part of the initial set of clues, R8C2 can not be 1,...


Your reasoning looks interesting, but I don't understand it. Could you explain a little further, specially the sentence of yours that I have quoted?


I'll try. We know that all the four corners were not part of the initial set of clues simply because we remember that they weren't. In other words, it's not apparent from looking at the puzzle in its current state, but looking back at an earlier stage, we know that it used to be an Almost Unique Rectangle. And therefore we know that R8C2<>1, or we would have created a (solved, but "swappable") BUG-Lite.

Another comment: an AUR can often be used in several ways, and most of the times one of them solve the puzzle in a not very complicated way. This is also the case for your puzzle. Regarding your first grid above, check this:

[r8c2]=9|4=[r9c5](-4-[r6c5]-9-[r5c5])-4-[r2c5](-2-[r5c5])=4=[r1c4]=1=[r4c4]-1-[r5c5],

This argument means that, if r8c2 is not "9" then r5c5 would be an empty cell. So, r8c2=9 and it solve the puzzle.


Nice one.:) I'm pretty crap at finding these multi-implication chains myself, so I'm mostly working with plain loops/cycles. It's not my priority to solve it in one step either, yet, but maybe when I get better at it.:)

Anyway, the grid above was mainly ment to demonstrate the Dismembered Unique Rectangle.:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ronk » Thu Mar 02, 2006 4:21 pm

Carcul wrote:Regarding your first grid above, check this:

[r8c2]=9|4=[r9c5](-4-[r6c5]-9-[r5c5])-4-[r2c5](-2-[r5c5])=4=[r1c4]=1=[r4c4]-1-[r5c5],

This argument means that, if r8c2 is not "9" then r5c5 would be an empty cell. So, r8c2=9 and it solve the puzzle.

How many candidates did you try (assert as true and negate as false) before you found that "backdoor" to the puzzle?

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Thu Mar 02, 2006 6:29 pm

If i understood Vidar right, we could formulate it as a rule:
Code: Select all
------------------
|a . . | b   . . |
|b . . | acd . . |
|. . . | .   . . |
------------------  X=acd

When you have a UR-like rectangle (2 corners in one box, 2 in another), with the candidates a,b and b,X, where X contains a, and none of a,b,b were given, you can eliminate a from X.
The reason is that (from an earlier stage) we know that if X could become a, there would be another solution b,a,a,b.
ravel
 
Posts: 998
Joined: 21 February 2006

Re: New Unique pattern trick?

Postby ronk » Thu Mar 02, 2006 7:12 pm

vidarino wrote:Conclusion; We can actually look for remnants of unique patterns even among the solved cells, and react accordingly, if-and-only-if none of the corners were part of the initial set of clues (which of course would avoid the two-solution potential).

So there you have it. I just thought it was an interesting twist on solving, since it either relies on knowing the starting position of the puzzle, or that the solver "remembers" strong links, even after the pattern from which they were formed has been partially solved.:)

Thanks. That sure clarifies what (I think) aeb meant by "freely invented" here.

vidarino wrote:
Code: Select all
 3    6   14 |  14    7     9 |     2    8    5
 7   29    8 |   3   24     5 |   469   46    1
49   12    5 |   8    6    12 |   479    3  479
-------------+----------------+----------------
28    5    9 | 147    3   246 |    18  467  478
28    4   67 |   5  129   126 |     3  167  789
 1    3   67 |  47   49     8 |  4679    5    2
-------------+----------------+----------------
 6    7  134 |   9    5    34 |    18    2   48
49  189*   2 |   6   18*   47 |     5  147    3
 5   18*  34 |   2  148* 1347 |    47    9    6

How did you eliminate the 4 in r8c5? I can only find an ALS xz-rule (A = r2c5,r3c6 and B = r789c6), but that would eliminate the 4 in r9c5 too.

Ron

P.S. To reduce line wrap, you might consider taking out some of the white space on your candidate grids.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Unique pattern trick?

Postby vidarino » Thu Mar 02, 2006 9:10 pm

ronk wrote:Thanks. That sure clarifies what (I think) aeb meant by "freely invented" here.


Yep, I would think so, too. Since you never get less information during the course of a puzzle, the strong link between the AUR "extras" remains, so one could imagine that the AUR corner candidates were still there.

How did you eliminate the 4 in r8c5? I can only find an ALS xz-rule (A = r2c5,r3c6 and B = r789c6), but that would eliminate the 4 in r9c5 too.


A bit earlier in the puzzle;
Code: Select all
   3   6    14 |  14    7     9 |     2    8    5
   7 289    48 |   3   24     5 |   469   46    1
  49  12     5 |   8    6    12 |   479    3  479
---------------+----------------+----------------
  28   5     9 | 147    3  1246 | 14678 1467  478
  28   4    67 |   5  129   126 |     3  167  789
   1   3    67 |  47   49     8 |  4679    5    2
---------------+----------------+----------------
   6   7  1348 |   9    5    34 |   148    2   48
  49 189*    2 |   6  148*   47 |     5  147    3
   5  18* 1348 |   2  148* 1347*|  1478    9    6


Then this grouped Nice Loop gets the 4 and a few more;
Code: Select all
R8C2=8=R8C5=1=[R9C56]-1-R9C2-8-R8C2
   -> R9C3 <> 1
   -> R9C7 <> 1
   -> R8C5 = 18

A Swordfish in 1s and another Nice Loop later and you end up with the puzzle as posted initially.:)

P.S. To reduce line wrap, you might consider taking out some of the white space on your candidate grids.


Good idea. I've been meaning to make my formatter use adaptive column width, and your reminder is just the excuse I need. ;)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Myth Jellies » Fri Mar 03, 2006 12:50 am

You have another dismembered UR (aka unavoidable set) marked in %'s here...
Code: Select all
      3      6     14 |      14      7      9 |       2      8      5
      7     29      8 |       3     24      5 |     469     46      1
     49     12      5 |       8      6     12 |     479      3    479
----------------------+-----------------------+----------------------
     28      5%     9 |     147%     3     26 |      18    467    478
     28      4%    67 |       5%    29    126 |       3    167    789
      1      3     67 |      47     49      8 |    4679      5      2
----------------------+-----------------------+----------------------
      6      7    134 |       9      5     34 |      18      2     48
     49     19*     2 |       6      8*    47 |       5    147      3
      5      8*    34 |       2      1*   347 |      47      9      6

I'm guessing that the rule is, if none of the 4's & 5's were given as initial clues in r45c24, then you can eliminate the 4 as a candidate in r4c4? [Edit: Doh! of course it is. Ravel just stated it a couple of posts earlier:) ]

Another interesting question is that if you knew the clues to the puzzle were minimal (each clue had to be there or the puzzle would not be unique), and one of the 4's or 5's were given, could you then come up with some reasoning that r4c4 had to be a 4? I suppose you would have to prove that the given clue was not part of any other unavoidable set.
Last edited by Myth Jellies on Thu Mar 02, 2006 10:39 pm, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby vidarino » Fri Mar 03, 2006 1:13 am

Myth Jellies wrote:You have another dismembered UR (aka unavoidable set) marked in %'s here...
Code: Select all
...


Ah, indeed I do.:)

They're not quite unavoidable sets, though. This one could be an unavoidable set iff one of the corners were given as clues. If not, since we know the puzzle has a unique solution, it can *not* be an unavoidable set.

Perhaps "Almost Unavoidable Set" is more in line with the current nomenclature.

I'm guessing that the rule is, if none of the 4's & 5's were given as initial clues in r45c24, then you can eliminate the 4 as a candidate in r4c4?


Spot on. Otherwise the rectangle would be an unavoidable set, which would be impossible in a proper puzzle.

Another interesting question is that if you knew the clues to the puzzle were minimal (each clue had to be there or the puzzle would not be unique), and one of the 4's or 5's were given, could you then come up with some reasoning that r4c4 had to be a 4? I suppose you would have to prove that the given clue was not part of any other unavoidable set.


Heh, that is indeed an interesting question! I imagine looking for unavoidable sets in an incomplete puzzle can be a bit of a challenge, though. And as the puzzle progresses, it wouldn't surprise me if there popped up other logical reasons for the cell in question to be a particular value.:)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ronk » Fri Mar 03, 2006 2:22 am

vidarino wrote:They're not quite unavoidable sets, though. This one could be an unavoidable set iff one of the corners were given as clues.
I have r45c2 and r5c4 as givens. Did I miss "the real" starting grid somewhere?

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby vidarino » Fri Mar 03, 2006 8:37 am

ronk wrote:
vidarino wrote:They're not quite unavoidable sets, though. This one could be an unavoidable set iff one of the corners were given as clues.
I have r45c2 and r5c4 as givens. Did I miss "the real" starting grid somewhere?


Ah, you didn't miss it, I just never posted it. Anyway, since this technique is based on knowing it, here it is;

Code: Select all
+-------+-------+-------+
| 3 6 . | . 7 . | . 8 . |
| 7 . . | . . . | . . 1 |
| . . 5 | . 6 . | . 3 . |
+-------+-------+-------+
| . . 9 | . 3 . | . . . |
| . 4 . | . . . | . . . |
| . . . | . . 8 | . 5 2 |
+-------+-------+-------+
| 6 7 . | 9 5 . | . . . |
| . . 2 | 6 . . | . . 3 |
| 5 . . | 2 . . | . 9 6 |
+-------+-------+-------+


Now we see that R5C2 is indeed an initial clue. Rewinding to Myth Jellies' post, this means that we cannot say anything about R4C4 being 4 or not.
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby vidarino » Fri Mar 03, 2006 12:11 pm

I have now dubbed this trick "Almost Unavoidable Set", since that's pretty much what it is.:)

Here's a draft of a more formal explanation:

Definition: An Almost Unavoidable Set is a partially solved pattern of 4 or more cells which, if one or more of the remaining candidates were true, would form an Unavoidable Set, but from which there were no initial clues given. Knowing that puzzles with a unique solution will have at least one initial clue in each unavoidable set, we might be able to make some eliminations.

There are a couple of types of AUS, analogous to the Unique Rectangle types.

Type 1:
One unsolved corner in an AUS = eliminate candidate that would make it into an Unavoidable Set;

Code: Select all
    3    6   14 |    14    7    9 |     2    8    5
    7   29    8 |     3   24    5 |   469   46    1
   49   12    5 |     8    6   12 |   479    3  479
----------------+-----------------+-----------------
   28    5    9 |   147    3  246 |    18  467  478
   28    4   67 |     5   29  126 |     3  167  789
    1    3   67 |    47   49    8 |  4679    5    2
----------------+-----------------+-----------------
    6    7  134 |     9    5   34 |    18    2   48
   49   19*   2 |     6    8*  47 |     5  147    3
    5    8*  34 |     2    1* 347 |    47    9    6


Almost Unavoidable Set type 1 with candidates 18 in R89C25.
-> R8C2 <> 1

Type 2:
Two unsolved corners + extra candidates.

Code: Select all
+-------+-------+-------+
| . . . | . . . | 9 4 . |
| . 1 9 | . 3 5 | . . 6 |
| . . 8 | . 6 . | 1 . . |
+-------+-------+-------+
| 6 2 . | . . 1 | 3 . 9 |
| . . . | . . . | . . . |
| 9 . . | . . . | . . 5 |
+-------+-------+-------+
| . . . | 3 . . | . . . |
| 2 5 6 | . 9 8 | 7 . . |
| 8 . 7 | . . . | . . . |
+-------+-------+-------+


... can be advanced (thought a handful of pretty hard steps, mind you) to here:

Code: Select all
   5   6   2 |    8   1   7 |    9   4   3
   7   1   9 |    4   3   5 |    8   2   6
   3   4   8 |    2   6   9 |    1   5   7
-------------+--------------+--------------
   6   2   4*|   57  58*  1 |    3  78   9
   1  78   5*|    9  48*  3 |  246 678  28
   9  78   3 |   67 248  26 |   24   1   5
-------------+--------------+--------------
   4   9   1 |    3   7  26 |    5  68  28
   2   5   6 |    1   9   8 |    7   3   4
   8   3   7 |   56  25   4 |   26   9   1


Almost Unavoidable Set type 2 with 45 in R45C35 + extra pair of 8s, one of which must be true.
We can eliminate 8 from cells that see both unsolved AUS corners:
-> R6C5 <> 8.

Type 3?:
There could also be a type 3, but I haven't found any in the wild yet. It should manifest itself as two unsolved corners + a combination of extra candidates, accompanied by a naked subset consisting of the same candidates. All subset candidates can be eliminated from their intersection.

I don't think there exists a AUS type 4, since none of the candidates can be in both the unsolved corners, since they would be eliminated by their solved neighbours.

That's it for now. Suggestions? Critique?

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby Neunmalneun » Fri Mar 03, 2006 12:46 pm

Code: Select all
 

 
 *-----------------------------------------------------------*
 | 3     6     14    | 14    7     29    | 29    8     5     |
 | 7     29    8     | 3     24    5     | 2469  46    1     |
 | 49    129   5     | 8     6     129   | 2479  3     479   |
 |-------------------+-------------------+-------------------|
 | 28    5     9     | 147   3     246   | 18    467   478   |
 | 28    4     67    | 5     129   126   | 3     167   789   |
 | 1     3     67    | 47    49    8     | 4679  5     2     |
 |-------------------+-------------------+-------------------|
 | 6     7     134   | 9     5     34    | 18    2     48    |
 | 49    19    2     | 6     8     47    | 5     147   3     |
 | 5     8     34    | 2     14    1347  | 47    9     6     |
 *-----------------------------------------------------------*

There is another AUR in your example. The 34s in R79C36 leave two possibilities: either R7C3 is 1 or you can eliminate 34 in R9C6. The other way round: if R9C6 is 34, R7C3 has to be 1 (Uniqueness rule).

Without complicated chains and loops (at least too complicated for me) it is obvious that a 3 in R9C6 (and consequently a 4 in R9C3 and a 1 in R7C3) would lead to a contradiction in box 7 (leaving only two 9s for R8C12). So R9C6 <> 3 and R7C6 = 3
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby ronk » Fri Mar 03, 2006 12:46 pm

vidarino wrote:I have now dubbed this trick "Almost Unavoidable Set", since that's pretty much what it is.:)

Having not dealt with "unavoidable sets" before, let me describe what I understand. Then please set me straight.

Two repeated digits in the shape of a rectangle is one example of a "set".
Code: Select all
  .  a  .  |  b  .  .
  .  .  .  |  .  .  .
  .  b  .  |  a  .  .

If any of the four cells contains a given, a clue, the set is an "unavoidable set". If none of the four cells contains a given, it follows that the "unavoidable set" is avoidable. IOW, if none of the four cells contains a given, the set is an "avoidable set".

If any of the four cells contain candidates [edit: AND none of the four cells contains a clue], it seems we would then have an "almost avoidable set", but that's not what you came up with. What am I missing?:?:

Ron

P.S. I'd like to see AUS used for Almost Unique Swordfish. And with a AAS here, who knows, we might soon have an A?S elsewhere.:D

P.P.S. I'm having a little fun with words here, but am serious about the question above.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques