The New Sudoku Players' Forum

[999_Springs]

Code: Select all

98.|7..|...
76.|.8.|...
..5|...|...
---+---+---
8..|9..|4..
..3|...|.2.
...|..1|..5
---+---+---
...|46.|7..
...|.9.|6.2
...|..2|.34

this is the most recent 11.8 rated puzzle in the hardest sudokus thread, by paquita

if you're stuck i'll get you started

Hidden Text: Show

after the locked candidate 3 in r3 and b1 you get to here

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

there is a MSLS with the 16 cells marked with * as base set and the numbers outside the rows and columns as cover set

it gives 16 eliminations indicated in the grid and now the puzzle drops to SE 7.2 and you can finish it off from there

[yzfwsf]

The picture below is just for fun.

Hidden Text: Show

MSLS.png (58.09 KiB) Viewed 1051 times

[denis_berthier]

Hidden Text: Show

after the locked candidate 3 in r3 and b1 you get to here

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

there is a MSLS with the 16 cells marked with * as base set and the numbers outside the rows and columns as cover set

Impressive case of covering sets. How did you find it? Manually?

Edit: After trying it, I find it still more impressive. 11.8 is close to the hardest known puzzles (11.9). Your 16 eliminations bring it to an easy level W4.
Notice that in the B?B classification, it is not so close to the hardest known (B7B): it is in B5B.
(I don't have any rule to deal with this pattern in SudoRules, but I can use simulated eliminations at the start.)

Hidden Text: Show

(bind ?*simulated-eliminations* (create$
415 927 138 139 742 745 556 159 263 972 183 386 586 188 588 193
))
(solve "98.7.....76..8......5......8..9..4....3....2......1..5...46.7......9.6.2.....2.34")

***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = W+SFin+JE
*** using CLIPS 6.31-r761
***********************************************************************************************
Simulated eliminations of 415 927 138 139 742 745 556 159 263 972 183 386 586 188 588 193
singles ==> r8c8 = 8, r8c6 = 7, r8c3 = 4
212 candidates, 1076 csp-links and 1076 links. Density = 4.81%
whip[1]: b1n4{r3c2 .} ==> r3c8 ≠ 4, r3c5 ≠ 4, r3c6 ≠ 4
whip[1]: c5n4{r6 .} ==> r5c6 ≠ 4
whip[1]: b1n3{r3c2 .} ==> r3c9 ≠ 3, r3c4 ≠ 3, r3c5 ≠ 3, r3c6 ≠ 3, r3c7 ≠ 3
naked-pairs-in-a-column: c3{r1 r2}{n1 n2} ==> r7c3 ≠ 2, r7c3 ≠ 1, r4c3 ≠ 2, r4c3 ≠ 1
whip[1]: c3n1{r2 .} ==> r3c1 ≠ 1, r3c2 ≠ 1
whip[1]: c3n2{r2 .} ==> r3c1 ≠ 2, r3c2 ≠ 2
hidden-pairs-in-a-column: c5{n4 n7}{r5 r6} ==> r6c5 ≠ 3, r6c5 ≠ 2, r5c5 ≠ 5
hidden-pairs-in-a-row: r6{n3 n8}{c4 c7} ==> r6c7 ≠ 9, r6c4 ≠ 6, r6c4 ≠ 2
singles ==> r4c5 = 2, r3c5 = 1, r9c5 = 5, r1c5 = 3
naked-triplets-in-a-column: c4{r6 r8 r9}{n8 n3 n1} ==> r5c4 ≠ 8
hidden-triplets-in-a-block: b7{r9c2 r9c3 r7c3}{n7 n8 n9} ==> r9c3 ≠ 6, r9c2 ≠ 1
hidden-single-in-a-block ==> r9c1 = 6
biv-chain[3]: r2c3{n1 n2} - r1n2{c3 c7} - c7n5{r1 r2} ==> r2c7 ≠ 1
biv-chain[3]: r3c6{n9 n6} - r5c6{n6 n8} - c9n8{r5 r3} ==> r3c9 ≠ 9
biv-chain[3]: c9n8{r3 r5} - r5c6{n8 n6} - c4n6{r5 r3} ==> r3c9 ≠ 6
biv-chain[3]: b1n2{r1c3 r2c3} - r2c4{n2 n5} - c7n5{r2 r1} ==> r1c7 ≠ 2
singles ==> r1c3 = 2, r2c3 = 1
biv-chain[4]: r3c6{n9 n6} - r5c6{n6 n8} - c9n8{r5 r3} - b3n7{r3c9 r3c8} ==> r3c8 ≠ 9
biv-chain[3]: r3c8{n7 n6} - r1c9{n6 n1} - c8n1{r1 r4} ==> r4c8 ≠ 7
biv-chain[4]: r5c6{n8 n6} - c4n6{r5 r3} - r3c8{n6 n7} - r3c9{n7 n8} ==> r5c9 ≠ 8
singles ==> r3c9 = 8, r3c8 = 7
whip[1]: r3n6{c6 .} ==> r1c6 ≠ 6
biv-chain[3]: b6n7{r5c9 r4c9} - r4c3{n7 n6} - r6n6{c3 c8} ==> r5c9 ≠ 6
whip[1]: r5n6{c6 .} ==> r4c6 ≠ 6
biv-chain[3]: r3n9{c7 c6} - c6n6{r3 r5} - r5n8{c6 c7} ==> r5c7 ≠ 9
finned-x-wing-in-rows: n9{r5 r7}{c9 c2} ==> r9c2 ≠ 9
naked-single ==> r9c2 = 7
whip[1]: b7n9{r9c3 .} ==> r6c3 ≠ 9
biv-chain[3]: r9n1{c4 c7} - r5c7{n1 n8} - b5n8{r5c6 r6c4} ==> r9c4 ≠ 8
stte

[eleven]

How did you find it? Manually?

See e.g. this post, how to find them manually. I think, it is based on David Birds method. The point is, that you have to look at the solved cells to get a start.
[edit: corrected the link]

[denis_berthier]

How did you find it? Manually?

See e.g. this post, how to find them manually. I think, it is based on David Birds method. The point is, that you have to look at the solved cells to get a start.

Hi eleven,
The link doesn't work.
The general problem with set covers is the combinatorial explosion when the number of base sets (and therefore of cover sets) increases - unless some specific conditions restrict the search to some special cases. It is the case here: only rc-cells are used as base sets. But even so, something more is required to focus on the proper 16 cells.
I know you don't like whips very much, but they are some generic way of (partially) dealing with combinatorial explosion. In case of set covers, I have no idea how to do.

[eleven]

I am not an expert here, but i think, that the big majority of MSLS's are just split by row/column sets.
With the look at the givens there are not much possible combinations to check.
Maybe some can be "repaired" with slight changes.

[Cenoman]

P&P first step:

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

MSLS
Base(1235); 16 cells r1247 c3689 (tagged '<')
16 links: 12c3, 35c6, 15c8, 13c9, 46r1,49r2, 67r4, 89r7
16 eliminations -2r6c3, -1r89c3, -5r5c6, -35r8c6, -1r3c8, -15r8c8, -1r35c9, -4r1c5, -9r2c7, -7r4c25, -9r7c2
=> 8 placements & basics

NOTE: as a reference document for finding MSLS's manually, I'd suggest this one

End with two AIC's

Code: Select all

 +----------------------+------------------+----------------------+
 |  9     8       12    |  7    3    456   |  125    146   6-1    |
 |  7     6       12    |  25   8    459   | E1235   149  F139    |
 |  34    34      5     |  26   1    69    |  289    679   6789   |
 +----------------------+------------------+----------------------+
 |  8    f15      67    |  9    2   a36-5  |  4      167   367-1  |
 | e145  e14579   3     |  56   47   68    | d189    2     6789   |
 |  24    2479    679   |Cb38   47   1     | D38     679   5      |
 +----------------------+------------------+----------------------+
 |  123   123     89    |  4    6    38    |  7      5   FA19     |
 |  135   135     4     |  13   9    7     |  6      8     2      |
 |  6     79      789   |Cb18   5    2     |Bc19     3     4      |
 +----------------------+------------------+----------------------+

2. (3)r4c6 = (3-81)r69c4 = r9c7 - r5c7 = r5c12 - (1=5)r4c2 => -5 r4c6
3. (1)r7c9 = r9c7 - (1=83)r69c4 - r6c7 = r2c7 - (3=91)r27c9 => -1 r14c9; ste

Added a link to David P. Bird's MSLS document.

EDIT April 24, 3:30 pm CET: as incredible as it may sound, I had not consulted 999_Springs hidden text, when I first posted this and yes, I found the MSLS manually.

[Mauriès Robert]

Hi Cenoman.
Nice resolution!
Can you tell me where I can find the proof of elimination evidence generated by an MSLS?
Thank you
Robert

[eleven]

The proof is simple:
You have 16 cells, and all the 16 digits outside the puzzle have to go into one of them, because there is no other candidate in the cells.
(no candidate matches 2 of the digits outside - trivial here, because you have different digits for the rows and the columns).

[Mauriès Robert]

The proof is simple:
You have 16 cells, and all the 16 digits outside the puzzle have to go into one of them, because there is no other candidate in the cells.
(none of them can be both in a row and a column).

It is therefore a demonstration based on the uniqueness of the solution previously admitted, if I understand correctly.
Is there a demonstration that does not use the uniqueness of the solution?
Robert

[eleven]

No, it has nothing to do with uniqeness.

For each candidate in each cell of the pattern you have exactly one candidate outside (for this row in the pattern or column resp.). So if you set any candidate in a cell, you can strike out exactly one outside. There are not more or less.
This means, a candidate outside must be in one of the row or column cells of the pattern it sees, and you can eliminate it from the other cells of the row/column.

Btw i warn you, when you read about that somewhere. The ones talk about home/aways, others about truths/links, others about base/cover.
At the end you don't need that all to understand them. They my be helpers to find them (e.g. start with a base in the rows and try to cover the rest with columns - but it has no relevance here, what is one and the other, as long as they see all candidates in the pattern - and none is seen twice).

[Cenoman]

Hi Cenoman.
...where I can find the proof of elimination evidence generated by an MSLS?

Hi Robert,
I don't know . AFAIK, the MSLS pattern results from thoughts started long ago about SK-Loops, followed by multifishes, and somehow encompassed by MSLS's.
All I have read about MSLS's is David's document referenced in my post above. This document is not a full theory of MSLS's, but rather a guide how to search them. While studying this, I also wondered how the pattern worked.
eleven told you:

the proof is simple

, much simpler than the pattern itself
Personally, I convinced myself, when I saw that the truth-link balance allowed to put the pattern into a matrix. This matrix is a symmetric Pigeonhole Matrix (i.e. the first column is a Weak Inference Set). The order of the columns can be any one. Therefore, each column can be the first one and yields its own eliminations.

Reference for matrices in sudoku here

Here is the 16x16 symmetric PM for the above MSLS

Hidden Text: Show

Code: Select all

      1c3  2c3  4r1  3c6  5c6  6r1  1c8  5c8  1c9  3c9  4r2  9r2  6r4  7r4  8r7  9r7       
r1c3   1    2    4
r1c6             4    3    5    6
r1c8             4              6    1    5
r1c9                            6              1    3
r2c3   1    2                                            4
r2c6                  3    5                             4    9
r2c8                                 1    5              4    9
r2c9                                           1    3         9   
r4c3   1    2                                                       6    7     
r4c6                  3    5                                        6    7
r4c8                                 1                              6    7
r4c9                                           1    3               6    7
r7c3   1    2                                                                 8    9
r7c6                  3    5                                                  8
r7c8                                 1    5                                   8    9   
r7c9                                           1                              8    9

[champagne]

as often, you can also use another TLG0 logic

truths={ 1235R1 1235R2 1235R4 1235R7 }
links={ r7c1 r4c2 r7c2 12C3 r2c4 r1c5 r4c5 35C6 r1c7 r2c7 15C8 13C9 }

with the same eliminations.

to eleven :

Right, the easiest MSLS, as here have the cells as crossings of rows and columns. But this group has many variants.
One interest of the MSLS group is that cells truths never have triple points.
For anybody interested in this field, I am trying to make an update of the old explorationshere TLG0 logic
My ongoing work is still locked for several days in my laptop currently out of order

[Mauriès Robert]

Hi Cenoman, Champagne, Denis, Eleven and all,
I just remembered that this discussion on the definition and demonstration of MSLS eliminations had already been done in 2019, but I had totally forgotten about it, I apologize.
Here is the link to that discussion: http://forum.enjoysudoku.com/sk-loops-and-msls-s-t36887-30.html on page 3.
Robert

[denis_berthier]

I don't understand all the fuss about this. We are talking of an exact cover problem - a problem whose solution has been known for decennies. It is know to be NP-complete.
999_spring made a very smart find for this puzzle. Finding the base and cover sets was great.
But there can be no debate about exact covers and I can't see the point of inventing new names for it.
Wikipedia is not always reliable, but in the present case, it has a good article: https://en.wikipedia.org/wiki/Exact_cover