A Hitch-hikers Guide to Uniqueness-based Solving Techniques

Advanced methods and approaches for solving Sudoku puzzles

Postby wintder » Sun Sep 30, 2007 8:45 pm

Ruud wrote:Wintder, I appreciate your concerns. I've changed the wording and added a footnote.

Ruud


Thank you Ruud.

I am content.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby daj95376 » Sun Sep 30, 2007 8:54 pm

Well, now for my next basic question. In my previous example, I used bivalue cells for chaining because it resulted in Naked Singles along the chain. However, it's possible for Naked N-tuples to perform eliminations in a UR Type 3. For a UR Type 4, I can envision a single strong link -- conjugate Hidden Singles -- explaining the eliminations. Does this make Hidden N-tuples acceptable? How about Locked Candidates 1/2? In general, which techniques are allowed in the elimination chains?

You can thank ronk for this question because he dropped this UR into my lap one day and I've never been able to shake the possible implications.

Code: Select all
UR Type 3:
+-------------+
|  -   -   #  |
| 12   -  123 |
|  -   -   #  |
+-------------+
| 12   -  124 |
|  -   -   #  |
|  -   -  345 |
+-------------+
|  -   -   #  |
|  -   -  45  |
|  -   -   #  |
+-------------+
           #    is where <345> can be eliminated
Last edited by daj95376 on Sun Sep 30, 2007 5:01 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ronk » Sun Sep 30, 2007 8:57 pm

wintder wrote:
Ruud wrote:Uniqueness-based solving techniques can only be used on valid Sudoku puzzles.

Should not be used, yes, cannot be used is untrue.
[...]
If this thread is to be definitive I believe the dangers should be listed as well as the benefits.

Sure, "should not drive on the wrong side of the road" is better grammar than "cannot drive on the wrong side of the road", but are we here to correct grammar?

Additionally, I'd be surprised if much space in a drivers' manual is devoted to the dangers of driving on the wrong side of the road.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby wintder » Sun Sep 30, 2007 9:02 pm

"cannot" means that.

"should not" means "you can do, the results may be odd."

Edited, still wondering the point.
wintder
 
Posts: 297
Joined: 24 April 2007

Postby daj95376 » Sun Sep 30, 2007 9:18 pm

My Turn wrote:Uniqueness-based solving techniques are based on the premise of a unique solution. A valid Sudoku puzzle has a unique solution. Thus, Uniqueness-based solving techniques should only be used on valid Sudoku puzzles.

Get rid of the *) and its lengthy explanation.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby RW » Mon Oct 01, 2007 3:52 am

wintder wrote:"should not" means "you can do, the results may be odd."

Which is exactly why the words "should not" are wrong. If you see a pattern similar to an uniqueness pattern in a multisolutional puzzle and make an elimination based on that, you are in fact NOT using uniqueness technique! If you think you are using the technique, then you have failed to understand the logic behind uniqueness based reductions. The reason that you can make an uniqueness reduction is not that you see a pattern that you have learned at the sudoku players forum. You make the elimination because if that digit was true, then the puzzle would have either 0 or >1 solutions. If the puzzle has >1 solutions, then there is absolutely no logical reason to make that elimination.

Rather than stating the danger of "using" uniqueness technique in multisolution puzzles, I think the first post should point out this contradiction between the basic definition of the technique and multisolution puzzles.

RW
RW
2010 Supporter
 
Posts: 1010
Joined: 16 March 2006

Wrong Side?

Postby keith » Tue Oct 02, 2007 12:06 am

Additionally, I'd be surprised if much space in a drivers' manual is devoted to the dangers of driving on the wrong side of the road.


... and even less space is devoted to how to drive on the wrong side of the road.

No sane person uses human manual solving techniques to prove uniqueness. I suggest dispensing with the entire discussion, and replacing it with a link to a site (or a downloadable solver) where the uniqueness of any particular puzzle can be tested.

Plus, maybe, a short comment to the effect that some people prefer not to use Uniqueness techniques, since they involve a perceived "extra" condition.

Keith
keith
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Postby coloin » Wed Oct 03, 2007 11:04 am

Well i sympathize with keith but I fear we have been down this road before and when you have a difficult puzzle you need all the help you can get.

Its pretty much where you draw the line.......a certain guy lost the first world championship because he lost out to a compeditor who gambled and guessed a few clues and solved the final puzzle quicker. Needless to say he wasnt happy !

I dont think uniqueness is going to go away, and I wonder if some puzzles would rate much much harder if it wasnt employed.

Given that its not immediately apparent just how many different unavoidable sets there are in any one completed grid solution [and there are a huge number of], how far can /do people take this technigue ?

I note Ruud has in mind to post
Ruud wrote:Lexicon of known Deadly Patterns

I will complete this section later. It will contain a canonicalized representative of each type of pattern.
At what size of unavoidable set do uniqueness test become impractical ?

If it was possible and all medium and/or large unavoidable sets [greater than ? 14 clues] were employed as a technique every puzzle would be solved with uniqueness methods !!

From Red Ed
Code: Select all
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|       Nr Clues|    4|    5|    6|    7|    8|    9|   10|   11|   12|
|Nr Unavoidables|    1|    0|    4|    0|    9|    3|   47|   44|  416|
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+

+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|       Nr Clues|   13|   14|   15|   16|   17|   18|   19|   20|   21|
|Nr Unavoidables|  849| 5182| 9834|20021|16753|18461|13362|12552| 9486|
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+

