Strong inferences induced by the UR

Advanced methods and approaches for solving Sudoku puzzles

Re: Strong inferences induced by the UR

Postby ronk » Wed Apr 08, 2009 2:28 pm

storm_norm wrote:The trick is to notice what looks like a UR, but really can't take advantage of the common rules of URs to make any eliminations. AND its very important that the UR candidates are the ONLY candidates left in the floor cells. as in this grid
Code: Select all
+--------+-----------+-------+
| 12 . . | 12345 . . | . . . |
| .  . . | .     . . | . . . |
| 12 . . | 12345 . . | . . . |
+--------+-----------+-------+
| .  . . | .     . . | . . . |
| .  . . | 13    . . | . . . |
| .  . . | 25    . . | . . . |
+--------+-----------+-------+
| .  . . | .     . . | . . . |
| .  . . | .     . . | . . . |
| .  . . | .     . . | . . . |
+--------+-----------+-------+

it just so happens that there is another 1 and another 2 in column 4. both cannot be false at the same time (that will force the UR to exist, NO NO !!) This provides yet another strong inference to exploit
UR12[(1)r5c4 = (2)r6c4]

Are we to assume the bivalues contain the only other UR digits in column 4?

storm_norm wrote:consider this grid and notice the UR {1,2} in r46c14
Code: Select all
+--------+-------------+-------+
| .  . . | 3456789 . . | . . . |
| .  . . | 3456789 . . | . . . |
| .  . . | 12(3456). . | . . . |
+--------+-------------+-------+
| 12 . . | 12345   . . | . . . |
| .  . . | .       . . | . . . |
| 12 . . | 12345   . . | . . . |
+--------+-------------+-------+
| .  . . | 3456789 . . | . . . |
| .  . . | 3456789 . . | . . . |
| .  . . | 3456789 . . | . . . |
+--------+-------------+-------+

as stated before, the extra UR candidates 1 and 2 in r3c4 exist in the same cell. From the rules of URs we can now eliminate the {3,4,5,6} from r3c4 because neither the 1 nor the 2 can be false at the same time.

Are we to assume r3c4 contains the only other UR digits in column 4? IOW what about r5c4?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby storm_norm » Wed Apr 08, 2009 11:06 pm

ronk said:
Are we to assume the bivalues contain the only other UR digits in column 4?


each one of the UR digits must only appear once (or as a group) in the "house" which contains the roof cells.
one of the examples I used in the posting for this type shows how a group can be strongly inferenced.
------

Are we to assume r3c4 contains the only other UR digits in column 4? IOW what about r5c4?

Yes.
each one of the UR digits must occur only once in the same "house" as the roof cells, AND be contained in one cell.
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby champagne » Thu Apr 09, 2009 9:42 am

storm_norm wrote:I agree that ttt does make very nice use of the AUR, but it should be noted that ttt's main use of the UR is in forming strong sets. .


I don’t catch precisely your point. “ttt” diagrams, as far as I can see, are closer to AIC’s nets than to Alan Barker SLG’s .




storm_norm wrote:you say that you don't notice a difference in a puzzle's path if your solver employs the easier UR inferences?
I can't deny or affirm that these inferences are ever needed in solving sudoku puzzles. I am leaning towards never.
.



First of all, If I introduced UR strong inferences in my solver, it is because I am convinced it is shortening some paths. I am just lacking time to find the most relevant examples and it did not show in the puzzles I studied in between.

BTW, I introduced a very efficient UR pattern, the double XWing which is not so far form your

storm_norm wrote:
IV. An uncommon UR inference.

Code: Select all
+--------+-----------+-------+
| 12 . . | 12345 . . | . . . |
| .  . . | .     . . | . . . |
| 12 . . | 12345 . . | . . . |
+--------+-----------+-------+
| .  . . | .     . . | . . . |
| .  . . | 13    . . | . . . |
| .  . . | 25    . . | . . . |
+--------+-----------+-------+
+



The double XWing pattern is extremely efficient coupled with Exocets. You can find some examples of use in the bb “ pattern” thread
http://forum.enjoysudoku.com/viewtopic.php?t=6546;

It is not exactly designed to work as strong inferences in an AIC, but the underlying concept is the same.

Let us assume you have a UR unrestricted pattern

Code: Select all
12+  12+
12+  12+  (+ means any number of other digits)


Let’s now consider that you are just working on digits 1 and 2.

If combining one candidate ‘1’ and one candidate ‘2’ (candidate or group of candidates) you are left with the double XWing, then the start is not valid.

