The New Sudoku Players' Forum

by **pjb** » Tue Jul 16, 2013 1:33 am

I have been following the MSLS threads with great interest, although struggling to keep up, and thought the old favorite 'golden nugget' would be a good one to try.

Code: Select all: 25678 14568 1247-56| 268 247-6 4678 | 1247 3 9 26789 4689 247-6 | 23689 247-36 1 | 247 2467 5 2679 1469 3 | 269 5 4679 | 8 12467 1247 ----------------------+-----------------------+---------------------- 235 345 8 | 135 9 357 | 123457 1247 6 3569 7 #456 | 3568-1 #136 2 | 13459 #1489 #1348 14 1 3569 #256 | 4 #367 3568-7 | 23579 #2789 #2378 27 ----------------------+-----------------------+---------------------- 367 136 9 | 1236 8 346 | 12347 5 1247-3 358-7 2 #157 | 359-1 #134 359-4 | 6 #14789 #13478 147 4 3568-1 #156 | 7 #1236 3569 | 39-12 #1289 #1238 12 56 36 89 38

I came up with Base 1247; r5689 c3589 giving 16 cell truths and 17 links: 14r5 27r6 147r8 12r9 56c3 36c5 89c8 38c9. All the potential eliminations are ok except for the 1 at r9c7. (something to do with being doubly covered?) I am interested to see how one might deal with this problem. Or is there a better grid to use?

Regarding puzzles in general, I would love it if someone could post a dummies-type explanation of the logic underlying how the extra cells are chosen to achieve a balance.

Thank you all, Phil

by **Leren** » Tue Jul 16, 2013 5:44 am

Hi Phil, I was carrying out some MSLS testing this afternoon so I was well placed to answer your question.

Take the following Puzzle as an example: 9876.....65....8............4..9..3...65..9.......2..1..59..7......3..49.....1..2

Code: Select all: *--------------------------------------------------------------------------------* | 9 8 7 | 6 1245 345 | 1234-5 125 345 | | 6 5 1234 | 1234-7 1247 3479 | 8 1279 347 | |*1234 #123 *1234 |*123478 578-124 5789-34 |*123456 5679-12 567-34 | |--------------------------+--------------------------+--------------------------| |*12578 4 *128 |*178 9 678 |*256 3 5678 | | 123-78 1237 6 | 5 1478 3478 | 9 278 478 | |*3578 79-3 *389 |*3478 678-4 2 |*456 5678 1 | |--------------------------+--------------------------+--------------------------| | 1234-8 1236 5 | 9 2468 468 | 7 168 368 | |*1278 67-12 *128 |*278 3 5678 |*156 4 9 | |*3478 679-3 *3489 |*478 5678-4 1 |*356 568 2 | *--------------------------------------------------------------------------------*

MSLS 1 : Base 1234; r34689 c1347 + r3c2 : 21 Links; 1234r3 12r4 34r6 12r8 34r9 ; 578c1 89c3 78c4 56c7 ;

20 Eliminations : r1c5 <> 5, r2c4 <> 7, r3c5 <> 124, r3c6 <> 34, r3c8 <> 12, r3c9<> 34, r5c1 <> 78, r6c2 <> 3, r6c5 <> 4, r7c1 <> 8, r8c2 <> 12, r9c2 <> 3, r9c5 <> 4

For this puzzle you initially have 20 cell Truths r34689 c1347 (marked as * in the PM). In this case none of the cells in this grid are given/solved so the number of Truths stays at 20.

Because your Home (or Base, or Floor) digit set is 1234 the idea is to eliminate 1234 in Rows 34689 but not in Columns 1347 and eliminate the Away (or Roof) digit set 56789 in columns 1347 but not in Rows 34689.

Unfortunately when you count up the Links in the covering rows and columns you get 21 - that's one too many for a Rank 0 logic - aaaargh !

But wait ... there might be a way out of this ... hmmm ... aaah, I've got it ! Take look at r3c2 (marked with # in the PM). This only holds Home digits 123 and the Links for Row 3 are already 1234, so if you add this cell to the grid you increase the Truth count to 21 but the Link count stays at 21. So you now have a Rank 0 logic (21 Truths/Links). One minor downside is that you can't eliminate any digits in the extra cell.

Leren

by **StrmCkr** » Tue Jul 16, 2013 8:57 am

deleted

by **David P Bird** » Tue Jul 16, 2013 11:13 am

Hi Leren.

