Great Monster Loops

Advanced methods and approaches for solving Sudoku puzzles

Postby champagne » Sun Oct 26, 2008 10:50 pm

Hi Allan,

Here a selection in my list of hard puzzle of some puzzle giving something different

Code: Select all
100000005020400060003000700040006000000049080002800000000050100060900020007000003 col803# 98781   


Code: Select all
1     789   46   |2367  236789 2378  |23489 349    5     
5789  2     589  |4     13789  13578 |389   6      189   
46    589   3    |1256  12689  1258  |7     149    12489
--------------------------------------------------------
35789 4     1589 |12357 1237   6     |2359  13579  1279 
3567  1357  156  |12357 4      9     |2356  8      1267 
35679 13579 2    |8     137    1357  |34569 134579 14679
--------------------------------------------------------
23489 389   489  |2367  5      23478 |1     479    46789
3458  6     1458 |9     1378   13478 |458   2      478   
24589 1589  7    |126   1268   1248  |45689 459    3


floors1357 permutations =85
Code: Select all
N:.....................................X...........XX..............................
R:.XXXXX.XX.........XX.XXXXX...........XXXXX.XX.........XX.XXXXX...................
C:.XXXXX.XX.........XX.XXXXX..........XXXX.XXX..........XX.XXX.XX..................
B:.XXXXXXX...........XXXXXXX..........XX.XXXX.X.........XX.XXX.XX..................
  1        2        3        4        5        6        7        8        9       
HC.x.xxxxx.x.x.xxx.x.x.xxx.xxx.xxx.xxxx.xx..x.xxx....xxxxx.x.x.xxx.x.xxx.xxx.xxxxx.

NE..................................x....x.........................................
1: r3c9
3: r4c5

Nothing really special, just a mix not to rich candidates and nodes


Code: Select all
100000005020400060003000700040809000000046080000000200007001000080900020500000300 col807# 95104     


Code: Select all
1     679    4689  |2367  236789 2378 |489   349    5     
789   2      589   |4     135789 3578 |189   6      1389   
4689  569    3     |156   15689  58   |7     149    2     
----------------------------------------------------------
2367  4      1256  |8     12357  9    |156   1357   1367   
2379  13579  1259  |12357 4      6    |159   8      1379   
36789 135679 15689 |1357  1357   357  |2     134579 134679
----------------------------------------------------------
23469 369    7     |2356  23568  1    |45689 459    4689   
346   8      146   |9     3567   3457 |1456  2      1467   
5     169    12469 |267   2678   2478 |3     1479   146789

Code: Select all
4: r8c9r9c89   
 floors4  permutations =8
actifs
R:...........................X.X..XXXX.............................................
C:...........................X.X..XXXX.............................................
B:...........................X.X..XXXX.............................................
  1        2        3        4        5        6        7        8        9 


An example where the start of my solver is three turbots

Code: Select all
000100030000000065003060800008090006070002000000400000009080050020001000400700900 col080502


Code: Select all
256789 45689 24567 |1   2457 45789 |247    3     2479   
12789  1489  1247  |238 2347 34789 |1247   6     5     
12579  1459  3     |25  6    4579  |8      12479 12479 
-------------------------------------------------------
1235   1345  8     |35  9    357   |123457 1247  6     
13569  7     1456  |68  135  2     |1345   1489  13489 
123569 13569 1256  |4   1357 68    |12357  12789 123789
-------------------------------------------------------
1367   136   9     |236 8    346   |123467 5     12347 
35678  2     567   |9   345  1     |3467   478   3478   
4      13568 156   |7   235  356   |9      128   1238   

floors156 permutations =4745
N:..........................................................................X......
R:.XXXXXX.X...........................X.XXXX.XXX...XXXXX...........................
C:XXX.X.XXX...........................XXXXXXX..XXXX.XX.............................
B:X.XXXXX.X...........................XX.XXXXX.X..XX.XXX...........................
1 2 3 4 5 6 7 8 9
total =61 sets actifs
HCxxx.xx...xxx...x..xx.x.x.xxxx.x.xxx.x.xxx.xxxxxx.xxxxxxx.x.xx.xx.x.x.x...x..xx.xx
assigned 6: r5c4
eliminations
6: r5c13r6c6r7c4
NE.......................................x.........................................

here a mix with the three cases : asigment, eliminations of candidates and node to clear

and the same results using floors 236
Code: Select all
N:.........................................................X.......................
R:.........XXXX.XX.X.X.XXXXXX..................X...XXXXX...........................
C:.........X.XXX.XXXXX.XXXX.X..................XXXX.XX.............................
B:.........XXXX.X.XX.X.XXXXXX..................X..XX.XXX...........................
  1        2        3        4        5        6        7        8        9       