Any invalid “And” has a corresponding “strong inference”

If you have a look at the bb thread, you will see that this is applied to the Exocet pattern., so it leads directly to the elimination of a super candidate. The search made by the solver uses a kind of Allan Barker model, but as far as I can see, in most cases, it could be an AIC net as well.

champagne
champagne
2017 Supporter
 
Posts: 5644
Joined: 02 August 2007
Location: France Brittany

Postby storm_norm » Thu Apr 09, 2009 11:14 am

champagne,

I don’t catch precisely your point. “ttt” diagrams, as far as I can see, are closer to AIC’s nets than to Alan Barker SLG’s

Yes, that is what I was saying. I read in another thread that ttt's AUR are used to make nets.

if the UR cells contain {1,2,3}, {1,2,4}, {1,2,5}, {1,2} then the 3,4 and 5 are considered to be a strong set because at least one is true in order to avoid the deadly pattern.
is this what you were thinking as well?
ttt is very adept at finding these relationships.

First of all, If I introduced UR strong inferences in my solver, it is because I am convinced it is shortening some paths. I am just lacking time to find the most relevant examples and it did not show in the puzzles I studied in between.

hmm.
I think you are missing the point. Sure, its fine that you want to introduce the UR strong inference to your solver, but can you stand back and enjoy the usefulness of the pattern? Maybe step back and realize that these patterns sometimes jump off the page without the help of a solver? The sole inspiration of this thread was provoked by how my eyes are drawn to these inferences. For a manual solver, that is BIG NEWS! I am sure all kinds of statistics can be researched about just how effective or uneffective these moves are.
The point is that they are being discussed and hopefully educational.
-------
your work on the double x-wing is quite interesting. Its probably the kind of powerful move that solvers like to hear about when it comes to really using a UR to its full potential. I will need to keep studying your work.
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby champagne » Thu Apr 09, 2009 1:29 pm

storm_norm wrote:if the UR cells contain {1,2,3}, {1,2,4}, {1,2,5}, {1,2} then the 3,4 and 5 are considered to be a strong set because at least one is true in order to avoid the deadly pattern.
is this what you were thinking as well?
ttt is very adept at finding these relationships..


I agree that he is not at all afraid by complexity. I know at least another player doing similar things on a French forum.

storm_norm wrote:
First of all, If I introduced UR strong inferences in my solver, it is because I am convinced it is shortening some paths. I am just lacking time to find the most relevant examples and it did not show in the puzzles I studied in between.

hmm.
I think you are missing the point. Sure, its fine that you want to introduce the UR strong inference to your solver, but can you stand back and enjoy the usefulness of the pattern? ....The point is that they are being discussed and hopefully educational..


I choose in priority to enter in my solver what seems feasible for a player, so I do not see any contradiction. I agree that many of the pattern your describe bring direct eliminations or assignments.



storm_norm wrote:-
your work on the double x-wing is quite interesting. Its probably the kind of powerful move that solvers like to hear about when it comes to really using a UR to its full potential. I will need to keep studying your work.


I hope it will help, although in the way I describe them, it seems more dedicated to Exocest patterns that I found mainly in puzzles classified as "Hardest".

champagne
champagne
2017 Supporter
 
Posts: 5644
Joined: 02 August 2007
Location: France Brittany

Postby DonM » Thu Apr 09, 2009 7:23 pm

storm_norm wrote:The sole inspiration of this thread was provoked by how my eyes are drawn to these inferences. For a manual solver, that is BIG NEWS!


Yes!:)
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby ronk » Fri Apr 10, 2009 2:53 am

UR Type 3 patterns always have complementary naked and hidden sets. Occasionally the hidden set is a hidden pair.
Code: Select all
top1465_0817
84..1...27.....8.....5.........5..3.65...9.....2.7...1.....628...6.....523....4..

After SSTS
 8      4      359    | 379    1      37     | 3569   569    2
 7     U26     15     | 2349  U26+934 234    | 8      15     39
 139   U26     39     | 5     U26+8   28     | 139    47     47
----------------------+----------------------+---------------------
 149    789    4789   | 2468   5      1248   | 69     3      4689
 6      5      1348   | 1348   348    9      | 7      2      48
 349    89     2      | 3468   7      348    | 569    4569   1
----------------------+----------------------+---------------------
 5      1      479    | 3479   349    6      | 2      8      379
 49     789    6      | 234789 2-3489 123478 | 139    79     5
 2      3      789    | 1789   89     5      | 4      1679   679