I've only had a quick look at your 6 puzzles of which I find #3 the worst because there are several possibilities that must be tried.

There are various ways to prioritise the selection order of the home set digits that I can see that would all have very similar success rates.

As part of my regime for checking for JExocets I filter the digits in each band of boxes for those that aren't placed yet. Those combinations that warrant checking for S cells also make good sets to test and these will frequently coincide with your "5 givens in a box test".

A simpler method is to count how many times is solved or given in the full grid and prioritise those with the minimum counts (greater than 1) which gives pretty much the same effect.

I also prioritise the choice of columns and rows to try first as cover sets. For the home set columns highest priority is given to those that contain 2 knowns for the Home set and lowest to those that contain 4. For the Away set row covers, I give priority to those that have the most home set knowns and the fewest away set ones. However if you are going to iterate every possibility before trying another home digit set this wouldn't have much effect on your run time.

Regarding your response to Phil, when I entered your digit cover sets onto my spreadsheet I got an instant hit because I count any cell that has every one of its candidates covered once as a truth. I thought that was what you were doing too! Anyway, I don't see how this point is relevant to the Golden Nugget.

David

by **David P Bird** » Tue Jul 16, 2013 11:14 am

Hi Phil,

If you kept the home and cover sets intact for your row and column covers you get two more digit covers than cell covers. You have already reduced this to 1 by adjusting the Away set for c8 by taking out (6), which is the best that I can do too, so you are no dummy.

There is a different 16 cell set using (568)r1,(69)r3,(35)r4,(36)r7, + (27)c1,(14)c2,(12)c4,(47)c6.
This also has one more digit cover than cell covers but doesn’t need any adjustment.

Various ways exist of adding extra Home or Away covers to the different patterns that don't affect the overall misbalance, but I can't find a way to use these to determine if there is any subset of the potential elimination cells which must contain the single invalid elimination.

In easier puzzles it may be possible to construct an AIC to show that two of the potential elimination nodes are strongly linked. As one of these must contain be the invalid elimination, then all the other eliminations must be valid.

David

by **David P Bird** » Tue Jul 16, 2013 11:16 am

Hi StrmCkr,

We have a mix of manual solvers and programmers here. Programmers want a procedure to follow whereas manual solvers, such as me, want tell-tale indicators when a potential MSLS is worthy of investigation, and to know which of the different 'flavours' of them are most frequent.

The basic SK loop pattern is well known and fairly easy to identify, but variations of the theme (which are AALS chains) are a lot harder to pick out. For example they can also be present as partially solved (ie degenerate) patterns.

I don't have time to consider your approach in depth so perhaps I'm mistaken, but it seems to focus on very specific cases. Is that right or is it more general?

David

by **champagne** » Tue Jul 16, 2013 3:11 pm

Hi Phil,

before trying to give another view of the "add cells" logic, some preliminary remarks;

a) Golden Nugget is not a good start. You come to a rank 1 logic, nobody so far could do more.
b) leren first worked on non overlapping rank 1 logic. In that case, all potential eliminations are valid except one, but we have normally no clue to tell which one is wrong.

Back to your question, a topic on which I am also currently working.
I have no general rule to extract a rank 0 logic, but some partial strategies using a starting pattern.

The MSLS target is one of the possible strategies.
In that case I start from a matrix "n rows p columns" and from a split of digits say "A" in rows and "B" in columns.

For each sub group ("A" + n), ("B" +p) the covering strategy is very similar to a start using a row base or a column base in a multi fish study.

My underlying logic, to find an existing rank 0 logic is the following (it does not guaranty that you'll get it as I'll show below)

if in the vicinity analysis you can define a best cover, you must use it. If you miss it, then you miss the rank 0 logic.

Let me illustrate that principle on an example where we have a very simple row base example recently posted by JC VAN HAY

Code: Select all: 9..8..7...8..9..6...5..4..38..4..6...7..2..8...3..8..51...4.2...6.9...1...7...... A B C |D E F |G H I 9 1234 1246 |8 1356 12356 |7 245 124 2347 8 124 |12357 9 12357 |145 6 124 267 12 5 |1267 167 4 |8 9 3 ------------------------------------------------- 8 1259 129 |4 1357 13579 |6 237 1279 456 7 1469 |1356 2 13569 |1349 8 149 246 1249 3 |167 167 8 |149 247 5 << ------------------------------------------------- 1 359 89 |3567 4 3567 |2 357 6789 << 2345 6 248 |9 3578 2357 |345 1 478 2345 23459 7 |12356 13568 12356 |3459 345 4689 << AA AA AA

