paquita's SE 11.8 puzzle

Post puzzles for others to solve here.

Re: paquita's SE 11.8 puzzle

Postby yzfwsf » Sun Apr 26, 2020 8:45 am

champagne wrote:Hi yzfwsf,
In David's manual approach to select the most promising n*p, you have the filter (one group of digits in rows, the rest in clumns)
I have another filter, cells with 5 digits have small chances to produce a MSLS (I have counter examples)
And for sure the best chance is when all crossing are filled (more truths)

At the end, this reduces drastically the number of np to check

Here
Code: Select all
9    8     124   |7    12345 3456  |1235  1456   136   x
7    6     124   |1235 8     3459  |12359 1459   139   x
1234 1234  5     |126  124   469   |1289  146789 16789
------------------------------------------------------
8    1257  1267  |9    2357  3567  |4     167    1367  x
1456 14579 3     |568  457   45678 |189   2      16789
246  2479  24679 |2368 2347  1     |389   6789   5     
------------------------------------------------------
1235 12359 1289  |4    6     358   |7     1589   189   x
1345 13457 1478  |1358 9     3578  |6     158    2     
156  1579  16789 |158  157   2     |1589  3      4     
           x                 x            x      x


truths{ R1C3689 R2C3689 R4C3689 R7C3689}
links{ 1C3 1C8 1C9 2C3 3C6 3C9 4R1 4R2 5C6 5C8 6R1 6R4 7R4 8R7 9R2 9R7 }

The MSLS fills david's constraints and we have no cell with more than 4 digits

If you flag as X cells with 2-4 digits you have the matrix

Code: Select all
..X..XXXX
..XX.X.XX
XX.XXXX..

.XX.XX.XX
X..XX.X..
XX.XX.XX.

X.X..X.XX
X.XX.X.X.
XX.XX.X..


and not so many 4x4 possibilities to check

Hi champagne:
Here is a counter sample for you
Code: Select all
9876.....5.....8.........6.4...6...3.7.5..6.......2.1..9.7..5......3...2.....1.4.

MSLS.PNG
MSLS.PNG (56.59 KiB) Viewed 778 times
yzfwsf
 
Posts: 905
Joined: 16 April 2019

Re: paquita's SE 11.8 puzzle

Postby champagne » Sun Apr 26, 2020 9:09 am

Hi again yzfwsf,

This is one counter example simpler that the one I had in hands.
This puzzle has a JExocet and likely an "Almost SK loop".
I got the following

Code: Select all
9     8     7      |6      1245    345    |1234   235   145   
5     12346 12346  |12349  12479   3479   |8      2379  1479 
123   1234  1234   |123489 1245789 345789 |123479 6     14579
-------------------------------------------------------------
4     125   12589  |189    6       789    |279    25789 3     
1238  7     12389  |5      1489    3489   |6      289   489   
368   356   35689  |3489   4789    2      |479    1     45789
-------------------------------------------------------------
12368 9     123468 |7      248     468    |5      38    168   
1678  1456  14568  |489    3       45689  |179    789   2     
23678 2356  23568  |289    2589    1      |379    4     6789 


1;4;3124,r3c1 r3c3 r1c7 r2c4 exocet

truths={ 1234R1 1234R2 1234R5 1234R7 r3c1 r3c2 r3c3 }
links={ 1234B1 r5c1 r5c3 r7c1 r7c3 r2c4 124C5 34C6 r1c7 23C8 14C9 }

truths={ 1234R5 1234R7 1234C4 1234C7 r3c1 r3c2 r3c3 }
links={ 134B5 24B6 24B8 13B9 1234R3 r1c7 r2c4 r5c1 r5c3 r7c1 r7c3 }

but not the MSLS due to the limit set in the search.

EDIT I'll put the 5 digit filter as an option in the search of MSLS
EDIT2 when a MSLS has the preferred David's structure, I usually have a multi floors equivalence
champagne
2017 Supporter
 
Posts: 7456
Joined: 02 August 2007
Location: France Brittany

Re: paquita's SE 11.8 puzzle

Postby Ajò Dimonios » Sun Apr 26, 2020 1:34 pm

Hi Champagne

In the numerous examples of sk loops and MSLS reported by Philip on his website http://www.philsfolly.net.au/ I noticed that the logic of all the sk-loops with all the variations included excluding the "almost sk- loops with rank = 1 = 2 = 3 "are always msls, that is, the same logic of the loop can be interpreted as rank = 0 by crossing lines, columns and boxes. This is the reason, as I explained in my post, sk-and-related-loops-t35883-45.html of the regularity observed by Philip on the eliminations and the inclusion in the "almost sk-loop with rank = 1" which are nothing but almost-msls with rank = 1. Probably this regularity observed also in the "almost sk-loop with rank = 2 and 3" hides almost-msls with higher rank.