The hidden set is <26> in r238c5 and the naked set is <3489> in r23579c5. The only UR digit external to UR(26)r23c25 in columns 2 and 5 is digit 2 in r8c5. Therefore r8c5=2.

But it's much better known as a Type 4 UR followed by a hidden single.:)
Last edited by ronk on Fri Apr 10, 2009 12:55 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby storm_norm » Fri Apr 10, 2009 3:23 am

champagne,
this example was presented to me by another poster in the daily forum...
I wonder if this is the same type of inference you are making in your "double x-wing" work?


Code: Select all
.------------------.------------------.------------------.
| 5     4     29   |A13    289   89   |#1-3   6     7    |
| 19    8     3    | 7     6     5    | 4     19    2    |
| 129   6     7    | 4     239   19   | 5     189  B38   |
:------------------+------------------+------------------:
| 2368  12    126  | 5     38    7    | 9     18    4    |
| 389   5     19   |U136   4     189  | 7     2    U368  |
| 389   7     4    |U136   389   2    | 13    5    U368  |
:------------------+------------------+------------------:
| 26    12    126  | 9     7     3    | 8     4     5    |
| 7     9     8    | 2     5     4    | 6     3     1    |
| 4     3     5    | 8     1     6    | 2     7     9    |
'------------------'------------------'------------------'

The 36UR is marked "U". It is important to note that the <6>s in this UR form an X-Wing. This means that any external <3>s in the UR columns will destroy the UR and thus have a strong inference. In this case:
36UR[(3)r1c4=(3)r3c9]
This strong inference alone performs an elimination! <3> is removed from r1c7, marked #. You won't find an AIC much shorter than that!

The x-wing on the 6's says that any existance of a 3 outside the UR in columns 4 and 9 would destroy the UR so at least one has to be true. both can't be false or the deadly pattern will exist.
in the above example, exactly one instance of 3 exists in columns 4 and 9 therefore creating the strong inference on them.

is this a simplified example of your "double x-wing" work?
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby champagne » Fri Apr 10, 2009 7:01 am

storm_norm wrote:champagne,

is this a simplified example of your "double x-wing" work?


surely it is one, the simplest you can imagine.

As you write, in that situation, the XWing is already there for digit 6, but the logic is the same.

I guess some examples nearly as basic covering the 2 digits could be found, but it does not push in direct action. It just creates a strong inference.

EDIT: In fact we create usually a weak inference a&b not valid. The strong inference (to stay in line with the title of the thread) applies to ~a and ~b the complemetary values for 'a' and 'b'



One can express the same in an AIC form using the "strong set" 18 r56c49 for example, but it does not add anything to the very simple fact that 3r1c7 creates the deadly pattern double XWing, I agree with you.

champagne
champagne
2017 Supporter
 
Posts: 5644
Joined: 02 August 2007
Location: France Brittany

Postby storm_norm » Fri Apr 10, 2009 10:41 am

champagne said:
EDIT: In fact we create usually a weak inference a&b not valid. The strong inference (to stay in line with the title of the thread) applies to ~a and ~b the complemetary values for 'a' and 'b'

right, the strong inference is not internal but external to the UR with the x-wing.
storm_norm
 
Posts: 85
Joined: 27 February 2008

Postby ronk » Fri Apr 10, 2009 11:42 pm

champagne wrote:I introduced a very efficient UR pattern, the double XWing ...

Other than limiting the shape to a rectangular pattern, how does "double x-wing" differ from "deadly pattern"?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Sat Apr 11, 2009 9:19 am

ronk wrote:
champagne wrote:I introduced a very efficient UR pattern, the double XWing ...

Other than limiting the shape to a rectangular pattern, how does "double x-wing" differ from "deadly pattern"?


The "double XWing" is a deadly pattern.

The specificity in the Exocet process is that the deadly pattern comes out of a bi floor analysis (which is a strong limitation) with, as a start, one super candidate of the Exocet base.

As I could expect, storm_norm has shown in the above example that the same deadly pattern can be used in much simpler contexts.



champagne
champagne
2017 Supporter
 
Posts: 5644
Joined: 02 August 2007
Location: France Brittany

Re: Strong inferences induced by the UR

Postby JasonLion » Mon Mar 28, 2011 6:20 pm

Thanks to Bob in TX we now have PDFs of posts made to this topic in July 2009.

Page 2
Page 3
Page 4
Page 5
Page 6
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Previous

Return to Advanced solving techniques