The New Sudoku Players' Forum

by **blue** » Fri Jun 21, 2013 2:35 am

Hi David,

David P Bird wrote:
blue wrote:I liked your notion about looking for cells/houses that would left with no candidates if the "would be" rank 0 eliminations were performed, and adding base sets if for them if any are found. I think it won't always apply. If the base set(s) don't overlap (each other, or) any other base set, then it definitely works.

Your twisting my words here somewhat because instead of adding a truth set I was taking the opportunity to reduce the link sets by using box links in place of row or column links so there would be no danger of a truth set overlap (the two methods have the same end effect though).

My mistake, yes.
I read something more into your fine idea.

Regards,
Blue.

Batting 1000 recently ... a mistake in every post, it seems

by **ronk** » Fri Jun 21, 2013 3:46 pm

David P Bird wrote:
ronk wrote:
David P Bird wrote:Of course that fits in nicely with the scheme I use for MSLS. It also provides the opportunity to build in a fin cell check so when the pattern turns out to be rank 1 they can be eliminated.
There are "1-rank" patterns that cannot reasonably be reduced to 0-rank, so what do you mean?
What I had in mind is probably a remote possibility, but only experience will tell. Say we have a row/column intersetion cell that contains 1 digit that is doubly covered and all the others are uncovered, then we can't create a cell truth set for it (well, not in my mind anyway). So if the pattern proves to be a rank 1 rather than a rank 0, that doubly covered candidate can be eliminated.

That makes sense, thanks. My thinking went off in a different direction because you referred to the intersection as a "fin cell." However, since I think your MSLS puts one set of digits in rows and the complementary digits in columns, I don't see how such an intersection could occur.

by **blue** » Fri Jun 21, 2013 4:45 pm

Hi David,

blue wrote:
David P Bird wrote:Naturally enough it poses one more question in my mind - when working with complementary digit sets, would it be possible to confine one of the digit sets to just one type of house and still cover all the possibilities?

I don't have much time to think about [that] question right now.
My gut says no, but who knows. More later.

My mind was terribly out of whack that day, it seems.

Yes, you can do that. You can first convert to the form with row truths and column, box, and cell links. Then you can choose complementary digit sets, and use Obi-Wahn transformations to convert row truths for one digit set, into column truths and row links. The final result would (in general) include row truths for one digit set, column truths for the other, and links of any type.

Another option would be to do like above, but convert row truths for one digit set, into box truths and row links, leaving row truths for one digit set, box truths for the other, and again, links of any type.

To get column truths for one digit set, and box truths for the other, you could do a similar thing, starting with a conversion to column truths and row, box and cell links, and then converting the column truths for one digit set, into box truths and column links.

Best Regards,
Blue.

by **David P Bird** » Fri Jun 21, 2013 7:41 pm

Here's another of Champagne's problem grids that nearly has the diagonal pattern of givens in boxes 5689 to support an SK Loop. The multi-fish digits would be 1234 and if only r5c4 held another given we'd be away. However I've found two MSLSs that will provide identical eliminations.

98.7.....6.7...8......85...4...3..2..9....6.......1..4.6.5..9......4...3.....2.1.;28180;GP;2011_12

Code: Select all: *-------------------------*-------------------------*-------------------------* | <9> <8> 12345 | <7> 126 346 | 1234-5 3456 1256 | | <6> 12345 <7> | 1234-9 129 349 | <8> 3459 1259 | | 123 1234 1234 | 123469 <8> <5> | 12347 679-34 679-12 | *-------------------------*-------------------------*-------------------------* | <4> 157 1568 | 689 <3># 6789 | 157 <2># 5789-1 | | 123-578 <9> 123-58 | 248 257 478 | <6> 3578 1578 | | 23578 2357 23568 | 2689 5679-2 <1># | 357 5789-3 <4># | *-------------------------*-------------------------*-------------------------* | 123-78 <6> 1234-8 | <5> 17 378 | <9> 478 278 | | 12578 1257 12589 | 1689 <4># 6789 | 257 5678 <3># | | 3578 3457 34589 | 3689 679 <2># | 457 <1># 5678 | *-------------------------*-------------------------*-------------------------*