total =61 sets actifs
HCxxx.x.x.xx.xxxxx..x..x...xxxx.x.xxx.x.xxx.x.xxxx.xxxxxxx...xx.xx.x.x.x.x.xx.xx.xx

and with floors 567
Code: Select all
N:.................................................................X...............
R:....................................X.XXXX.XXX...XXXXXXXXX.XXX...................
C:....................................XXXXXXX..XXXX.XX..X.X.XXXXX..................
B:....................................XX.XXXXX.X..XX.XXXXXX.XXX.X..................
  1        2        3        4        5        6        7        8        9       
total =61 sets actifs
HCxxx.xxx.xx.x.xxx..xx.x.x.xxxx.x.xxx.x.xxx.x..xxx.xxxxxxx.x.xx.xx...x.xxx.xx.xx...

using floors 357, only the clearing of another node appears
éliminations trouvées
Code: Select all
NE...................................................................x.............
 floors357  permutations =6525
N:..............................X.X................................................
R:...................X.XXXXXX.........X.XXXX.XX.........XXXX.XXX...................
C:..................XX.XXXX.X.........XXXXXXX...........X.X.XXXXX..................
B:...................X.XXXXXX.........XX.XXXXX..........XXX.XXX.X..................
  1        2        3        4        5        6        7        8        9       
total =65 sets actifs
HCxxx.xxx.xx.xxxxx..xx.x.x.xxxx....xx.x.x.x.x.xxxx.x.xxxxx.x.xx.xx.x.x.xxx.xx.xx..x

Code: Select all
000010005020400090003000700040006000000049080000800002007000100060900020500000003 col810# 95384   


Code: Select all
46789  789   4689  |367   1     378    |2     346    5   
1678   2     1568  |4     35678 3578   |368   9      168 
1468   158   3     |256   9     258    |7     146    1468
---------------------------------------------------------
123789 4     12589 |12357 2357  6      |359   1357   179 
12367  1357  1256  |12357 4     9      |356   8      167 
13679  13579 1569  |8     357   1357   |34569 134567 2   
---------------------------------------------------------
23489  389   7     |2356  23568 23458  |1     456    4689
1348   6     148   |9     3578  134578 |458   2      478 
5      189   12489 |1267  2678  12478  |4689  467    3   


I'll come back with an edit for that one.
The solver did not find any possibility combining up to four floors.
I added a possibility to combine five floors and I will check it to day.

Code: Select all
000001009000000085009050060008030006070002000100400000003080050400700000020000300 col401# 98353 



Code: Select all
235678 34568 24567 |2368  2467  1     |247    2347  9     
2367   1346  12467 |2369  24679 4679  |1247   8     5     
2378   1348  9     |238   5     478   |1247   6     12347
---------------------------------------------------------
259    459   8     |159   3     579   |124579 12479 6     
3569   7     456   |15689 169   2     |14589  1349  1348 
1      3569  256   |4     679   56789 |25789  2379  2378 
---------------------------------------------------------
679    169   3     |1269  8     469   |124679 5     1247 
4      15689 156   |7     1269  3     |12689  129   128   
6789   2     167   |1569  1469  4569  |3      1479  1478 

A second example with two possibilities to combine 4 floors

The best one
floors1247 permutations =9
Code: Select all
N:......X........X........X.....................................X..................
R:.XXXX.XXXXXXX.XXX..........XXXXX.X.X..................XXXX.XX.X..................
C:.XXXX.XXXX.XXX.XXX..........XX.XXXXX..................X.X.XXXXX..................
B:X.X.XXXXXXXXX.X.XX.........XXXX.X.XX..................XXX.XXX.X..................
  1        2        3        4        5        6        7        8        9       
HCxxxxx..x.xxxxxx...xx.x.x..xxx.x.xxx...xxx.xxx..x.xxxxxxx.x.xx...xx.x.xxxx.xxxx.xx

1: r4c8r5c47r7c7r8c279r9c49
2: r1c148r2c4r678c7
4: r1c28r2c36r57c7r9c6
7: r1c18r2c67r3c1r4c7r6c67r7c9r9c1
NE..x.x......x.x............x.......x......................x.....................x.


and a very limted effect (one node to clear) using
floors1678 permutations =16150
actifs
Code: Select all
N:..........................................................................X......
R:.XXXX.XXX....................................XX..XXXXXXXXX.XX.XX.X.XX.XX.........
C:.XXXX.XXX....................................XXXXXXX..X.X.XXXXXXX.X.XX.X.........
B:X.X.XXXXX....................................XX.XX.XXXXXX.XXX.XXX..XXX.X.........
  1        2        3        4        5        6        7        8        9       