here we have here a MSLS

Code: Select all: 17 Truths = {6N124578 7N2468 9N1245678 } 17 Links = {1r69 2r69 3r79 4r69 5r79 6r6 6b8 7r67 8c5 9c27 } 5 elims 4r9c9 7r7c9 8r8c5 9r4c2 9r5c7

My solver started on a matrix 3x3 rows 6 7 9 columns 2 5 7
with digits 89 cover in column and other digits in rows.
note: we have 3 empty cells in the base matrix

Let's study the row cover.

Code: Select all: row 6 cells r6c2 r6c5 r6c7 digits 12467 (5 links) in that row, we have 3 extra cells without the digits 8,9 r6c1=246 r6c4=167 r6c8=247 these cells containing only digits of the lot 12467 can (must) be added as truths. The final balance is 5 links - 3 additional truths row 7 cell r7c2 digits 35 (2 links) in that row, we have 3 extra cells without the digits 8,9 r7c4=3567 r7c6=3567 r7c8=357 but adding these cells as truths, me must add digits 67 as links the balance is positive, we must do it row 9 cells r9c2 r9c5 r9c7 digits 123456 (6 links) in that row, we have 4 extra cells without the digits 8,9 r9c1=2345 r9c4=12356 r9c6=12356 r9c8=345 these cells containing only digits of the lot 123456 can (must) be added as truths. The final balance is 6 links - 4 additional truths

At that point, the rank is 1. It will be still necessary to optimise the band 3, replacing the links 6r7 and 6r9 by the link 6b8.

Note, it can be in the situation seen in row 7, that the balance is negative. Then we can not add cells. We can foresee a situation where the use of only part of the extra cells gives a positive (or neutral) balance;

But the vicinity optimisation is not always the right way to build an active rank 0 logic.
On the same puzzle, I'll comment the row based logic proposed by JC

Code: Select all: A B C |D E F |G H I 9 1234 1246 |8 1356 12356 |7 245 124 2347 8 124 |12357 9 12357 |145 6 124 267 12 5 |1267 167 4 |8 9 3 ------------------------------------------------- 8 1259 129 |4 1357 13579 |6 237 1279 456 7 1469 |1356 2 13569 |1349 8 149 246 1249 3 |167 167 8 |149 247 5 << ------------------------------------------------- 1 359 89 |3567 4 3567 |2 357 6789 << 2345 6 248 |9 3578 2357 |345 1 478 2345 23459 7 |12356 13568 12356 |3459 345 4689 << All Rows Loop[6] : {6R79 8R7 9R679} - {9c27 7n3 79n9 6b8} 5 Eliminations --> r9c9<>48, r4c2<>9, r5c7<>9, r7c9<>7

This is a multi fish pattern not directly produced by my solver. Digit 6 is ignored in row 6, digit 8 is ignored in row 9. My solver does not accept that.

I see one theoretical way to produce it using my lay-out:

you start of a with 2 rows 79 and the digits 69 (4 truths)
you do the cover proposed by JC (6 links)
you then look for possibility to add truths in 2 ways
. extra digit (8) in an existing row (7) covering cells used as link (r7c39)
. digit(9) in an extra row (6) having only candidates (9r6c27) belonging to links

This would be nice but my vicinity optimisation in that case would suggest
use of 9B7 instead of 9r2+7n3
use of 89b9 instead of 9c7 79n9.
At the end, my process would find a 4truths 4links logic with no elimination.

Adding flexibility in the lay-out means adding complexity, and as noticed david what is easy for a player is not always easy to code.

by **pjb** » Wed Jul 17, 2013 11:29 pm

Thank you all for the feedback. It will take a while to digest.
David, I found it interesting that your second 4x4 grid for the golden nugget (same base set 1247 but in columns) does not overlap the one I found, they had 18 and 19 potential eliminations respectively, of which 10 were common. The one incorrect one in my grid was the 1 at r9c7, and in yours the 5 at r4c7. I wonder if there is logic to prove the 10 common eliminations are valid?

Phil

by **daj95376** » Thu Jul 18, 2013 12:12 am

When I compare my Templates solver's output to Multi-Fish, my output has always matched or exceeded the Multi-Fish results. This isn't surprising since N-value Templates takes into account every (straightforward) possible way to combine the values in question.

