Set Logic Solns: Top1465#77, Easter Mons. Golden Nugget

Advanced methods and approaches for solving Sudoku puzzles

Re: It is 9 or 10 linkset?

Postby ronk » Fri May 30, 2008 5:56 pm

Allan Barker wrote:However, I count [... and] the tiny "end" linkset in row 8. Thats 10.
[...]
The thin dark gray line traveling all the way across row 8 and the thin gray square box surronding the cell linkset in r8c7 is a cursor I often turn on to show which sets are causing an elimination.

That's the one I missed. I was already conditioned to look for light blue, light red, light green, and tan.

Needless to say, I didn't find the "cursor" helpful. There must be an easy way to obtain a cursor function while retaining near-normal linkset coloring and size.

Is the cursor the reason for the "double border" on r8c7? Sort of a "cursor box" around the cell linkset? If so, couldn't a similar "cursor around" concept be used for row, column and box linksets?

More importantly, with a 5r8 linkset there would appear to be two linkset triples, not one ... with the second at 5r8c7. Please clarify.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Sat May 31, 2008 2:45 am

I was already conditioned to look for light blue, light red, light green, and tan............There must be an easy way to obtain a cursor function while retaining near-normal linkset coloring and size............couldn't a similar "cursor around" concept be used for row, column and box linksets?

This is all helpful feedback because I am accustomed to looking at the 3D images. I should force myself to look at 2D grids for a couple of weeks.

More importantly, with a 5r8 linkset there would appear to be two linkset triples, not one ... with the second at 5r8c7. Please clarify.

5r8c7 is the eliminated candidate so it sits in 2 linksets but has no connection to any set in the structure. This one is really clearer in 3D so I copied the 3D image which shows the overlapping cursors clearly.

Image
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Sat May 31, 2008 3:29 am

Allan Barker wrote:
ronk wrote:More importantly, with a 5r8 linkset there would appear to be two linkset triples, not one ... with the second at 5r8c7. Please clarify.

5r8c7 is the eliminated candidate so it sits in 2 linksets but has no connection to any set in the structure.

I certainly don't have a priori knowledge of the elimination. I first see two linkset triples. Then I must analyze the structure -- including the two linkset triples -- to see where an elimination might exist.

How is this approach not correct?

Are you suggesting that once I deduce the elimination, a linkset triple at that elimination is no longer a linkset triple? If so, IMO that's not an intuitive thought process ... and not a common sense description.

[edit: While your 3D images are pretty, I prefer using the 2D images. I find the 3D too abstract -- no row, column and digit numbers, for example. IOW, for the time being at least, you need not supply 3D images on my account.]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Sat May 31, 2008 4:23 am

I certainly don't have a priori knowledge of the elimination. I first see two linkset triples. Then I must analyze the structure -- including the two linkset triples -- to see where an elimination might exist.

How is this approach not correct?


There is nothing wrong with that approach that I see. However, there cannot be a linkset triplet at 5r8c7 because that candidate is not contained in any set in this structure.

Are you suggesting that once I deduce the elimination, a linkset triple at that elimination is no longer a linkset triple? If so, IMO that's not an intuitive thought process ... and not a common sense description.


No, I'm not.

I think we are looking at one thing and seeing two. To make sure we are seeing the same, can you tell me which one set and two linksets are attached to a triplet at 5r8c7?

Area of logic under question without cursor.
Image

Edit: adding .... Could the difference be from overlaying candidates and sets in the image, i.e. you are seeing a box set at 5b9 whereas the only box set int box 9 is 4b9?
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Sat May 31, 2008 3:28 pm

Allan Barker wrote:there cannot be a linkset triplet at 5r8c7 because that candidate is not contained in any set in this structure.
[...]
To make sure we are seeing the same, can you tell me which one set and two linksets are attached to a triplet at 5r8c7?

My mistake. That a linkset triple must contain a set candidate hadn't yet registered. I was interpreting it as any candidate in the intersection of two linksets.

I'll spend some time reading the basic descriptions on your website.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Sun Jun 01, 2008 10:12 am

The Idea of Uniform Rank

[Edit: replace previous argument on uniform rank with revised version. 3-6-08]

A key question about Sudoku set logic principles is, why would logic work in a way that guarantees a uniform rank over some region? In some ways, this seems counterintuitive, especially thinking about first order logic.

There is in fact a rational for such an effect, which is based on the logical permutations of candidates.

Given a rank 1 structure with 10 sets 11 linksets, the covering set principle says any two linksets must have at least one candidate, which is logically correct. But what makes sure there is always an arrangement of candidates that fulfills this requirement? Candidates are possibilities. Without constraints, all permutations or arrangements of candidates are possible, about one billion for this size problem. The number is much smaller because constraints remove most of them but without a constraint, or reason not to be there, all permutations are possible, and will be there. In this sense, the mathematics of combinorics fills every possible configuration that is not invalid, everywhere in the structure.

This turns the argument upside down, rather than why would a particular candidate or configuration be there, the correct question is why would it not be there? In the current example, if any two sets did not contain a candidate, that configuration must be invalid because it would force two candidates into one of the other sets.