HCxxxxx.xx.xxxxxxx..xx.x.xx.x...x.xxx.x.xxx.xxx.xx.xxxxxxx.x.xx.x.xx.x.xxxx..xxx.xx

NE........................................................................x........
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sun Oct 26, 2008 11:10 pm

Hi again,

Some days, you are lucky. It seems that extension to 5 floors worked immediatly.
My first idea was to edit the previous post, having several results, I find better to show it individually

Code: Select all
000010005020400090003000700040006000000049080000800002007000100060900020500000003 col810# 95384 


Code: Select all
46789  789   4689  |367   1     378    |2     346    5   
1678   2     1568  |4     35678 3578   |368   9      168 
1468   158   3     |256   9     258    |7     146    1468
---------------------------------------------------------
123789 4     12589 |12357 2357  6      |359   1357   179 
12367  1357  1256  |12357 4     9      |356   8      167 
13679  13579 1569  |8     357   1357   |34569 134567 2   
---------------------------------------------------------
23489  389   7     |2356  23568 23458  |1     456    4689
1348   6     148   |9     3578  134578 |458   2      478 
5      189   12489 |1267  2678  12478  |4689  467    3   


No outlet found by the solver combining up to four floors.
We know that increasing the number of floors we must find possibilites (taking all floors, we have in once all false candidates elimnated).

What I don't know is whether this is still feasible to extract sets/linksets patterns, but Allan will tell us.
We have seven possibilties to combine succesfully floors. I give all of them.


floors12357 permutations =43 (may be the best)

Code: Select all
N:..............................XX..X..X.X.........XX..............................
R:.XXXXX.XX..XXX.X.XXX.XXXXX...........XXXXXXX..........XX.XXX.XX..................
C:XXXX.X.XXX.XXXX...XX.XXXXX...........XXXXXXX..........XX.XXX.XX..................
B:X.XXXXXX..X.XX.XX..XXXXXXX..........XX.XXX.XX.........XX.XXX.XX..................
  1        2        3        4        5        6        7        8        9       
HCxx.x.x.x.x.x.xxx.xxx.x.x.xxx.x...x.xx.x...x.xxxx...xx.xx.xxx.x.x.x.xxx.x.xxxxx.x.

1: r6c1
3: r7c56
5: r6c37
NE....................................x.x.............................x............




floors13457 permutations =89

Code: Select all
N:..................................X..X...........XX..............................
R:.XXXXX.XX.........XX.XXXXX.X.X..XXXX.XXXXXXX..........XX.XXX.XX..................
C:XXXX.X.XX.........XX.XXXXX.X.X..XXXX.XXXXXXX..........XX.XXX.XX..................
B:X.XXXXXX...........XXXXXXX.X.X..XXXXXX.XXX.XX.........XX.XXX.XX..................
  1        2        3        4        5        6        7        8        9       
HCxxxx.x.x.x.x.xxx.xxx.x.x.xxx.xxx.x.xx.xx..x.xxxx...xx.xx.xxx.xxx.x.xxx.x.xxxxxxx.

3: r7c5
5: r6c7
NE...................................................................xx............



floors13567 permutations =112
Code: Select all
N:...X..............................X..X....X.X....XX..............................
R:.XXXXX.XX.........XX.XXXXX...........XXXXXXX.XXX.XXX.XXX.XXX.XX..................
C:XXXX.X.XX.........XX.XXXXX...........XXXXXXX.X.XXX.XXXXX.XXX.XX..................
B:X.XXXXXX...........XXXXXXX..........XX.XXX.XXXXXX.X.XXXX.XXX.XX..................
  1        2        3        4        5        6        7        8        9       
HCxxx..x.x.x.x.xxx.xxx.x.x.xxx.xxx.x.xx.xx.....xxx...xx.xx.xxx.xxx.x.xxx.x.xxxxxxx.

1: r6c3
3: r7c5
5: r6c7
6: r5c13r6c78




floors13578 permutations =125
Code: Select all
N:.....X........X....X..............X..X...........XX................X.............
R:.XXXXX.XX.........XX.XXXXX...........XXXXXXX..........XX.XXX.XXXXXX..XXX.........
C:XXXX.X.XX.........XX.XXXXX...........XXXXXXX..........XX.XXX.XXXXX.XXX.X.........
B:X.XXXXXX...........XXXXXXX..........XX.XXX.XX.........XX.XXX.XXXXXX..XXX.........
  1        2        3        4        5        6        7        8        9       