With respect to Golden Nugget and the selection of Base Set = 1247, my Templates solver found one elimination.

Code: Select all: +--------------------------------------------------------------------------------+ | 25678 14568 124567 | 268 2467 4678 | 1247 3 9 | | 26789 4689 2467 | 23689 23467 1 | 247 2467 5 | | 2679 1469 3 | 269 5 4679 | 8 12467 1247 | |--------------------------+--------------------------+--------------------------| | 235 345 8 | 135 9 357 | 123457 1247 6 | | 3569 7 456 | 13568 136 2 | 13459 1489 1348 | | 1 3569 256 | 4 367 35678 | 23579 2789 2378 | |--------------------------+--------------------------+--------------------------| | 367 136 9 | 1236 8 346 | 12347 5 12347 | | 3578 2 157 | 1359 134 3459 | 6 14789 13478 | | 4 13568 156 | 7 1236 3569 | 1239 1289 1238 | +--------------------------------------------------------------------------------+ # 182 eliminations remain Templates: 47 37 108 38 32 96 52 12 16 *** 2-template completed *** 3-template completed <1247> accepted = 80 template combinations <1247> <>3 r7c9 <1247> r12c7,r4c8,r37c9 locked for candidates

I find it interesting that other eliminations were found by MSLS. I suspect that it's because additional values are folded into the mix.

by **champagne** » Thu Jul 18, 2013 5:46 am

daj95376 wrote:I find it interesting that other eliminations were found by MSLS. I suspect that it's because additional values are folded into the mix.

This is a wrong reading of the posts. A rank 1 logic, unhappily, does not bring direct effect. You get for each rank 1 logic a set of candidates all false except one, but you don't know which one is true. We have the same information in each unknown cell.

by **David P Bird** » Thu Jul 18, 2013 9:58 am

Phil, the combined potential elimination sets will either contain one or two invalid eliminations depending on whether there are different ones in the unique subsets or a single one in the common subset. In the past I've tried but failed to find an acceptable way to find out which one of these it is (but perhaps I gave up too quickly.)

BTW for some people "base" sets are always strong and "cover" sets are always weak with "fins" always being in the cover sets. Consequently I've had my knuckles rapped for my cavalier use of these terms. To keep out of trouble I'm therefore using the concept of Home and Away sets. If a Naked Locked Set is found, together these sets will form a cover set, and if a Hidden one is found they will form a base set.

David

by **Leren** » Thu Jul 18, 2013 12:10 pm

Hi all,

Champagne and I have been corresponding on the following three puzzles that we can find Multifish for, but no MSLS equivalents.

98.7..6..5.7....4..3.......2...9.1....86...3......5..2.4.8...7.....1...9.....65..;4;4;10.2;10.2;9.2;fl; 1259;tr; 16;
98.7..6......6.........5.4.8..3..7...2...1.6...3......7...1..5..9..4...6..82..9..;4;4;10.2;10.2;9.2;fl; 1456;tr; 15;
98.7..6......6.........5.4.8..3..2...2...1..6..3......7...1...5.3..4..6...82..9..;4;4;10.2;10.2;9.2;fl; 1456;tr; 15;

Perhaps others can succeed where we have failed. Good luck and good hunting.

Leren

by **JC Van Hay** » Thu Jul 18, 2013 1:50 pm

Is it what you are looking for ?

Hidden Text: Show

98.7..6..5.7....4..3.......2...9.1....86...3......5..2.4.8...7.....1...9.....65..;4;4;10.2;10.2;9.2;fl; 1259;tr; 16;

Code: Select all: +------------------------+-----------------------+-----------------------+ | 9 8 124 | 7 2345 1234 | 6 125 135 | | 5 126 7 | 129-3 2368 12389 | 2389 4 138 | | 46-1 3 1246 | 1259-4 24568 12489 | 2789 1259-8 1578 | +------------------------+-----------------------+-----------------------+ | 2 567 3456 | (34) 9 3478 | 1 (568) 4678-5 | | (147) 159-7 8 | 6 (247) (1247) | (479) 3 (457) | | 3467-1 1679 13469 | (134) 3478 5 | 478-9 (689) 2 | +------------------------+-----------------------+-----------------------+ | (136) 4 1259-36 | 8 (235) (239) | (23) 7 (136) | | 3678 2567 2356 | (2345) 1 347-2 | 348-2 (268) 9 | | 378-1 1279 1239 | (2349) 347-2 6 | 5 (128) 348-1 | +------------------------+-----------------------+-----------------------+