In all cases, the areas presumed to have uniform rank are ones that also have uniform constraints. The rank rules require that each candidate is contained in only one set in each group, every candidate is in both groups, and no sets in the same group can overlap. When all permutations of an area with uniform constraints is considered, it probably should have uniform rank.

Although this does not prove anything, all things considered uniform rank seems reasonable.

[8-6-08]
Uploaded major revision of SudokuOne Web Site. Main differences are:
. Much shorter, the entire set theory derivation and explanation is now on one page.
. A new section with many simple examples of set theory principles.
. Full attention to previously sketchy areas, i.e., triplets, rank zones, summing of rank effects.

As usual, all feedback is welcome. rab.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Sun Jul 20, 2008 5:40 pm

Allan Barker, this has nothing to do with Easter Monster or the top1465 #77 but ...

Would you please tell me what your program finds for the following:?:

Sets: r1c4, r1c5, r2c6, r3c6, r4c6 and r6c4

Linksets: 5c4, 5b2, 8b2, 6c6, 9c6 and 3b5 plus "leftovers" 4r1c45

Code: Select all
 *-----------------------------------------------------------------------------*
 | 1       3457    9       | 45      458     2       | 378     478     6       |
 | 456     24567   8       | 1       3       69      | 279     2479    57      |
 | 3456    23456   23456   | 7       45689   5689    | 2389    1       358     |
 |-------------------------+-------------------------+-------------------------|
 | 7       2346    2346    | 8       269     369     | 1       5       49      |
 | 45      8       245     | 259     1       7       | 6       3       49      |
 | 356     9       1       | 35      56      4       | 78      78      2       |
 |-------------------------+-------------------------+-------------------------|
 | 345689  3456    34567   | 23459   24589   1       | 23789   26789   378     |
 | 34689   1       346     | 2349    7       389     | 5       2689    38      |
 | 2       35      357     | 6       589     3589    | 4       789     1       |
 *-----------------------------------------------------------------------------*
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Mon Jul 21, 2008 12:02 am

Ron, sure. Entering your solution I get:

rank 1 = 7-6, [r1c45 r234c6 r6c4].[4r1 5c4 69c6 58b2 3b5](T=5r1c4) 4r1 => r1c2<>4, r1c8<>4
rank 1 = 7-6, [r1c45 r234c6 r6c4].[ 5c4 69c6 458b2 3b5](T=5r1c4) 4b2 => r3c5<>4


where the intersecting cover sets at 5r1c4 (the T) make both 4r1 and 4b2 rank 0 to eliminate some 4s. This is listed as 2 eliminations to keep the counting right.

Searching gives me only one slight variation where cell sets r234c6 are swapped with column sets 358c6. Nothing else.
[Edit] Typo, there is only one triplet (T), not two.
Last edited by Allan Barker on Tue Jul 22, 2008 7:23 pm, edited 1 time in total.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Mon Jul 21, 2008 10:20 am

Allan Barker, thanks for the reply. I'll likely have some follow-on questions when I get back from a 2-week trip.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Fri Sep 05, 2008 11:31 am

Hi to all,

I have just placed a new set logic solution to Golden Nugget on my website and include a little data here. The full solution can be seen at: Solution to Golden Nugget
This solution is perhaps a different way of viewing the logic inside of the puzzle however, I agree with Champagne that this one is "a few times" more difficult than most monsters. Below is a chart that shows the relative difficulty of each move based on (blue) the number of sets used by the logic and (red) the number of nodes involved in the logic. Most difficult eliminations require around 20 - 25 sets and roughly 70 nodes. These eliminations fall into 3 groups of about 10 to 15 where each group is followed by an assignment. The assignments roughly correlate to the gaps between the 3 groups.

Image
Like the solution to Easter Monster, this solution uses a free form logic that can take on most any form. The first thing apparent from the solution is that many difficult eliminations are well beyond any simple interpretation using set logic rules. However, some interesting exceptions take a form where several single digit layers each form a strong inference group that then combine into a single group of vertical linksets that lead to eliminations. Such highly organized logic is a bit surprising and may indicate a logical weakness in this monster.

The first elimination uses 5 layers to make 5 SIS that combine into 5 vertical linksets, which thus become rank 0 to cause an elimination. This elimination is shown here (click on thumbnail).
Image

To demonstrate how this works, I have included a logic diagram for a simpler elimination that uses 4 levels where 3 levels form SIS that combine into 4 vertical sets. These are then "input" to layer 2 where the elimination occurs. The combined SIS input to layer 2 forces the column linkset containing 2r7c4 and 2r3c4 (p742 p342 in diagram) to be occupied and thus eliminates the candidate 2r1c4.

Code: Select all

p321=p121A==p131                                                                                           
 |     /\    |
 +----+  +---+
 |           |
 |          p171B=========================p391==p381                                                 
 |           |                             |     |