HCxxxx...x.x.x.x.x.xx..x.x.xxx.xxx.x.xx.xx..x.xxxx...xx.xx.xxx.xxx.x..xx.x.xxxxxxx.

8: r2c3r89c6



floors13579 permutations =135
Code: Select all
N:.................................XXX.X........X..XX..............................
R:.XXXXX.XX.........XX.XXXXX...........XXXXXXX..........XX.XXX.XX.........X..X.XX.X
C:XXXX.X.XX.........XX.XXXXX...........XXXXXXX..........XX.XXX.XX.........XXX...X.X
B:X.XXXXXX...........XXXXXXX..........XX.XXX.XX.........XX.XXX.XX.........X..X.XX.X
  1        2        3        4        5        6        7        8        9       
HCxxxx.x.x.x.x.xxx.xxx.x.x.xxx.xxx....x.xx..x.xx.x...xx.xx.xxx.xxx.x.xxx.x.xxxxxxx.

1: r6c3



floors23567 permutations =1130
Code: Select all
N:...X.................X.........X..........X......X.......X.......................
R:...........XXX.X.XXX.XXXXX...........XXXXXXX.XXX.XXX.XXX.XXX.XX..................
C:.........X.XXXX...XX.XXXXX...........XXXXXXX.X.XXX.XXXXX.XXX.XX..................
B:..........X.XX.XX..XXXXXXX..........XX.XXX.XXXXXX.X.XXXX.XXX.XX..................
  1        2        3        4        5        6        7        8        9       
HCxxx..x.x.x.x.xxx.xxx...x.xxx.xx..xxxxxxx....xxxx..xxx.xx..xx.xxx...xxx.x..xxxxxx.
6: r9c4


floors24689 permutations =1079

Code: Select all
N:..X...........................................................X...............X..
R:...........XXX.X.X.........X.X..XXXX.........XXX.XXX.X.........XXXX..XXXX..X.XX.X
C:.........X.XXXX............X.X..XXXX.........X.XXX.XXX.........XXX.XXX.XXXX...X.X
B:..........X.XX.XX..........X.X..XXXX.........XXXX.X.XX.........XXXX..XXXX..X.XX.X
  1        2        3        4        5        6        7        8        9       
HCxx.x.x.x.x.x.xxx.xxx.x.x.xxx.xxx.x.xx.xx..x.xxxx...xx.xx.xxx.x.x.x.xxx.x.xxxxx.x.

8: r8c6
champagne
2017 Supporter
 
Posts: 5653
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Mon Oct 27, 2008 3:17 am

Allan, a couple of questions: For a given puzzle state (pencilmarks), is your program capable of ...
  1. finding the smallest rank0 constraint set(s) for any elimination(s):?:
  2. exhaustively searching for all different rank0 constraint sets that result in an identical set of elimination(s):?:
[edit: Constraint sets with identical strong sets but different weak sets would also be considered "different" in my POV.]
Last edited by ronk on Mon Oct 27, 2008 3:09 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Mon Oct 27, 2008 6:48 am

Champagne,

Champagne wrote:Here, what tells me the solver for the three puzzles at the top of my list of hardest (including Golden Nugget, number 3)

Just some initial feedback. So we can talk about your logic, here is some notation:

U = set of all occupied sets in a puzzle (usually about 300)
P = group all candidates in some logic
S = set of all sets in some logic (every node is in the logic)
L = set of all linksets in some logic (some or all nodes in logic)
X = all sets *not* in some logic

Right now, your logic is all S, no linksets yet. After slimfast you would have S + L.

I looked at the first three puzzles. SP, col809# 92145 (COL) and GN,

In my analyzer, there are no eliminations from X(SP), X(COL), or X(GN)

1) GN. If I add one more set/linkset to cell N79 (a cell set), I get the elimination r7c9<>3, which is correct.
2) SP. If I add one linkset to cell N48 *or* N52, no eliminations. If I add linksets to both N48 and N52, then I get the correct two eliminations, N48<>2 N52<>8.

I think you are missing some of the required constraints.