MSLS:34689N47, 57N5689, 3N123, 5N4 (22 Cells)
Links 1234r3, 578r5, 78r7, 689c4, 57c7, 24b5, 13b6, 13b8, 24b9, (22 Digits)

MSLS: 1257N5689 (16 Cells)
Links: 6r1, 9r2, 578r5, 78r7, 12c5, 34c6, 34c8, 12c9, 5b3, (16 Digits)
=> Elims:5r1c7,9r2c4,34r3c8,12r3c9,1r4c9,578r5c1,58r5c3,8r5c4,2r6c5,3r6c8,78r7c1,8r7c3,(18 Candidates 12 cells)

The first uses link sets in the boxes for digits in the set (1234) and link sets for digits in the complementary set for r57 and c47 which would normally provide an SK loop elimination set, but not in this case because of the problem cell r5c4. However by adding a 1234r3 link set a rank 0 emerges! (It looks like this tactic will often be available) Note here that the elimination of (8)r5c4 results because it is an 'internal' fin candidate doubly covered in cell covered by a truth set.

The second is the result of trying out link sets for (1234) in the columns and for (56789) in the rows. As shown 5r12 has been taken out of the original configuration tried with 17 link sets and replaced with 5b3 so reducing the count to 16 and hence achieving rank 0. (As referred to in out previous exchange Blue. It's easy to spot because (5)r1c3 and (5)r2c2 are PEs for the rank 1 pattern but would leave box 1 with no other 5 left.) This looks a far more elegant solution as uses less sets, the MSLS are in a neat 4x4 array, and all the fin cells are external to the truth set cells.

Warning the following trains of thought may be half-baked.

Confining the truth sets to cells only is very appealing to me because it's directly equivalent to my MSLS search method. However it doesn't allow the cover patterns for the individual digits to be treated as components and capable of being added or subtracted separately because the truth sets are all shared.

I haven't tried in earnest to transform one pattern into the other because it appears to me that the operation must be performed in two phases: the first will fragment the truth sets across the 4 container types, and the second will therefore have to restore them all to being cell sets again. It gives me flashbacks to the days when I tried to find the integrals of mathematical functions - which I never mastered!

Blue,

The reason I posed my question was practical. If we can find a way to prove that every rank 0 elimination pattern can be found by confining the rows, columns and boxes to link sets, and further confining all digits in one partition to just one house type, then the number of combinations to test would fall dramatically.

I'm coming to believe that what's good for a manually controlled approach won't be so good for a brute force iteration of every option.

David

by **JC Van Hay** » Fri Jun 21, 2013 8:36 pm

Hi David,

David P Bird wrote:Confining the truth sets to cells only is very appealing to me because it's directly equivalent to my MSLS search method.

That's good news, at least for me ! Try the following, if you want to, in the last Champagne's list : do find if it is possible to extract 16 unsolved cells containing a maximum of 4 candidates at the intersection of 4 rows and 4 columns and check if it gives rise to a Rank 0 Logic! This is a topological problem relatively easy to solve and a' little' more general than your MSLS approach.
Best Regards, JC.

by **Leren** » Tue Jun 25, 2013 3:45 am

Hi all, I've taken JCVH's suggestion and looked for 16 cell MSLS Rank 0 logic sets in the list of puzzles that Champagne posted on p 28 of this thread.

I was successful in 204 out of 219 of those puzzles. In these cases the MSLS logic eliminations matched the equivalent "conventional" Multifish eliminations.

Some of the puzzles had givens one cell of in the 16 cell grid but the MSLS method still works with a reduced link count of 15.

For the following puzzles I found no MSLS logic. In all such cases I found no Multifish either.

Hidden Text: Show

Tentative conclusion: if a 3-5 digit R,C or X Multifish Rank 0 logic can be found then an equivalent 16 MSLS can also be found.

MSLS is a great method - a bit quicker and not as messy as Multifish to code.

Perhaps others can check these 15 puzzles to see if there is a Rank 0 logic set in them that I can't see.

Leren

by **champagne** » Tue Jun 25, 2013 6:16 am

Hi leren

no rank 0 on my side with the current code. Likely an old bug, but I wait for the results of other players

by **David P Bird** » Tue Jun 25, 2013 9:21 am

Thanks Leren!

I took it that JCVH's challenge was confined to puzzle #219 not the whole collection. In that case it's easy to prove that no 4x4 array of unresolved cells with <5 candidates exists either before or after basic eliminations. As your results show that's one of the puzzles that has no multi-fish pattern.

Leren wrote: Tentative conclusion: if a 3-5 digit R,C or X Multifish Rank 0 logic can be found then an equivalent 16 MSLS can also be found.

We should still be cautious here because I believe that this collection contains grids that almost support the SK loop pattern. The other multi-fish patterns Champagne has found also need to be checked.

Leren wrote:MSLS is a great method - a bit quicker and not as messy as Multifish to code.

It's good to have someone else confirm what I've been thinking for some time now. But now it appears that the procedure should be made to be two-tailed to
1) check if all doubly covered cells equal the link count to find a Naked Set with external eliminations
2) check if the all the covered cells equal the link count to find a Hidden Set with internal eliminations
For Xsudo users 2) involves treating the house sets as truths and the intersection cells as links