All Cells Loop[18] : {4689N48 57N15679} - {47r5 36r7 1c1 34c4 68c8 1b59 2b589 5b68 9b68}
15 Eliminations --> r369c1<>1, r8c67<>2, r7c3<>36, r2c4<>3, r3c4<>4, r3c8<>8, r4c9<>5, r5c2<>7, r6c7<>9, r9c9<>1, r9c5<>2

98.7..6......6.........5.4.8..3..7...2...1.6...3......7...1..5..9..4...6..82..9..;4;4;10.2;10.2;9.2;fl; 1456;tr; 15;

Code: Select all: +-----------------------+-----------------------+----------------------------+ | 9 8 145-2 | 7 (23) (234) | 6 (123) (1235) | | 12345 13457 12457 | (1489) 6 2389-4 | (12358) 23789-1 23789-15 | | 1236 1367 1267 | (189) 2389 5 | (1238) 4 23789-1 | +-----------------------+-----------------------+----------------------------+ | 8 1456 14569 | 3 259 2469 | 7 129 12459 | | (45) 2 79-45 | (4589) 789-5 1 | (3458) 6 389-45 | | 1456 14567 3 | 456-89 25789 246789 | 145-28 1289 124589 | +-----------------------+-----------------------+----------------------------+ | 7 346 246 | (689) 1 389-6 | (2348) 5 238-4 | | 1235 9 125 | (58) 4 378 | (1238) 2378-1 6 | | 1456-3 1456-3 8 | 2 (357) (367) | 9 (137) (1347) | +-----------------------+-----------------------+----------------------------+

All Cells loop[19] : {5N1 23578N47 19N5689} - {2r1 3r19 4r5 5r5 7r9 89c4 238c7 1b239 4b29 5b38 6b8}
20 Eliminations --> r5c359<>5, r2c89<>1, r5c39<>4, r6c47<>8, r9c12<>3, r1c3<>2, r2c6<>4, r2c9<>5, r3c9<>1, r6c7<>2, r6c4<>9, r7c9<>4, r7c6<>6, r8c8<>1

98.7..6......6.........5.4.8..3..2...2...1..6..3......7...1...5.3..4..6...82..9..;4;4;10.2;10.2;9.2;fl; 1456;tr; 15;

Code: Select all: +-----------------------+-----------------------+----------------------------+ | 9 8 145-2 | 7 (23) (234) | 6 (1235) (123) | | 12345 1457 12457 | (1489) 6 2389-4 | (13578) 23789-15 23789-1 | | 1236 167 1267 | (189) 2389 5 | (1378) 4 23789-1 | +-----------------------+-----------------------+----------------------------+ | 8 145679 145679 | 3 579 4679 | 2 1579 1479 | | (45) 2 79-45 | (4589) 789-5 1 | (34578) 3789-5 6 | | 1456 145679 3 | 456-89 25789 246789 | 145-78 15789 14789 | +-----------------------+-----------------------+----------------------------+ | 7 469 2469 | (689) 1 389-6 | (348) 238 5 | | 125 3 1259 | (589) 4 789 | (178) 6 278-1 | | 1456 1456 8 | 2 (357) (367) | 9 (137) (1347) | +-----------------------+-----------------------+----------------------------+

All Cells Loop[19] : {5N1 23578N47 19N5689} - {2r1 3r19 4r5 5r5 7r9 89c4 378c7 1b239 4b29 5b38 6b8}
16 Eliminations --> r5c358<>5, r238c9<>1, r6c47<>8, r2c8<>15, r1c3<>2, r2c6<>4, r5c3<>4, r6c7<>7, r6c4<>9, r7c6<>6

by **blue** » Thu Jul 18, 2013 2:44 pm

Or more like these:

Hidden Text: Show

Regards,
Blue.

by **David P Bird** » Thu Jul 18, 2013 4:20 pm

Hi Blue,

Just as I found the first of these, JCVH posted his full set of solutions, so I watched the Tour de France instead! My solution was identical to JC's and was an adaptation of the 4 box cover pattern used for SK loops.

Now I notice that each of his and your solutions includes a box cover set. This might be why Champagne & Leren couldn't identify them. The question therefore is – is it possible to get these results using only row and column cover sets?

Regards

David

The New Sudoku Players' Forum

Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets

Re: Using Multi-Sector Locked Sets