I have found the loop in SP for N48<>2 N52<>8, it uses 15 sets, maybe this can help. (It may not be the same as a loop you find, but close.

I see what you mean about Silver Platter, it is worse than Golden Nugget. I have one more loop before this one, eliminates
one candidate.

Code: Select all
set
5R4: 548===========================546A=549==541==546A
      |                            544   |    |    |                                               
      |                             |    |    |    |                                               
5R2:  |                             |    |   521==526==525                                         
      |                             |    |    |    |    |                                           
5R5:  |                       552==554==559==551   |    |
      |                        |    |    |         |    |                                           
5R8:  |                        |    |   589=======586==585                                         
1C8: 148=======138==168==178   |    |              |    |
      |         |    |    |    |    |              |    |                                           
1C4:  |   144==134   |    |    |    |              |    |                                           
      |   154        |    |    |    |              |    |                                           
1C2:  |    |        162==172==152   |              |    |
      |    |         |         |    |              |    |
6N6:  |    |         |         |   566G===========566G==|===766H===========766H=366F=366F           
      |    |         |         |    |                   |    |              |    |    |             
6N5:  |   165B======165B=======|===565D================565D=765E===========765E=365C=365C
      |                        |                             |              |    |    |             
3C4:  |                        |                             |              |    |   344==394==314 
      |                        |                             |              |    |   354   |    |
      |                        |                             |              |    |         |    |   
7C4:  |                        |                             |   734==774==744   |         |    |   
      |                        |                             |    |    |   754   |         |    |
7C2:  |                       752===========================762==732   |         |         |    |
      |                        |                             |         |         |         |    |
7C8: 748=======================|============================768=======778        |         |    |   
      |                        |                                                 |         |    |   
3C2:  |                       352===============================================362=======392   |   
      |                                                                          |              |   
3C8: 348========================================================================368============318 
                                                                                                   
All notation is NCR format
'=' strong set                       |         |     }
'|' weak set                        165B======165B=  } same candidate in 2 sets
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ttt » Mon Oct 27, 2008 7:08 am

Hi Allan & champagne,

For Silver Plate, I took long… long times to study it. It seems SK loop with [(13) & (57)] but 1’s at r8c79, then I try to study as a “Almost SK loop” : if r8c7=1 or r8c9=1 => …nothing the same as SK loop deductions when r8c79<>1… Must be more time for this:D

ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby champagne » Mon Oct 27, 2008 7:50 am

Allan Barker wrote:I think you are missing some of the required constraints.


In my turn a quick feedback before I analyze your post.

What I did is just to apply a "focusing step" to select groups of floors leading to "eliminations/assignments".

There is no slimfast program applied here. All sets belonging to the selected floors contribute to the permutation process. I only made a restriction on nodes to reduce the number of permutations. Only nodes having no extra candidates (not belonging to the floors) contribute to the permutations till the final step.

What I forecast is that you should find a sets/linksets organization giving the same results (maybe partial) using only sets belonging to the group selected.

I can be wrong.

What is for sure is that what I have shown as "eliminated" is not allowed in permutations (subject to no bug in the program) valid for that group.

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

Postby champagne » Mon Oct 27, 2008 7:59 am

ttt wrote:Hi Allan & champagne,

For Silver Plate, I took long… long times to study it. It seems SK loop with [(13) & (57)] but 1’s at r8c79, then I try to study as a “Almost SK loop” : if r8c7=1 or r8c9=1 => …nothing the same as SK loop deductions when r8c79<>1… Must be more time for this:D

ttt


I have a long and boring solution (20% longer than GN ) I never published. I must confess I never digged in it.

I had the feeling nobody would be interested by the result and GN was enough..

Another reason is that I hope, thru work in progress to come to something easier to digest.

I can try to summarize the way the solver cracks it if you want.

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

Postby Allan Barker » Mon Oct 27, 2008 8:51 am

Ronk wrote:Allan, a couple of questions: For a given puzzle state (pencilmarks), is your program capable of ...
finding the smallest rank0 constraint set(s) for any elimination(s)
exhaustively searching for all different rank0 constraint sets that result in an identical set of elimination(s)
[edit: Constraint sets with identical strong sets but different weak sets would be considered "different" in my POV.]

Ronk, I think you question is clear, let me try for a clear answer.

The software has a small solver and a large solver integrated to an editor/analyzer. Some things will be done by a solver and some can done in the E/A after eliminations are found. The small solver does exhaustive search and is comfortable up to 6-10 sets or about 20 to 25 candidates. The big solver (one used for monsters) is not exhaustive but can go to almost any size.

The answer for the small solver is yes to both. You can include higher ranks or choose a particular rank like 1. It may also find different groups of strong sets that eliminate the same candidate, say a fish and a chain. The E/A can also find different (weak) constraint sets. I.e., it will fill in the weak sets for a given set of constraints.

The big solver will not guarantee the smallest elimination but often comes close. It will often provide a number of examples but may miss some configurations.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Mon Oct 27, 2008 9:11 am

Hi Allan,

I now make quick comments to your post.


Right now, your logic is all S, no linksets yet. After slimfast you would have S + L.
In my analyzer, there are no eliminations from X(SP), X(COL), or X(GN)


I am not sure I catch your point here.

. my logic is analysing permutatons in a group of floors and linking Cells/Nodes in that "focusing step";
. the definition for 'X' is not clear to me.