I'm afraid I don't have time to manually run through puzzle collections looking for exceptions.

JC Van Hay wrote:.. find if it is possible to extract 16 unsolved cells containing a maximum of 4 candidates at the intersection of 4 rows and 4 columns and check if it gives rise to a Rank 0 Logic! This is a topological problem relatively easy to solve and a' little' more general than your MSLS approach.

As you say it's relatively easy to check if this situation exists, but at what stage in a developing solution should it be done? There is also the problem that Leren has discovered; that in some cases the 4x4 matrix of cells can contain a given.

David

by **Leren** » Tue Jun 25, 2013 12:26 pm

PM for the following puzzle from Champagne's List showing MSLS eliminations for a set with a non base given in the 4 x 4 cell grid

Code: Select all: *--------------------------------------------------------------------------------* | 9 8 12345 | 7 *346 *126 | 1234-5 *1456 *2356 | | 7 12345 6 | 1234-9 *349 *129 | 8 *1459 *2359 | | 123 1234 1234 | 1234689 5 689-12 | 12347 679-14 679-23 | |--------------------------+--------------------------+--------------------------| | 4 156 158 | 689 6789 3 | 157 2 5678 | | 23568 9 2358 | 268 1 678-2 | 357 5678 4 | | 123-68 123-6 7 | 24-68 *468 *5 | 9 *168 *368 | |--------------------------+--------------------------+--------------------------| | 123-8 1234-7 9 | 5 *378 *178 | 6 *478 *278 | | 1568 14567 1458 | 1689 2 6789-1 | 457 3 5789 | | 23568 23567 2358 | 3689 6789-3 4 | 257 5789 1 | *--------------------------------------------------------------------------------*

MSLS: Base 1234; r1267 c5689: 15 Links; 6r1 9r2 68r6 78r7; 34c5 12c6 14c8 23c9; 5b3;

18 Eliminations : r1c7 <> 5, r2c4 <> 9, r3c6 <> 12, r3c8 <> 14, r3c9 <> 23, r5c6 <> 2, r6c1 <> 68, r6c2 <> 6, r6c4 <> 68, r7c1 <> 8, r7c2 <> 7, r8c6 <> 1, r9c5 <> 3

Note the presence of a non-base given 5 at r6c6 which reduces the required links to 15.

Corresponding X style Multifish for the same 18 eliminations : 19 Truths = { 1234R6 1234R7 1234C4 1234C7 3N123 } 19 Links = { 1234r3 1n7 2n4 6n124 7n12 1b68 2b59 3b68 4b59 }