Paolo
Ajò Dimonios
 
Posts: 213
Joined: 07 November 2019

Re: paquita's SE 11.8 puzzle

Postby champagne » Sun Apr 26, 2020 3:58 pm

Ajò Dimonios wrote:Hi Champagne

In the numerous examples of sk loops and MSLS reported by Philip on his website http://www.philsfolly.net.au/ I noticed that the logic of all the sk-loops with all the variations included excluding the "almost sk- loops with rank = 1 = 2 = 3 "are always msls, that is, the same logic of the loop can be interpreted as rank = 0 by crossing lines, columns and boxes. This is the reason, as I explained in my post, sk-and-related-loops-t35883-45.html of the regularity observed by Philip on the eliminations and the inclusion in the "almost sk-loop with rank = 1" which are nothing but almost-msls with rank = 1. Probably this regularity observed also in the "almost sk-loop with rank = 2 and 3" hides almost-msls with higher rank.

Paolo

Hi Paolo,
what you write is correct, but I don't see clearly what is your point.
Some free thought here:

If a puzzle is very hard using the classical set of rules, you likely have a big truths/links structure, hard to break with such rules.
The most common known exotic pattern is the exocet, it is not a rank 0 logic and it has triple points in truths, but we often see some TLG0 and then, we usually have several of them leading to the same eliminations.

I am very cautious with logic of rank >0 in big TLGs. You don't know "a priori" where are the "false" candidates.
On noticeable exception in an unexplored field AFAIK, the TLG-1 plus uncovered candidates in truths.
Then, any candidate seeing all uncovered truths can be cleared. (see my new thread for more details)

And yes, when we have something close to a SK loop (I have no clear definition of an "almost SK loop") we usually have variants of the family of TLG0 that we have with a SK loop.
champagne
2017 Supporter
 
Posts: 7456
Joined: 02 August 2007
Location: France Brittany

Re: paquita's SE 11.8 puzzle

Postby eleven » Sun Apr 26, 2020 6:49 pm

denis_berthier wrote:
eleven wrote:seeing normal sudoku as an exact cover problem was not very fruitful, after it had turned out, that direct backtracking was faster than the dancing links algorithm.

Speed of an algorithm is one thing. Readability of the solution is another. Most of the time they are contradictory. Nobody in Sudoku solving accepts backtracking as a readable solution.

Well, the dancing link algorithm is less readable than backtracking.
This combinatorial explosion problem is what motivated my original question. How was the 16 base cells pattern found? As of now, I can't see any answer in this thread.

Finding the MSLS for the original puzzle manually is really straightforward here, and done in 10 min.
For other puzzles you may have to check more possibilities.

As i said, you have to look at the solved cells.
You will find 3 rectangles with 6789. So if you cannot split the digits with 6789 in one group, you definitely can forget it - there will not be a row/column MSLS.
And you have a rectangle 1245, one with 479 and 235 as well as 23 in 3 corners of 2 rectangles.
So you would try with 6789 on one side and 1235 on the other and look, how far you can come.

Always keep in mind, that for a 4x4 MSLS you have only 16 digits to cover all 4 rows and 4 columns.
A rectangle with 3 or 4 digits guarantees that you will not need 2 group digits for these 2 rows and 2 columns.
If you do not have 2 of 4 group givens in 3 rows/columns you already need 9 to cover them with this group, only 7 remaining for all the rest.

List the number of digits of each group, which you need to cover the rows/columns.
Code: Select all
                                 1235  6789
        +-------+-------+-------+     
        | 9 8 . | 7 . . | . . . |  4    1   
        | 7 6 . | . 8 . | . . . |  4    1   
        | . . 5 | . . . | . . . |  3    4   
        +-------+-------+-------+   
        | 8 . . | 9 . . | 4 . . |  4    2   
        | . . 3 | . . . | . 2 . |  2    3   
        | . . . | . . 1 | . . 5 |  2    3   
        +-------+-------+-------+   
        | . . . | 4 6 . | 7 . . |  4    2   
        | . . . | . 9 . | 6 . 2 |  3    2   
        | . . . | . . 2 | . 3 4 |  2    4   
        +-------+-------+-------+
 6789     1 2 4  2  1 4   2 4 4   
 1235     4 4 2  4  4 2   4 2 2