but it does not affect the rest.


1) GN. If I add one more set/linkset to cell N79 (a cell set), I get the elimination r7c9<>3, which is correct.
2) SP. If I add one linkset to cell N48 *or* N52, no eliminations.
If I add linksets to both N48 and N52, then I get the correct two eliminations, N48<>2 N52<>8.


. difficult to figure out what you mean precisely, especially after I analyzed your loop. In SP loop, I did not see any addition to the group of sets I printed. May be you want to say that you can not find the loop if you start a growing program only with the target?
. for me nothing estonishing if you need both N48 and N52 to build a sets/linksets structure

I have found the loop in SP for N48<>2 N52<>8, it uses 15 sets, maybe this can help.
(It may not be the same as a loop you find, but close.
I see what you mean about Silver Platter, it is worse than Golden Nugget. I have one more loop before this one, eliminates
one candidate.


. unhappily, I am not yet in a position to find sets/linksets groups and I had no time to work recently on that topic.
. You say you have another loop, I am interested to know if it uses more than four floors.
My program says it is not possible to find other clearings with only four floors, but I did not reduce the number of permutations using nodes with extra candidates, so I can miss some eliminations.


And now your sets/linksets diagram.

This is exactly what I was expecting.
All sets and linksets are in the group I used.

Now I have just to find:

The appropriate slimfast program,
The rank calculation.
Code: Select all
I see we have here 15 sets and 19 linkset -> rank 4.
  If I am right, 8 triple points, all linkset form.
  and we must conclude N48 N52 are rank 0.

still some work for me.

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

Postby Allan Barker » Mon Oct 27, 2008 5:22 pm

champagne wrote:
Allan wrote:Right now, your logic is all S, no linksets yet. After slimfast you would have S + L.
In my analyzer, there are no eliminations from X(SP), X(COL), or X(GN)


Uh-oh, super dylsexia, I mean that set groups
S(Silver P), S(Coloin's puzzle), or S(Golden N) produce no eliminations by themselves, I must add some more linksets

Srooy, Allan
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Allan Barker » Sat Nov 15, 2008 9:59 pm

Destruction of a Mild Monster, Top1465 #2

Following 999_Springs lead here , I took a look at this ER = 9.5 puzzle to see if I could understand it's hardness level. The results provide a little more insight into nature of initial SK-type loops, so I thought to post it here.

What I found was a relatively small 13 set SK-like loop with no apparent symmetry and no way to morph the puzzle to a symmetrical form (that I could find). Otherwise, it shares all the logical qualities of other SK loops, i.e., it is rank 0 (like a swordfish) with equal numbers of sets and cover sets. It eliminates all external candidates in its 13 cover sets. It can be described as a single cell set in r4c5 connecred to 4 ALS each with 3 sets, for a total of 13 sets. The 4 ALS's are in a row, a row, a column , and a cell otherwise the logic looks fairlysymetrical.

The other point of interest is the loop virtually blasts the puzzle into singles. It does this by eliminating 31 candidates, after wihci there is very little left except perhaps a hidden pair. Below are details and a thumb.

Code: Select all
EPRC 36 Nodes, Raw Rank = 0 (linksets - sets)
     13 Sets = {578r2 269r5 578c2 4n5 7n157}
     13 Links = {12r7 5c5 7c7 2n89 5n236 6n2 9n2 9b5 8b7}
   (5c5) => r1c5<>5, (2n8) => r2c8<>4, (2n8) => r2c8<>6, (2n9) => r2c9<>9,
   (9b5) => r4c4<>9, (9b5) => r4c6<>9, (7c7) => r4c7<>7, (5n2) => r5c2<>1,
   (5n3) => r5c3<>1, (5n3) => r5c3<>7, (5n6) => r5c6<>4,
   (5n6) => r5c6<>7, r5c6<>9,          (7c7) => r5c7<>7, (6n2) => r6c2<>2,
   (6n2) => r6c2<>6, (5c5) => r6c5<>5, (7c7) => r6c7<>7, (1r7) => r7c3<>1,
   (2r7) => r7c3<>2, (2r7) => r7c6<>2, (1r7) => r7c8<>1, (8b7) => r8c1<>8,
   (8b7) => r9c1<>8, (9n2) => r9c2<>1, (9n2) => r9c2<>2, (9n2) => r9c2<>3,
   (9n2) => r9c2<>6, r9c2<>8,          (5c5) => r9c5<>5, (7c7) => r9c7<>7


Code: Select all
 +--------------------------------------------------------------------------------------+
  | 7        126      8        | 459      4569     4569     | 3        1456     1259     |
  | 469      36       3469     | 2        3469(5)  1        | 469(7)   46(578)  9(578)   |
  | 5        1236     123469   | 78       3469     78       | 12469    146      129      |
  +--------------------------------------------------------------------------------------+
  | 189      4        1579     | 3579     (59)     3579     | 178      2        6        |
  | 3        1(267)   17(269)  | 47(9)    8        47(269)  | 147      1457     157      |
  | 268      26(578)  2567     | 1        2456     24567    | 478      9        3        |
  +--------------------------------------------------------------------------------------+
  | (128)    9        12357    | 6        (125)    2358     | (127)    1378     4        |
  | 12468    1236(8)  12346    | 3489     7        23489    | 5        1368     1289     |
  | 12468   1236(578) 1234567  | 34589    12459    234589   | 12679    13678    12789    |
  +--------------------------------------------------------------------------------------+


Code: Select all
     5c5  2n8  2n9  7c7  1r7  2r7  8b7  9n2  6n2  5n2  5n3  5n6  9b5

7N5: 575=================175==275                                     
      |                   |    |                                     
5R2: 525==528==529        |    |                                     
      |    |    |         |    |                                     
8R2:  |   828==829        |    |
      |    |    |         |    |                                     
7R2:  |   728==729==727   |    |                                     
      |              |    |    |                                     
7N7:  |             777==177==277                                     
      |                   |    |                                     
7N1:  |                  171==271==871                               
      |                             |                                 
8C2:  |                            892B=892B=862                     
      |                            882   |    |                       
      |                                  |    |
5C2:  |                                 592==562                     
      |                                  |    |                       
7C2:  |                                 792==762==752                 
      |                                            |                 
6R5:  |                                           652==653==656       
      |                                            |    |    |       
2R5:  |                                           252==253==256       
      |                                                 |    |       
9R5:  |                                                953==956A=956A
      |                                                          954 
      |                                                           |   
4N5: 545=========================================================945 

Note: 956A=956A, and similar, same candidate sits in 2 cover sets


Thumb 2D grid drawing with set logic in the green heads up display.

Image
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby champagne » Sun Nov 16, 2008 12:01 am

Hi Allan,

Your top1465 _2 is an interesting example.
At the point where you started, you could have found a very simple SLG in floor 2 eliminating 2r9c2.
But I guess this was not your goal. This locks, for the time being, my search for more complex SLGs

Your SLG is not very big, but it is using six different digits: 256789.
It seems to me that such a solution can only come if you are exploring all possible paths to find a kind of "One shot" solution.

Using classical AIC's and AIC's nets, it is a "medium difficulty" puzzle.
If I apply a strategy to speed up the process, i find two AIC's:
. one using digits 5 and 9 eliminating 9r2c79
. one using digits 5,7,9 eliminating 7t5c236

For sure, you can find corresponding SLG's, but both are using AHS/ACs and I don't know yet how it is translated in SLGs

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

Postby denis_berthier » Sun Nov 16, 2008 12:03 am

Allan Barker wrote:Following 999_Springs lead here , I took a look at this ER = 9.5 puzzle to see if I could understand it's hardness level. The results provide a little more insight into nature of initial SK-type loops, so I thought to post it here.
What I found was a relatively small 13 set SK-like loop with no apparent symmetry and no way to morph the puzzle to a symmetrical form (that I could find). Otherwise, it shares all the logical qualities of other SK loops, i.e., it is rank 0 (like a swordfish) with equal numbers of sets and cover sets. It eliminates all external candidates in its 13 cover sets. It can be described as a single cell set in r4c5 connecred to 4 ALS each with 3 sets, for a total of 13 sets. The 4 ALS's are in a row, a row, a column , and a cell otherwise the logic looks fairlysymetrical.


Two questions.

1) Could you define more precisely what you call an "SK-like loop", especially if there is no symmetry in the pattern. Your description evokes less a loop than some central cell with petals.

I gave two different interpretations of the "SK-loop", here: http://forum.enjoysudoku.com/viewtopic.php?t=5894
When I activate any of them, I can't find any belt, even after the following whip eliminations (starting from your PM):
nrczt-whip-cn[4] n2{r9c1 r6c1} - n2{r6c3 r3c3} - n2{r3c7 r7c7} - {n2r7c5 .} ==> r9c2 <> 2
nrczt-whip-cn[4] n8{r2c9 r2c8} - n5{r2c8 r2c5} - {n5 n9}r4c5 - {n9r4c1 .} ==> r2c9 <> 9
nrczt-whip-rn[6] n7{r9c3 r9c2} - n7{r9c9 r2c9} - n8{r2c9 r2c8} - n5{r2c8 r2c5} - {n5 n9}r4c5 - {n9r5c6 .} ==> r5c3 <> 7
nrczt-whip-rc[10] n2{r9c1 r6c1} - n2{r6c5 r9c5} - n1{r9c5 r7c5} - {n1 n8}r7c1 - n8{r4c1 r4c7} - n8{r6c7 r6c2} - n5{r6c2 r9c2} - n7{r9c2 r5c2} - n7{r5c9 r6c7} - {n7r7c7 .} ==> r7c3 <> 2
nrczt-whip[21] n5{r6c2 r9c2} - n5{r9c4 r1c4} - n5{r2c5 r7c5} - {n5 n9}r4c5 - n9{r4c1 r2c1} - n9{r2c5 r1c6} - n6{r1c6 r5c6} - n9{r5c6 r5c3} - n2{r5c3 r5c2} - n7{r5c2 r6c2} - {n7 n6}r6c3 - {n6 n8}r6c1 - {n8 n1}r4c1 - {n1 n2}r7c1 - n2{r9c3 r3c3} - n2{r3c7 r9c7} - n9{r9c7 r3c7} - n6{r3c7 r2c7} - {n6 n3}r2c2 - {n3 n4}r2c5 - {n4r2c3 .} ==> r6c6 <> 5

after which there's no nrczt-whip (more complex whips are not - not yet? - in SudoRules).
Notice that the whip[21], although very long, is rather easy to find because there are not many whips.

If I have time, I'll try to see what I get with braids, but, as they are not programmed in SudoRules, I have to do this manually and you know I'm a little lazy for manual solving of hard puzzles.

Anyway, if there appears to be an interpretation of the "SK-loop" more general than mine, whatever it is, I'm interested if it can be described in terms of factual patterns.


2) Second question. ttt gave another, apparently much simpler, solution in the "abominable T&E" thread. What do you think of it? And, if it is really simpler, do you know why your solver didn't find it?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby ronk » Sun Nov 16, 2008 3:15 am