p721========p771==p741=====================|=====|==========p791                                     
             |     |                       |     |           |
            p471==p441=====================|=====|====p481   |                                       
                   SIS, Layer 1 ---->      |     |     |     |
                                           |     |     |     |          p632========p132
                                           |     |     |     |           |          p232
                                           |     |     |     +--+        |           |
                     Level 2 ---->         |     |     |     | p792H=====|====p742   |               
                                           |     |     |     |     \     |     |     |
                                           |    p382C=p482===|====p982==p682   |     |               
                                           |     |  #  |     |                 |     |
                                          p392==p382C==|=====|================p342==p312
                  SIS, Layer 4 ---->       |     |     |     |                 |     
                        p174==============p394F=p384D  |     |                 |                       
                        p274               |     |  #  |     |                 |                       
                         |    p324==p364==p394F=p384D  |     |  Elimination:  r1c4<>2                     
                         |     |     |     |     |     |     |
                        p474==p424===|=====|=====|====p484   |                                       
                         |           |     |     |     |     |
                        p774========p764===|=====|=====|====p794                                     
                  SIS, Layer 7 ---->       |     |     |
                                          p397G=p387E==|======================p367 
                                           |    |   #  |                       |
                                          p397G=p387E==|================p277   |   
                                                       |                 |     |
                                                      p487==============p477==p467 

====== (Strong) Set
------ (Weak) Linkset
   #   Designates 2 sets that are linked
   + 
p123   Same as 3r1c2

p174   2 Stacked Nodes = 2 nodes in box/link link
p274

p121A  Alphabetic letter used to label triplets, which may appear twice
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Sun Sep 14, 2008 6:52 am

Hi allan,

I'll have more time within next days to study your solution for GN.

1) Did you try silver plate? (for me it is harder)
2) My solver seems to be defeated by these two recent ones :

Code: Select all
........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........#tarx0001
........2..1...7...3..5..9......6.4...3.4.8...4.5.9....9..6..3...2...1..7....3...#tarx0006



It would be interesting to know if your's is more efficient

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

Postby coloin » Sun Sep 14, 2008 2:17 pm

Great work Allan.

I particularly liked the diagrams before - but couldnt follow [a long while back] them because I didnt have immediate access to the PM grid you were refering to - this has now been resolved and I recommend anyone to follow your links and marvel at the complexity of the solving paths.

Good luck with those other "critters"

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby Allan Barker » Sun Sep 14, 2008 9:13 pm

champagne wrote:
Did you try silver plate? (for me it is harder)

No, I haven't. I do note that for me Strmckr's EM like puzzle is much more difficult,... just after KZ loops, than EM.
My solver seems to be defeated by these two recent ones: It would be interesting to know if your's is more efficient

Great, I will give these puzzles a try, it will be interesting one way or the other. I would doubt that my solver is more efficient but it perhaps has more degrees of freedom. You could call one Platinum Pony but I don't know what comes after platinum, credit card companies have the same problem.

Coloin, thanks for the useful feedback, I have been trying to find better ways to describe 2nd order logic. At the same time, many of the GN eliminations are, thus far, beyond easy comprehension.

Now Champagne has worse ones.

Allan
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby coloin » Mon Sep 15, 2008 2:01 pm

Inspired by GN - I am afraid I extended the precious metal theme already - the word I have associated with platinum wasnt your word !

If the "critters" are worth naming I am sure tarek will come up with a suitable double initial !

Heres the few [apart from EM] which have been allocated a name/double initial !

Code: Select all
Cloudy Bay      #1.........2.4...6...3...5.1.4..86.......49.8....2.....5.7...3...6.9...4.........7
Bronze Medalian #1.......7.2.4...6...3...5...9..82.......9..8....6..4....5...1...6.8...2.7....3...
Silver Plate    #1.......7.2.4...6...3...5...9..4........62.4....9..8....5.....3.6.2...8.7....1...
Platinum Blonde #.......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...
Tungston Rod    #........7.2.4...6.1.....5...9...2.4....8..6..6..9.......5..3....3..8..2.7....4..1
Golden Nugget   #.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....
DukDiamond1     #1.......2.2.....6...34..5.....8.5.....8.3.9.....9.4.....5..34...7.....1.6.......7
DukDiamond2     #1.......2.2.....6...34..5.....8.5.....8.3.9.....9.4.....53..4...6......77......1.
WeeKender2      #..1.....7.2..4..6.3.....5...9.4.6.......92.4.......8....7..3....6..2..8.5.......1
WeeKender1      #........91......35..9.3.8....3.5...67....2......4.......6.8..9..2.7..6..4.....1..


C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby tarek » Mon Sep 15, 2008 2:53 pm

I figured that the 2 puzzles that defeated champagne's solver deserve a name:D

I think that their apparant difficulty is just an illusion, therfore:
tarx0001 = Fata Morgana
tarx0006 = Trompe-l'oeil (Thank you Champagne for your suggestions ... That is why this gets a French name)
Code: Select all
........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........#Fata Morgana
........2..1...7...3..5..9......6.4...3.4.8...4.5.9....9..6..3...2...1..7....3...#Trompe-l'oeil


No precious metals, however, I couldn't break the tradition of double initials:D

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

PreviousNext

Return to Advanced solving techniques