Minimum counts for 4 rows and 4 columns for the 2 cases:
1235 in rows: min in r35689 2+2+2+3, c12457 1+1+2+2: 9+6 = 15, but you need 3 4's to cover 4 of the rows and 2 4's for columns c1457.
6789 in rows: min in r12478 1+1+2+2, c3689 2+2+2+2: 6+8 = 14, here r47 already have a 4, so adding 4 in r12 covers all.
=> MSLS in r1247 with 46789 and c3689 with 1235.

Of course you can also program this counting, also for different matrix sizes. Since most possibilities very soon extend the number of digits needed, you should have a result in milliseconds. (If already candidates have been eliminated from the candidates grid, the counts may get lower and have to be adopted)

[Added:] Tried yzfwsf's puzzle above with first split 124 vs 56789 from the rectangles -> 14 digits + 2 for the 3 (less than 10 min)

[Edit:]Looking at it again after SpAces post, i had wrong counts in row 3 (2 3 instead of 3 4)
Last edited by eleven on Sun May 03, 2020 9:39 am, edited 1 time in total.
eleven
 
Posts: 3152
Joined: 10 February 2008

Re: paquita's SE 11.8 puzzle

Postby denis_berthier » Mon Apr 27, 2020 3:19 am

eleven wrote:
denis_berthier wrote:
eleven wrote:seeing normal sudoku as an exact cover problem was not very fruitful, after it had turned out, that direct backtracking was faster than the dancing links algorithm.

Speed of an algorithm is one thing. Readability of the solution is another. Most of the time they are contradictory. Nobody in Sudoku solving accepts backtracking as a readable solution.

Well, the dancing link algorithm is less readable than backtracking.

I'm not speaking of reading the algorithm code, but of reading the resolution paths.
A backtracking algorithm doesn't produce a readable resolution path.
BTW, backtracking is a very general term. DFS would be more appropriate here.

eleven wrote:
This combinatorial explosion problem is what motivated my original question. How was the 16 base cells pattern found? As of now, I can't see any answer in this thread.

Finding the MSLS for the original puzzle manually is really straightforward here, and done in 10 min.
For other puzzles you may have to check more possibilities [...]
[Added:] Tried yzfwsf's puzzle above with first split 124 vs 56789 from the rectangles -> 14 digits + 2 for the 3 (less than 10 min)

OK, I agree that in such cases and with some training, it can be done manually relatively fast and I've also seen how fast it is on yzfwsf's website.
However, a fast program must have some tricks to avoid looking for all the possible combinations. And formalising these so that they cover all the possible cases may not be so easy.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: paquita's SE 11.8 puzzle

Postby StrmCkr » Mon Apr 27, 2020 8:12 am

And formalizing these so that they cover all the possible cases may not be so easy.
modified obis's Fish algorithm for n digits is adequate enough with very little modification a reduction for the N set size combination search based on the digit units not given for the sectors = set for the away set. {AND VICE VERSA looking at home away non givens = home set } as they always balance 4 away - 5 home etc

ie 84 home combinations at max and 1 away set.

which is all i did for my first version of the msls finder

its pretty quick for size 4 as the smaller sets are covered by als-xz, als-xy
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1430
Joined: 05 September 2006

Re: paquita's SE 11.8 puzzle

Postby SpAce » Sun May 03, 2020 7:17 am

Hi guys,