denis_berthier wrote:1) Could you [edit: Allan Barker] define more precisely what you call an "SK-like loop", especially if there is no symmetry in the pattern. Your description evokes less a loop than some central cell with petals.

A "best symmetry" isomorph of the top1465 #2 is ...
Code: Select all
 7 . 8 | . . . | 3 . .
 . . . | 2 . 1 | . . .
 5 . . | . . . | . . .
-------+-------+-------
 . 4 . | . . . | . 2 6
 3 . . | . 8 . | . . .
 . . . | 1 . . | . 9 .
-------+-------+-------
 . 9 . | 6 . . | . . 4
 . . . | . 7 . | 5 . .
 . . . | . . . | . . .
 top1465 #2

 . . . | . . . | . . .
 . 7 . | . . . | . . 5
 . . 6 | . . 9 | . 4 .
-------+-------+-------
 . . . | . 5 . | . . .
 . . . | 8 7 . | . . 3
 1 . 2 | . . . | . . .
-------+-------+-------
 . . . | . . 4 | 2 6 .
 . . 1 | . . . | 9 . .
 . 8 . | . 3 . | . . .
 top1465 #2 isomorph
 permutation: -pr(159)(268)(347)c(1526)(34)(798)

Allan, I would like to see the 2-D grid drawing for your "SK-like loop" deduction in this isomorph. Assuming you have the time, thanks in advance.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Allan Barker » Sun Nov 16, 2008 5:11 am

champagne wrote:At the point where you started, you could have found a very simple SLG in floor 2 eliminating 2r9c2.But I guess this was not your goal. This locks, for the time being, my search for more complex SLGs

I do see several shorter eliminations but found this one after searching around a bit. I was quite surprised to see 31 eliminations, so I focused on this elimination

By "lock" you mean that the simpler solutions prevent the solver from finding more complex eliminations, right? I often see this, too.

champagne wrote:Your SLG is not very big, but it is using six different digits: 256789. It seems to me that such a solution can only come if you are exploring all possible paths to find a kind of "One shot" solution.

Yes, I am looking for any path, as opposed to starting with floors. To the solver, multiple digits in a row/column are the same as one digit in several rows/columns. Of course, any is not the same as every.

champagne wrote:For sure, you can find corresponding SLG's, but both are using AHS/ACs and I don't know yet how it is translated in SLGs

This is an interesting point. In principle, there must be a (constraint) set description for any elimination path. However, a rule may embody this in various ways. Compared to computer languages, a rule might be C language and the 324 constraints would be assembly language. (?)
Allan Barker
 
Posts: 266
Joined: 20 February 2008

PreviousNext

Return to Advanced solving techniques