The New Sudoku Players' Forum

[champagne]

Hi Eleven,
What is your definition of an MSLS ?
I can't find a rigorous definition on the forum.
Robert

I'll try my own answer.

The MSLS name was given by David P Bird years ago.

2 clear points.

It is a Truth/Links rank 0 in Allan Barker's model
All truths are cells.

In the first definition from David,
all cells were in the crossings of a" n rows p columns" matrix.
part of the digit were linked in rows, the rest in column

Other members of the forum used the same name for all kinds of rank 0 logic but keeping the restriction that all truths are cells.

I have also seen some non rank 0 logic, but IMO, this is not any more a MSLS

[Ajò Dimonios]

Hi Champagne.

Code: Select all

 Champagne wrote:
The MSLS name was given by David P Bird years ago.

2 clear points.

It is a Truth/Links rank 0 in Allan Barker's model
All truths are cells.

In the first definition from David,
all cells were in the crossings of a" n rows p columns" matrix.
part of the digit were linked in rows, the rest in column.

It is possible to include in this definition also all SK-loops simply by adding also the intersections between rows, columns and boxes, generally two rows two columns and four boxes.

Paolo

[eleven]

IMO yes, see also the hierarchy of SpAce here. (It is known, that he and David had different opinions in some topics)
[Edit: changed the link to the updated version]
From a manual solver's view, (pure) SK-loops can be spotted easily, row/column-MSLS's with some practice, including slightly different variants of both. Others i think, are rare (champagne ?)
As you can see, there was not much echo to his hierarchy. Those with different opinions were not active anymore and in practice we have different methods to find the different patterns (with the same property) both in manual and program solving.

[denis_berthier]

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.

XSudo relies on some version of a covering problem.
The problem when you want to apply covering to Sudoku is to find a proper sequence of base sets. If you adopt the rational approach of trying first the small base combinations (i.e. all the 2 base sets, then all the 3 base sets, ...), it is very unlikely you'll ever reach the 16 described in the first post.

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.

[denis_berthier]

I don't have Windows and I can't use XSudo. What does one get from XSudo when it is given this puzzle (with no added hint)? Does it find this pattern?

Me neither, with Apple, I don't have the possibility to use Xsudo. But Phil's solver (http://www.philsfolly.net.au/) finds this MSLS.

I checked this website and I could check it works.
However, I could find no explanation about the algorithm.

[yzfwsf]

My solver uses the matrix of 2 * 3, 3 * 2, 3 * 3, 3 * 4, 4 * 3, 4 * 4, 4 * 5, 5 * 4 as the base set, and then searches for the possible cover sets to see if rank 0 is available. In this process, I will try out various combinations of Rows columns and Boxes, and sometimes add other cells to base (at the same time, add additional link sets, but the added links are smaller than the added base)

[denis_berthier]

My solver uses the matrix of 2 * 3, 3 * 2, 3 * 3, 3 * 4, 4 * 3, 4 * 4, 4 * 5, 5 * 4 as the base set, and then searches for the possible cover sets to see if rank 0 is available. In this process, I will try out various combinations of Rows columns and Boxes, and sometimes add other cells to base (at the same time, add additional link sets, but the added links are smaller than the added base)

Hi yzfwsf
Thanks for the explanations. I understand they are designed to restrict the number of possible base sets.
Just to make sure I understand them properly:
1) do you consider only rc-cells (no rn, cn or bn cells) as possible members of the base sets? (or possibly also groups or 3 cells = intersections row-block or column-block ?)
2) when you say e.g. 3*4, does it mean "either 3 rows and 4 columns, or 3 columns and 4 rows, or 3 rows and 4 blocks, or 3 columns and 4 blocks"? or what else?
3) what's the difference between 3*4 and 4*3 ?

[Ajò Dimonios]

Code: Select all

+-------+-------+-------+
| 9 8 . | 7 . . | . . . |
| 7 6 . | . 8 . | . . . |
| . . 5 | . . . | . . . |
+-------+-------+-------+
| 8 . . | 9 . . | 4 . . |
| . . 3 | . . . | . 2 . |
| . . . | . . 1 | . . 5 |
+-------+-------+-------+
| . . . | 4 6 . | 7 . . |
| . . . | . 9 . | 6 . 2 |
| . . . | . . 2 | . 3 4 |
+-------+-------+-------+