Leren

by **JC Van Hay** » Tue Jun 25, 2013 1:32 pm

Thanks a lot for checking, Leren.

Leren wrote:Some of the puzzles had givens one cell of in the 16 cell grid but the MSLS method still works with a reduced link count of 15.

David wrote:There is also the problem that Leren has discovered; that in some cases the 4x4 matrix of cells can contain a given.

I was well aware of that.

here

The basic loops can contain less cells provided that each time a cell is removed a cover set is removed.
But this also means that a given can take the place of a removed cell.

Leren, it would be interesting if you could extend the test on Champagne's list of hardest ( file 03 G multi fish seen).
However,

Leren wrote:Tentative conclusion: if a 3-5 digit R,C or X Multifish Rank 0 logic can be found then an equivalent 16 MSLS can also be found.

is contradicted by the puzzle 55;elev. See an analysis in the same post.
Therefore I would recommend you to read again, but with a grain of salt as I didn't necessarily cover all the cases, the following posts

David wrote:
JC Van Hay wrote:..find if it is possible to extract 16 unsolved cells containing a maximum of 4 candidates at the intersection of 4 rows and 4 columns and check if it gives rise to a Rank 0 Logic! This is a topological problem relatively easy to solve and a' little' more general than your MSLS approach.
As you say it's relatively easy to check if this situation exists, but at what stage in a developing solution should it be done?

I would usually look for all the multi-digit rank 0 configurations of increasing complexity after having found all the placements and all the eliminations for each digit (this is what I would consider the most natural understanding of ordered basics

).

JC

by **David P Bird** » Tue Jun 25, 2013 2:51 pm

Hi JC,

Some fairly trivial points which depend to some degree on what different players feel most comfortable with:

Without intending to be picky, I'm far from sure that everyone here (particularly Champagne) performs the same basic checks. I look for naked and hidden singles, doubles and triples (but not quads), Line/Box eliminations, and un-finned basic fish, but I think I'm now in the minority.