Sorry for being late to the party as I haven't been checking the forum lately. I've been enjoying my vacation from sudoku and plan to continue :) However, now that I did check in, I noticed that eleven mentioned my brief tutorial about finding MSLS manually. I'd already forgotten all about MSLS because I'd never used them before nor after, so I thought it would be fun to have a fresh test of my own manual algorithm (obviously derived from David's).

Indeed it seems to work as promised, as I did find an MSLS in this puzzle very easily without looking at anyone else's solutions. Of course it helped to know that there was an MSLS to be found, but I think it makes no difference because you'd probably try to find one anyway for a puzzle of this difficulty.

However, my straight-forward application of the tutorial yielded a slightly different MSLS (20x20 vs 16x16) and partly different (immediate) eliminations from what's been presented here and what Phil's solver gives. I think mine is probably correct too, but I'd be happier if someone double-checked my results, as I'm pretty out of touch at the moment.

Here's the coloring I used to locate the MSLS and the eliminations. The color-coding is explained in the tutorial (except for the eliminations).

mslspic.png
mslspic.png (90.28 KiB) Viewed 703 times

The black candidates are common eliminations with Phil's. The differences are on row 8: the dark red ones are mine, while the light red ones are Phil's.

Below are the two complementary 20x20 MSNS-variants (actually, the other is 19x19) that can be read from that image. One with the "Home" assigned to the rows and the other to the columns. The results are the same, as expected.

Code: Select all
  \46    \479              \68    \47               \89
.------------------------.------------------------.-------------------------.
|  9      8       124    |  7      1235-4  3456   |  1235    1456    136    |
|  7      6       124    |  1235   8       3459   |  1235-9  1459    139    |
| *1234  *1234    5      | *126   *124     469    | *1289    46789-1 6789-1 | \123
:------------------------+------------------------+-------------------------:
|  8      125-7   1267   |  9      235-7   3567   |  4       167     1367   |
| *1456  *14579   3      | *568   *457     4678-5 | *189     2       6789-1 | \15
| *246   *2479    4679-2 | *2368  *2347    1      | *389     6789    5      | \23
:------------------------+------------------------+-------------------------:
|  1235   1235-9  1289   |  4      6       358    |  7       1589    189    |
|  135-4  135-47  1478   |  135-8  9       3578   |  6       158     2      |
| *156   *1579    6789-1 | *158   *157     2      | *1589    3       4      | \15
'------------------------'------------------------'-------------------------'

MSNS 4x5: Home (1235)r3569, Away (46789)c12457

20x20 (Rank 0): {3569N12457 \ 123r3 15r5 23r6 15r9 46c1 479c2 68c4 47c5 89c7}

=> -1 r3c89,r5c9,r9c3; -2 r6c3; -4 r1c5,r8c12; -7 r4c25,r8c2; -8 r8c4; -9 r2c7,r7c2 (15 elims)

And the other:

Code: Select all
                 \12                      \35               \15       \13
.------------------------.------------------------.---------------------------.
| 9      8       *124    | 7      1235-4  *3456   | 1235    *1456     *136    | \46
| 7      6       *124    | 1235   8       *3459   | 1235-9  *1459     *139    | \49
| 1234   1234     5      | 126    124      469    | 1289     46789-1   6789-1 |
:------------------------+------------------------+---------------------------:
| 8      125-7   *1267   | 9      235-7   *3567   | 4       *167      *1367   | \67
| 1456   14579    3      | 568    457      4678-5 | 189      2         6789-1 |
| 246    2479     4679-2 | 2368   2347     1      | 389      6789      5      |
:------------------------+------------------------+---------------------------:
| 1235   1235-9  *1289   | 4      6       *358    | 7       *1589     *189    | \89
| 135-4  135-47  *1478   | 135-8  9       *3578   | 6       *158      !2      | \478
| 156    1579     6789-1 | 158    157      2      | 1589     3         4      |
'------------------------'------------------------'---------------------------'

MSNS 4x5: Home (1235)c3689, Away (46789)r12478

19x19 {1247N3689 8N368 \ 46r1 49r2 67r4 89r7 478r8 12c3 35c6 15c8 13c9}

=> the same eliminations

Of those 15 eliminations 11 are common with Phil's 16x16 MSLS. The differences are on row 8 which is part of my MSLS but not Phil's:

only mine: -4 r8c12, -7 r8c2, -8 r8c4 (4 elims)
only Phil's: -1 r8c38, -3 r8c6, -5 r8c68 (5 elims)

(Phil's MSLS: 16x16 (Rank 0): {1247N3689 \ 46r1 49r2 67r4 89r7 12c3 35c6 15c8 13c9} )

Both sets of eliminations lead to the same end result after basics are applied. I guess Phil's smaller 16x16 with one more elimination could be considered more efficient, though?

Does everyone agree with my results? They're worked out after several months of avoiding sudoku, so I wouldn't be surprised if I got something wrong.

Bottom line: basic rectangular MSLSs that don't require extra balancing acts etc are very easy to find and apply manually. Just check if the givens and solved cells form two groups of digits that can be covered with mostly non-intersecting rectangles, and you probably have one. The rest is normal base\cover logic.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: paquita's SE 11.8 puzzle

Postby eleven » Sun May 03, 2020 11:40 am

Hello and goodbye, SpAce !

When you look at my post above (i corrected the row 3 counts), you can easily find the 4x5 MSLS's after adding the counts for digit 4.
eleven
 
Posts: 3152
Joined: 10 February 2008

Re: paquita's SE 11.8 puzzle

Postby tarek » Sun May 03, 2020 2:42 pm

SpAce You should change you name to CoMet if you make these short visits after a long absence! Nice to hear from you though!
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Re: paquita's SE 11.8 puzzle

Postby Cenoman » Sun May 03, 2020 9:07 pm

Hi SpAce,
You forced me to get out my confinement ! Happy to hear you breaking your vow of silence...
I am in line with your post. As I was not aware of your tutorial, I have made my own manual processing of the two puzzles dealt with in this thread.

In my first post I wrote: P&P first step: Clearly, it meant that I had found the MSLS manually.
Reading multiple comments about the difficulty to find MSLS manually, I added an Edit line on April 24. It seems that nobody trusted me.
Of course I could have cheated using Phil's or yzfwsf's solvers.
My method is very close to David's document. For the Paquita's SE11.8 puzzle, here is how it can be treated:

Searching for lines (rows or columns) with two givens each, one can spot easily columns 4, 6, 8.
The set of givens in these columns is {1, 2, 3, 5}: a good candidate for a MSLS base (Home set in David's vocabulary} A fourth column containing two of these base digits would help. Column 9 does, let's forget 4r9c9 for the moment. The four columns c4689 provide 2 links each (the base candidates not placed within)
Now searching for cross-lines with no base digit as a given, one can easily spot rows 1, 2, 4, 7.
What is left to be done is to count the not solved cells at the crossings of these rows with columns c4689, here 16 cells (yielding thus 16 truths); and to count the links provided in rows r1247 by digits complementary to the base set, here these four rows provide 2 links each (the non-base candidates not placed within)
And... what a chance, the truth count equals the link count.
Hidden Text: Show
Code: Select all
 +-------------------------+-------------------------+---------------------------+
 |  9      8      <124     |  7      1235-4 <3456    |  1235   <1456    <136     |46
 |  7      6      <124     |  1235   8      <3459    |  1235-9 <1459    <139     |49
 |  1234   1234    5       |  126    124     469     |  1289    46789-1  6789-1  |
 +-------------------------+-------------------------+---------------------------+
 |  8      125-7  <1267    |  9      235-7  <3567    |  4      <167     <1367    |67
 |  1456   14579   3       |  568    457     4678-5  |  189     2        6789-1  |
 |  246    2479    4679-2  |  2368   2347    1       |  389     6789     5       |
 +-------------------------+-------------------------+---------------------------+
 |  1235   1235-9 <1289    |  4      6      <358     |  7      <1589    <189     |89
 |  1345   13457   478-1   |  1358   9       78-35   |  6       8-15     2       |
 |  156    1579    6789-1  |  158    157     2       |  1589    3        4       |
 +-------------------------+-------------------------+---------------------------+
                   12                        35                 15       13

16 cells, 16 links, 16 elim.

Not more than 10 minutes, just the time needed to count the givens in rows and columns, to issue a PM table and to count the links in selected lines.

Now, yzfwsf posted "for fun" an output picture of his solver, showing three MSLS's for this puzzle.
In fact there are four !
I have a personal conjecture. When you have found a MSLS, there exists a second one, that I would call a dual one, having the same base digits, but using the unused lines of the first one with inverted roles: in the above puzzle,
- columns 1, 2, 4, 5, 7 as Home set houses (i.e. as houses for links with digits 1, 2, 3, 5)
- rows 3, 5, 6, 7, 9 as Away set houses (i.e. as houses for links with digits 4, 6, 7, 8, 9)
give a 5x5 MSLS with 23 cells "only" because of given (or solved) cells r8c57.
The link count and the eliminations are shown in the following PM's
Hidden Text: Show
Code: Select all
 +-------------------------+-------------------------+---------------------------+
 |  9      8       124     |  7      1235-4  3456    |  1235    1456     136     |
 |  7      6       124     |  1235   8       3459    |  1235-9  1459     139     |
 | <1234  <1234    5       | <126   <124     469     | <1289    46789-1  6789-1  |123
 +-------------------------+-------------------------+---------------------------+
 |  8      125-7   1267    |  9      235-7   3567    |  4       167      1367    |
 | <1456  <14579   3       | <568   <457     4678-5  | <189     2        6789-1  |15
 | <246   <2479    4679-2  | <2368  <2347    1       | <389     6789     5       |23
 +-------------------------+-------------------------+---------------------------+
 |  1235   1235-9  1289    |  4      6       358     |  7       1589     189     |
 | <1345  <13457   478-1   | <1358   9       78-35   |  6       8-15     2       |135
 | <156   <1579    6789-1  | <158   <157     2       | <1589    3        4       |15
 +-------------------------+-------------------------+---------------------------+
    46     479                68     47                 89


23 cells, r35689 c12457 (25 intersections minus r8c57)
23 links: 123r3, 15r5, 23r6, 135r8, 15r9, 46c1, 479c2, 68c4, 47c5, 89c7
16 eliminations (before running basics) Same eliminations as the 16-cell MSLS


Now, with a careful search, it can be seen easily that row 8 can be added to the 16 cell-MSLS
Row 8 adds three cells: r8c368, and three links: 478r8. So the truth-link balance is unchanged.
Hidden Text: Show
Code: Select all
 +-------------------------+-------------------------+---------------------------+
 |  9      8      <124     |  7      1235-4 <3456    |  1235   <1456    <136     |46
 |  7      6      <124     |  1235   8      <3459    |  1235-9 <1459    <139     |49
 |  1234   1234    5       |  126    124     469     |  1289    46789-1  6789-1  |
 +-------------------------+-------------------------+---------------------------+
 |  8      125-7  <1267    |  9      235-7  <3567    |  4      <167     <1367    |67
 |  1456   14579   3       |  568    457     4678-5  |  189     2        6789-1  |
 |  246    2479    4679-2  |  2368   2347    1       |  389     6789     5       |
 +-------------------------+-------------------------+---------------------------+
 |  1235   1235-9 <1289    |  4      6      <358     |  7      <1589    <189     |89
 |  135-4  135-47 <1478    |  135-8  9      <3578    |  6      <158      2       |478
 |  156    1579    6789-1  |  158    157     2       |  1589    3        4       |
 +-------------------------+-------------------------+---------------------------+
                   12                        35                 15       13

19 cells, 19 links, 15 eliminations

Same transformation as above for its dual MSLS:
Hidden Text: Show
Code: Select all
 +-------------------------+-------------------------+---------------------------+
 |  9      8       124     |  7      1235-4  3456    |  1235    1456     136     |
 |  7      6       124     |  1235   8       3459    |  1235-9  1459     139     |
 | <1234  <1234    5       | <126   <124     469     | <1289    46789-1  6789-1  |123
 +-------------------------+-------------------------+---------------------------+
 |  8      125-7   1267    |  9      235-7   3567    |  4       167      1367    |
 | <1456  <14579   3       | <568   <457     4678-5  | <189     2        6789-1  |15
 | <246   <2479    4679-2  | <2368  <2347    1       | <389     6789     5       |23
 +-------------------------+-------------------------+---------------------------+
 |  1235   1235-9  1289    |  4      6       358     |  7       1589     189     |
 |  135-4  135-47  1478    |  135-8  9       3578    |  6       158      2       |
 | <156   <1579    6789-1  | <158   <157     2       | <1589    3        4       |15
 +-------------------------+-------------------------+---------------------------+
    46     479                68     47                 89

20 cells, 20 links, 15 eliminations (same as its dual 19 cells)


For the example posted by yzfwsf, in the same way I started to count the givens in columns. Found columns 5, 6, 9 with two givens in the set {1, 2, 3, 6}, column 8 could then be the complement. Rows 1, 2, 5, 7 seem to be the expected cross lines. But the truth-link balance is far from being reached. So, one has to try the other base set {1, 2, 3, 4} also possible in these columns. The process lead to the 16 cells MSLS discussed above.
Hidden Text: Show
Code: Select all
 +---------------------------+------------------------------+---------------------------+
 |  9       8       7        |  6       <1245     <345      |  1234    <235    <145     |5
 |  5       12346   12346    |  1234-9  <12479    <3479     |  8       <2379   <1479    |79
 |  123     1234    1234     |  123489   5789-124  5789-34  |  123479   6       579-14  |
 +---------------------------+------------------------------+---------------------------+
 |  4       125     12589    |  189      6         789      |  279      5789-2  3       |
 |  123-8   7       123-89   |  5       <1489     <3489     |  6       <289    <489     |89
 |  368     356     35689    |  3489     789-4     2        |  479      1       5789-4  |
 +---------------------------+------------------------------+---------------------------+
 |  123-68  9       1234-68  |  7       <248      <468      |  5       <38     <168     |68
 |  1678    1456    14568    |  489      3         5689-4   |  179      789     2       |
 |  23678   2356    23568    |  289      589-2     1        |  379      4       6789    |
 +---------------------------+------------------------------+---------------------------+
                                         124       34                   23      14

16 cells, 16 links, 19 eliminations


Now if one tries to find a MSLS from the count of givens in rows, rows 689 are selected with two givens each in the set {1, 2, 3, 4}. Row 4 is the obvious complement. Columns 1247 with quite no base digit are selected first. Unfortunately, no balanced MSLS: 15 cells, 17 links. The only row that could be added is row 3: adds 4 cells but also 4 links (digits 1, 2, 3, 4) It is necessary to add also a column: will add five cells and hopefully less links. Column 3 does, but adds 4 links.
The balance is now 24 cells vs 25 links.
This is the point immediately encountered when searching the dual MSLS of the 16-cell MSLS. To get a balanced count of links, it can be noticed that in stack 1, there are 3 links of digit 6: 6c1, 6c2, 6c3 while the 6s in MSLS c123-cells are all in boxes 4 & 7.
Hidden Text: Show
Code: Select all
 +---------------------------+------------------------------+---------------------------+
 |  9       8       7        |  6        1245      345      |  1234     235     145     |
 |  5       12346   12346    |  12349    12479     3479     |  8        2379    1479    |
 | <123    <1234   <1234     | <123489   1245789   345789   | <123479   6       14579   |1234
 +---------------------------+------------------------------+---------------------------+
 |  4      <125    <12589    | <189      6         789      | <279      25789   3       |12
 |  1238    7       12389    |  5        1489      3489     |  6        289     489     |
 | <368    <356    <35689    | <3489     4789      2        | <479      1       45789   |34
 +---------------------------+------------------------------+---------------------------+
 |  12368   9       123468   |  7        248       468      |  5        38      168     |
 | <1678   <1456   <14568    | <489      3         45689    | <179      789     2       |14
 | <23678  <2356   <23568    | <289      2589      1        | <379      4       6789    |23
 +---------------------------+------------------------------+---------------------------+
    678     56      5689        89                             79

Un balanced: 24 truths, 25 links


So, eventually here is the dual MSLS:
Hidden Text: Show
Code: Select all
 +---------------------------+------------------------------+---------------------------+
 |  9       8       7        |  6        1245      345      |  1234     235     145     |
 |  5       12346   12346    |  1234-9   12479     3479     |  8        2379    1479    |
 | <123    <1234   <1234     | <123489   5789-124  5789-34  | <123479   6       579-14  |1234
 +---------------------------+------------------------------+---------------------------+
 |  4      <125    <12589    | <189      6         789      | <279      5789-2  3       |12
 |  123-8   7       123-89   |  5        1489      3489     |  6        289     489     |
 | <368    <356    <35689    | <3489     79-4      2        | <479      1       5789-4  |34
 +---------------------------+------------------------------+---------------------------+
 |  123-68  9       1234-68  |  7        248       468      |  5        38      168     |
 | <1678   <1456   <14568    | <489      3         5689-4   | <179      789     2       |14
 | <23678  <2356   <23568    | <289      589-2     1        | <379      4       6789    |23
 +---------------------------+------------------------------+---------------------------+
    78      5       589         89                             79
       6b4     6b7

24 cells, 24 links: 1r3, 2r3, 3r3, 4r3, 1r4, 2r4, 3r6, 4r6, 1r8, 4r8, 2r9, 3r9, 6b4, 6b7, 7c1, 8c1, 5c2, 5c3, 8c3, 9c3, 8c4, 9c4, 7c7, 9c7
19 eliminations (same as dual 16-cell MSLS)
Last edited by Cenoman on Tue Sep 15, 2020 2:38 pm, edited 1 time in total.
Cenoman
Cenoman
 
Posts: 2975
Joined: 21 November 2016
Location: France

Re: paquita's SE 11.8 puzzle

Postby StrmCkr » Sun May 03, 2020 9:50 pm

a bit late for me to chime in with mathematical proof that msls it isn't based on uniqueness

Pat wrote:
ronk wrote:
Code: Select all
Sets:
                   Bn = units of the base set
  Base (size N):   B  = B1 + B2 ... + BN
  Base Intersect:  BI = B1*B2 + B1*B3 ... + B1*BN + B2*B3 ... + (BN-1)*BN

                   Cn = units of the cover set
  Cover (size N):  C  = C1 + C2 ... + CN
  Cover Intersect: CI = C1*C2 + C1*C3 ... + C1*CN + C2*C3 ... + (CN-1)*CN

  Hidden Pattern:  H  = (B \ C) + BI
  Exclusion:       E  = (C \ B) + CI


Symbol Key:
    '+'   <=> union         ('|'       in C++)
    '*'   <=> intersection  ('&'       in C++)
    '\'   <=> substraction  ('X & ~Y'  in C++)



Conjecture:
    If the "hidden set" is empty,
    then the "exclusion set" is empty also.

yes

1. exclusions in C\B
    B will supply the digit N times (not less since none in BI);
    all N will be in C (since none in B\C);
    this supplies the full quota of the digit for the N units of C,
    therefore, exclude it elswhere in C (i.e. in C\B).
2. exclusions in CI
    placing the digit in CI would satisfy 2 (or more) units of C,
    so C could only take N-1 of the total N supplied by B.
anyone wants to phrase it more formally?


here some proof for the math for N digits in N sectors in N cells. written by pat for the NXN coverset for 1 digit
nothing changes to move this up to n digits as we can directly use obis fish mathematics and nxn fish to construct msls
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1430
Joined: 05 September 2006

Re: paquita's SE 11.8 puzzle

Postby SpAce » Tue May 05, 2020 3:44 am

Hi eleven,

eleven wrote:When you look at my post above (i corrected the row 3 counts), you can easily find the 4x5 MSLS's after adding the counts for digit 4.

Yes, and I like your methodical procedure. I guess it was mostly meant for programmers or situations where the two groups might be harder to identify directly? I mean, in this particular case it's probably faster to pick the two groups visually, including which group the misfit digit '4' should belong to. In other situations it might not be so easy, and programmers need to be methodical anyway.
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: paquita's SE 11.8 puzzle

Postby SpAce » Tue May 05, 2020 4:08 am

tarek wrote:SpAce You should change you name to CoMet if you make these short visits after a long absence! Nice to hear from you though!

That's a good one, tarek! :lol: For the next perihelion, I promise I'll make every effort to beat Halley's to the punch! It's good to be back, even briefly, and to see familiar 'faces' around. I haven't quit the forum; I'm just recharging batteries (and probably not just mine, lol). I try to login every once in a while to keep my account active until I have more time. I'm happy to see that there's quite a bit of activity on the forum, including some new faces and apparently no other recent vacationers among the regulars. Has anyone heard of Dan, though? Hope he's in good health. Keep up the great work, everyone!
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

Re: paquita's SE 11.8 puzzle

Postby SpAce » Tue May 05, 2020 6:45 am

Hi Cenoman,

Cenoman wrote:You forced me to get out my confinement ! Happy to hear you breaking your vow of silence...

Great to hear from you too! And you have excellent input, as always. I especially loved your treatment of the second puzzle.

I have a personal conjecture. When you have found a MSLS, there exists a second one, that I would call a dual one, having the same base digits, but using the unused lines of the first one with inverted roles

Yes, that's true. However, I recall from my few earlier experiments that it was sometimes difficult or even impossible (with my poor balancing skills) to make both orientations work. Thus, sometimes one or the other is the more natural fit (like in your second example); other times it might not matter much (like in the first example). Would you agree?

Now, just to prove it's me and not someone who's hijacked my account, I have to complain about terminology :D Hope you don't mind! One of my pet peeves about the common MSLS terms is the "base digits". I know it's not your invention so don't take it personally. I just think it's extremely confusing because we're dealing in a context where "base" has an established and entirely different meaning. That's why I strongly agree with David's preference of "home" instead of "base", for the same reason he suggested it:

David P Bird wrote:The digits are partitioned into two sets – a 'Home' set typically of 4 digits and the complementary 'Away' set of 5 digits (these names have been selected to avoid any confusion with base and cover sets.)

I would also suggest another term for "dual" to capture your meaning better. David used "complementary":

David P Bird wrote:Another point to note is that there is set of 20 cells with no digits covered at all where the unused rows and columns intersect that form a complementary locked set. This is the set that would have been found if the Home sets were allocated to the rows and the Away set to columns.

I have adopted that term too. On the other hand, "dual" is more of a synonym for "double", and thus a related pair of MSLSs could be seen as a "dual MSLS".

Anyway, that's not very important. Your method of finding and treating the MSLSs is! Very nice. Here's a new coloring of the first puzzle which shows both the 16-cell MSLS (light green cells) and its complementary 23-cell one (dark green cells). (My original coloring shows the 20-cell and 19-cell variants of the same.)

mslspic2.png
mslspic2.png (92.8 KiB) Viewed 642 times

The second puzzle was a bit tougher, and I was really impressed how you found the balances! Even the easier 16-cell variant is not quite trivial because it requires one to see that the '6'-cover isn't needed for row 2 even though it's not a solved cell there. The 24-cell version is even harder, requiring a true balancing act (3 columns -> 2 boxes). Figuring out those kinds of things is what makes dealing with MSLS fun, I think. Nice job!

Here's my coloring for the second puzzle, showing both variants. Again, light green for the 16-cell variant, and dark green for the 24-cell one.

mslspic3.png
mslspic3.png (92.08 KiB) Viewed 642 times
User avatar
SpAce
 
Posts: 2671
Joined: 22 May 2017

PreviousNext

Return to Puzzles