I state that it is not easy to locate the MSLS base manually but it is still possible. If you think of a cross between columns and rows you have to start from the scheme without the candidates. At this point, if you think of a 4x4 cross between rows and columns, you need to think of two groups, one of 5 candidates and the other complementary of 4 candidates. At this point it is useful to look for the groups with greater numbers both in the rows and in the columns. It can be seen that three numbers (987) are present both in the first row and in the first column while there is only one row or column with only one element (5) in row 3. It is also noted that the same 5 appears together with other candidates with greater number in the columns (C3; C9) than in the rows (R3; R6), this is an indication that the 5 must be included in the base relative to the columns. If we think that the least numerous base is in the columns with 4 units we have to think of two units per column then C3, C6, C8 and C9. Since column 9 has three numbers, 5 is clearly chosen with 2 since 4 is not included in the other three columns. At this point the base 1235 for the columns is a good candidate also because in the columns C3, C6, C8 and C9 there are a total of 2x4 = 8 numbers of the group 1235. Now we just have to find 4 rows in which the group (46789) understands 12 overall so as to exclude 8. It is clear that the lines that have this characteristic are R1, R2, R4 and R7. At this point we are sure that the rank = 0 because both candidates in the rows and columns chosen are missing 8 candidates (8 + 8 = 16) which is equal to 4x4 = 16. It is therefore possible to perform the crossings and obtain the truth cells and consequently the links, 8 vertical and 8 horizontal, are obviously the same as the missing candidates in the selected columns and rows.

Paolo

[denis_berthier]

Hi Paolo
I guess that with some experience in looking for such patterns, your approach may work. But as you said, it's not so easy.

[denis_berthier]

Just curious about XSudo.
Could anyone who can run it try it and tell us what it does?

[yzfwsf]

Hi denis_berthier:
It means the intersection of m rows * n columns，my solver only use cells as base set.

[champagne]

My solver uses the matrix of 2 * 3, 3 * 2, 3 * 3, 3 * 4, 4 * 3, 4 * 4, 4 * 5, 5 * 4 as the base set, and then searches for the possible cover sets to see if rank 0 is available. In this process, I will try out various combinations of Rows columns and Boxes, and sometimes add other cells to base (at the same time, add additional link sets, but the added links are smaller than the added base)

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

[champagne]

Hi Champagne.

Code: Select all

 Champagne wrote:
The MSLS name was given by David P Bird years ago.

2 clear points.

It is a Truth/Links rank 0 in Allan Barker's model
All truths are cells.

In the first definition from David,
all cells were in the crossings of a" n rows p columns" matrix.
part of the digit were linked in rows, the rest in column.

It is possible to include in this definition also all SK-loops simply by adding also the intersections between rows, columns and boxes, generally two rows two columns and four boxes.

Paolo

Hi Paolo,

If you have a look to my summary of the TLG (work in progress)

http://forum.enjoysudoku.com/tlg0-logic-truths-links-groups-rank-0-t37603.html


the MSLS applied to the SKloop is the second well identified pattern for a big MSLS start. One important point is that it can work when the SKloop fails (called sometimes almost SK loop in the forum) . In such MSLS, the links structure is not as clear as in the np usual case.

[champagne]

From a manual solver's view, (pure) SK-loops can be spotted easily, row/column-MSLS's with some practice, including slightly different variants of both. Others i think, are rare (champagne ?)

Hi eleven,

I am convinced that we have many variants of MSLS, but then, the question is "how can a manual player find them".
From past experience several members of the forum (among them "blue") have engines covering many other cases.

And we have still more accepting a mix mode for truths. "yzfwsf" produced one of "size 4" recently with 2 cells and 2 digits truths and one of size 3 with one cell and 2 digit truths.

BTW this pushed me to restart the MSLS analysis from the very beginning, the naked pair. This is what I am doing in parallel with the fish analysis in TLG mode.
I hope at the end to have fresh Ideas to produce these variants.

[denis_berthier]

Hi denis_berthier:
It means the intersection of m rows * n columns，my solver only use cells as base set.

OK. Thanks