+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|       Nr Clues|   22|   23|   24|   25|   26|   27|   28|   29|   30|
|Nr Unavoidables| 7912| 6252| 4818| 3556| 2615| 1836| 1320|  830|  516|
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+

+---------------+-----+-----+-----+-----+-----+-----+-----+-----+
|       Nr Clues|   31|   32|   33|   34|   35|   36|   37|  38+|
|Nr Unavoidables|  334|  217|  120|   63|   32|   14|    7|    0|
+---------------+-----+-----+-----+-----+-----+-----+-----+-----+


This is complete for the small sizes - but far from complete in the larger sizes !!!!!

The post goes on to list a representative examples of size 6,8 & 9 unavoidable sets.

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby re'born » Wed Oct 03, 2007 12:19 pm

coloin wrote:At what size of unavoidable set do uniqueness test become impractical ?

For me it's not the size of the unavoidable set that matters (BUG+n grids can use a lot of cells and are very easy to spot), but the number of extra candidates that obstruct the puzzle from reducing to a deadly pattern.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby coloin » Fri Oct 05, 2007 10:40 am

re'born wrote:For me it's not the size of the unavoidable set that matters (BUG+n grids can use a lot of cells and are very easy to spot), but the number of extra candidates that obstruct the puzzle from reducing to a deadly pattern.


I dont know how you can say they are easy to spot !

Size 4 "deadly pattern" is fairly obvious......but extending the princeple to size 8 is a bit trickier, and anything above 12 must be difficult......

Here are the reprsentatives of the size 8s.....
Code: Select all
T1
-----------
1..|2..|3..
.2.|3..|1..
...|...|...
-----------
21.|
...|
...|
-----------

T2
-----------
1..|2..|...
.2.|...|1..
...|1..|2..
-----------
21.|
...|
...|
-----------

T3
-----------
1..|2..|...
.2.|1..|...
...|...|...
-----------
2..|.1.|
.1.|.2.|
...|...|
-----------

T4
-----------
1..|2..|...
.2.|1..|...
...|...|...
-----------
2..|...|1..
.1.|...|2..
...|...|...
-----------

T5
-----------
1..|2..|...
.2.|.1.|...
...|...|...
-----------
2..|1..|
.1.|.2.|
...|...|
-----------

T6
-----------
12.|3..|...
..3|1..|...
...|...|...
-----------
231|
...|
...|
-----------

T7
-----------
1..|2..|4..
2..|3..|...
3..|4..|1..
-----------

T8
-----------
12.|3..|4..
34.|2..|1..
...|...|...
-----------

T9
-----------
12.|4..|...
34.|1..|...
...|...|...
-----------
23.|
...|
...|
-----------


I suppose the "T5" unavoidable can be spotted easily.

The nagging worry I have is that unavoidable sets are derived from a complete grid......not something you have access to if you havnt yet solved the puzzle !

Although many of the grid solutions will have unavoidable sets in common, so perhaps it will work.

I must say that I never realized there was so many unavoidable sets until it was pointed out to me - and I was very surprized.........maybe it hasnt hit home yet ?

So using T1
Code: Select all
-----------
1..|2..|3..
.2.|3..|1..
...|...|...
-----------
21.|
...|
...|
-----------
and its converse
-----------
2..|3..|1..
.1.|2..|3..
...|...|...
-----------
12.|
...|
...|
-----------


Has anyone really used this type of unavoidable/deadly pattern in a uniqueness method ?

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby ronk » Fri Oct 05, 2007 11:57 am

coloin wrote:Has anyone really used this type of unavoidable/deadly pattern in a uniqueness method ?

I'm sure there are quite a few in the form of BUG+N and BUG-Lite+N patterns. One by RW is here. Also, these threads started by Jeff and Myth Jellies, respectively, should have many more.

The BUG (Bivalue Universal Grave) principle

Between Uniqueness and BUG: BUG Lite
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby coloin » Fri Oct 05, 2007 12:37 pm

Thank-you......
I must confess I switch off when the the "BUG" word is used.
Perhaps I will have to re-evaluate my princeples !

Well I am sure the various hitch-hikers will be interested in the classification system of BUG-lites and how far it can be taken.......

Please could you explain what your colleagues on "Eureka" are arguing about ?

Its entertaining [slightly] - but I wish I could fathom out who believes what and whether it is logically correct to assume uniqueness

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby ronk » Fri Oct 05, 2007 3:01 pm

coloin wrote:Please could you explain what your colleagues on "Eureka" are arguing about ?

Its entertaining [slightly] - but I wish I could fathom out who believes what and whether it is logically correct to assume uniqueness

Other than saying I have very few colleagues there, I have no comment.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby coloin » Fri Oct 05, 2007 3:10 pm

I do understand !

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby Ruud » Fri Oct 05, 2007 6:32 pm

coloin wrote:Please could you explain what your colleagues on "Eureka" are arguing about ?

Everything.:(

- Uniqueness
- Bifurcation
- Trial & Error
- Acceptability of techniques (in general)
- Who invented what
- Forum etiquette
- Status & reputation
- Notation systems
- Reversibility

Name any sudoku-related subject, and I can show you a thread on Eureka that argues about it.

Must be a tough job for the guy who's moderating that forum...
Ruud
 
Posts: 664
Joined: 28 October 2005

PreviousNext

Return to Advanced solving techniques