While the search is limited to unresolved cells with <5 digits I guess your 4x4 arrays can be found very efficiently by a computer (doing it by hand I was greying out rows that couldn't be included, then columns, then rows again etc until no more reductions could be made). However if givens and solved cells are allowed to be included, then it gets a lot more complex and I wouldn't want to even try to do it manually. This would get worse when the basic first steps add more singles.

Coming at it from the other direction I try to identify how the partitions of the digits are likely to fall by looking at the distribution of the givens in the various houses. The fist thing I look for is boxes with givens lying on a diagonal, then I then look for digits that often occur together as givens in rows and columns. (I have even thought that a 9x9 chart for digit A vs digit B could be filled with how often this happens to streamline a computer search). Now I've developed an eye for them, it doesn't take long to identify the favourites. My banker rows are then the ones where the set of 4 never appear as givens, and the banker columns where 2 of them occur together.

David

by **blue** » Tue Jun 25, 2013 3:02 pm

Leren wrote:Perhaps others can check these 15 puzzles to see if there is a Rank 0 logic set in them that I can't see.

champagne wrote:no rank 0 on my side with the current code. Likely an old bug, but I wait for the results of other players

Same results here - no rank 0 logic that my code can detect.
I don't have anything to check for X patterns and variations.

Champagne: "Likely an old bug" ? ... did you expect something, or identify a "close" X pattern for these puzzles ?

Blue

by **champagne** » Tue Jun 25, 2013 7:52 pm

blue wrote:Champagne: "Likely an old bug" ? ... did you expect something, or identify a "close" X pattern for these puzzles ?

Blue

hi blue,

I had to go back in the past to understand how it came.

In my former process, I used the potential of eliminations in a multi floors pattern to see if I had a chance to find a rank 0 logic.

The first puzzle has a potential of more than 100 eliminations with the floors 16789.

My solver worked out a bugged rank 0 logic in that pattern. It was a "X" logic using rows 3 9 and columns 49.

It seems to me that you have a valid logic 28 truths 28 links (4 cells at the crossings), but with no elimination.

As the bug is not granted so it could be that some of these puzzles have a valid complex "X" logic

by **Leren** » Wed Jun 26, 2013 12:40 pm

I've improved my MSLS solution process to include 4 x 4, 4 x 5, 5 x 4 and 5 x 5 cell grids (16 - 25 Truths)

I've tested all puzzles up to # 100 of Champagnes 03 G Multifish seen file with MSLS solutions similar to the Multifish seen in each puzzle.

I've informally tested up to puzzle # 400 but need to retest with the improved code.

An example is puzzle 55 which was mentioned above.

Code: Select all: *--------------------------------------------------------------------------------* | 123-4 249 1349 | 2349 5 6 | 1237-9 8 179 | |*2345 4589-2 7 | 1 *238 *2349 |*2369 *239 569 | | 6 2589 13589 | 2389 237-8 237-9 | 4 123-9 159 | |--------------------------+--------------------------+--------------------------| | 127-4 2467 146 | 2369 1237-6 8 | 5 137-49 1479 | |*1457 3 4568-1 | 569 *167 *1579 |*1789 *1479 2 | | 9 2578 158 | 235 4 1237-5 | 137-8 6 178 | |--------------------------+--------------------------+--------------------------| |*345 1 4569-3 | 7 *2368 *2345 |*2689 *249 4689 | |*457 4569-7 2 | 4568 *168 *145 |*16789 *1479 3 | | 8 467 346 | 2346 9 123-4 | 127-6 5 1467 | *--------------------------------------------------------------------------------*

MSLS 1 : Base 1237; r2578 c15678: 20 Links; 23r2 17r5 23r7 17r8; 45c1 68c5 459c6 689c7 49c8; with 17 eliminations as shown in the PM.

A Multifish I see in this puzzle for the same 17 eliminations is : 20 Truths = { 1R13469 2R13469 3R13469 7R13469 } 20 Links = { 1c39 2c24 3c34 7c29 1n17 3n568 4n158 6n67 9n67 }

Another example is puzzle # 1426 that Champagne posted on p 28 of this thread:

Code: Select all: *--------------------------------------------------------------------------------* |*134 248-13 *123 | 4589 *3589 6 | 7 2589-1 *189 | |*467 5 *267 | 1 *789 489 | 289-6 3 *689 | | 1367 13678 9 | 578 2 358 | 568 158 4 | |--------------------------+--------------------------+--------------------------| | 2 1367 13567 | 5789 137-589 13589 | 345689 145789 1367-89 | | 13567 1367 8 | 579 4 1359 | 3569 1579 2 | | 9 137 4 | 6 137-58 2 | 358 1578 137-8 | |--------------------------+--------------------------+--------------------------| |*1345 249-13 *1235 | 24589 *1589 7 | 2489-3 6 *389 | |*4567 249-67 *2567 | 3 *5689 4589 | 1 2489-7 *789 | | 8 1234679 1367-2 | 249 16-9 149 | 2349 2479 5 | *--------------------------------------------------------------------------------*

MSLS 1 : Base 1367; r1278 c1359: 16 Links; 13r1 67r2 13r7 67r8; 4c1 2c3 589c5 89c9; 5b7; for 20 eliminations as shown in the PM.

I now suspect that all 3-5 digit R, C and X style Multifish will have an equivalent 16 - 25 cell MSLS equivalent. At this stage I haven't seen the need for
a 25 cell grid. It's getting late so I'll continue testing tomorrow. Hopefully I haven't made too many blunders in this post.

Leren

by **David P Bird** » Wed Jun 26, 2013 4:39 pm

Leren that's good progress!

You should find that 5x5 and 4x4 grids come in complementary pairs (like simple fish) that will make the same eliminations, when the 4x4 one is easier to notate.

For 4x5 the compliment is another 5x4, but one may use fewer digits than the other.

David

The New Sudoku Players' Forum

Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume

Re: Exotic patterns a resume