Exotic patterns a resume

Advanced methods and approaches for solving Sudoku puzzles

Re: Exotic patterns a resume

Postby David P Bird » Mon Oct 15, 2012 10:51 pm

ronk wrote:Using WIS to identify SIS puts things in reverse order for me. To avoid r1c3,r2c2<>5, these two cells must be members of the SIS, which in turn creates the need for 1234b1 WIS. To avoid r3c123<>1234, these three cells must be members of the SIS too.

Better IMO to leave b1 out of the picture and use b3 instead ... 6r1, 9r2, 578r5, 78r7, 14c5, 23c6, 12c8, 34c9, 5b3

Your MSLS is more economical than mine as it only has 16 cells/confined digits rather than 21 and therefore can be considered superior.

The discipline I'm using is to restrict the cover sets to either the full focus digit set or the full complementary set once any singles in the houses concerned are stripped out. This reduces the number of options to be tried in the search routine.

Hits can be found quite quickly for simple row/column multi-fish and vanilla SK loops, but can be awkward otherwise. In such cases I look for a truth balance using only the focus digit set which I currently find is quicker. If this is successful it's then easy to convert the cover sets used into the better of the two possible equivalent MSLS formats.

If a truth and link sets search method is used my guess is that more options might have to be tried before a hit is found, but then it would be likely that the MSLS would be reduced to its smallest size as you've achieved.

It would be an interesting exercise to see which approach would be easier to code / quicker to run in a computer solver.
David P Bird
2010 Supporter
 
Posts: 1039
Joined: 16 September 2008
Location: Middle England

Re: Exotic patterns a resume

Postby JC Van Hay » Tue Oct 16, 2012 9:30 am

ronk wrote:
JC Van Hay wrote: ... concerning Xsudo, I am keeping in mind :
1. There is no such a theorem saying that N SIS contain N truths, even if they do not overlap!
Incorrect, independent of Xsudo! If each candidate of N SIS is a member of only one SIS, and if each SIS candidate is covered by one or more of N WIS, there will be exactly N placements, one per SIS and one per WIS.
If it were true that any set of N non-overlapping SIS contain N truths, then any puzzle would have at least one solution !

A counter-example in number 2 : in "T-mode", right click on any eliminated candidate and click on "set candidate" in the pop-up menu -> an invalid puzzle will result where 19 non-overlapping SIS contain less than 19 truths.
ronk wrote:
JC Van Hay wrote: ... concerning Xsudo, I am keeping in mind :
4. A global rank 0 logic is only defined for a base of N non-overlapping SIS having at least one solution.
Also incorrect. The logic sets I posted above are each shown by Xsudo to have effective 0-rank. That the raw rank in the 1st and 3rd instances is also 0-rank is coincidence (I think).
I don't have a complete understanding of Xsudo as its outputs can be quite complex at first sight.
However, having played with it for some time, I can imagine that the core of it is a "DLX engine" computing all the solutions of all the combinations of 1,2,3, ... SIS.
If all the solutions of a particular combination lead to elimination(s), a minimal cover is looked for containing the base (except eventually for some candidates of the base common to 2 base sets) and the eliminated candidate(s).
The interpretation of the eliminations in terms of base and cover is however not that easy as it is based on ("overall") "rank N logic", only applicable when the base sets are not overlapping, and ("local") "rank N link" of each cover set (or link) to take into account overlapping base sets and/or overlapping cover sets.

Therefore, in the case of "loops", one should distinguish between "rank 0 logic" and "rank 0 link" :

    The logic in number 2 is that of "rank 0 logic" : a valid base of 19 non-overlapping SIS covered by 19 SIS -> the candidates in the cover ouside the base can be eliminated.
    The logic in number 1 and number 3 is that of "rank 0 link" due to the overlapping of base sets, even if all the cover sets are of rank 0. So, as a proof,

Code: Select all
In number 1 :

If r5c7<>2 ("clear candidate), then removing 4C7 gives 17 non-overlapping SIS covered by 17 SIS (-> rank 0 logic is applicable):

   [22,236] 52 Candidates,
   17 Truths = {123R5 1234R7 1234C4 123C7 3N123}
   17 Links = {1234r3 57n1 57n3 2n4 1n7 1b59 2b68 3b59 4b8}
   20 Eliminations --> r5c3<>578, r3c68<>2, r3c69<>3, r3c79<>4, r7c13<>8, r1c7<>46, r5c1<>58,
                       r3c8<>1, r4c5<>1, r7c3<>7, r8c6<>2, r9c5<>4

   Furthermore, r5c7=4 --> r5c7<>7

If r5c7=2 ("set candidate"), (--> r5c7<>7), then removing 13R5 and 13C4 gives 12 non-overlapping SIS covered by 12 SIS (-> rank 0 logic is applicable) :

   [23,226] 36 Candidates,
   12 Truths = {1234R7 24C4 134C7 3N123}
   12 Links = {1234r3 1n7 2n4 7n13 24b8 13b9}
   15 Eliminations --> r3c469<>3, r3c48<>1, r3c68<>2, r7c13<>8, r2c4<>13, r3c9<>4, r7c3<>7,
                       r8c6<>2, r9c5<>4

   Furthermore, r4c4=1, r6c4=3; r5c13=13 -->r4c5<>1, r5c1<>58, r5c3<>578

The common eliminated candidates can be removed.

In number 3 :

Here, fortunately, the overlapping can be removed by replacing the ANT(1234)r3c123 by the AHQ(6789)r3c46789. The logic is then the same as for a base of 23 non-overlapping SIS covered by 23 SIS (-> rank 0 logic is applicable).

   [22,237] 87 Candidates,
   23 Truths = {6789R3 1C12347 2C12347 3C12347 4C2347}
   23 Links = {1r48 2r48 3r69 4r9 1n7 2n4 3n46789 5n137 7n13 1234b1}
   19 Eliminations --> r5c3<>578, r3c68<>2, r3c69<>3, r7c13<>8, r5c1<>58, r1c7<>6, r3c8<>1,
                       r3c9<>4, r4c5<>1, r5c7<>7, r7c3<>7, r8c6<>2, r9c5<>4

   Furthermore, r357=123 --> r89c1=58 (r8c1<>12, r9c1<>3)

Final important note : that the number of cover sets is equal to the number of base sets does not imply that the rank of each link is 0 or that there is even one rank 0 link ! One has to prove it.

    Here is an example I didn't post in the lost forum (I think):
    000000052902000034060300987010008563006130879830007421008013706600240318000876205
    NoFish1 [44,101] 13 Candidates, Starfish
    5 Truths = {5R8 5C136 5B5}
    5 Links = {5r356 5b27}
    1 Elimination --> r3c5<>5

    And what about this one !
    000710854871540032000008701008107005000820007709654018085960473490075186007480529
    NoFish2 [49,86] 12 Candidates, Whale
    6 Truths = {3R8 3C36 3B458}
    5 Links = {3r145 3c2 3b1}
    1 Elimination --> r1c2<>3
JC Van Hay
 
Posts: 719
Joined: 22 May 2010

Re: Exotic patterns a resume

Postby ronk » Tue Oct 16, 2012 2:55 pm

JC Van Hay wrote:
ronk wrote:
JC Van Hay wrote: ... concerning Xsudo, I am keeping in mind :
1. There is no such a theorem saying that N SIS contain N truths, even if they do not overlap!
Incorrect, independent of Xsudo! If each candidate of N SIS is a member of only one SIS, and if each SIS candidate is covered by one or more of N WIS, there will be exactly N placements, one per SIS and one per WIS.
If it were true that any set of N non-overlapping SIS contain N truths, then any puzzle would have at least one solution !

A counter-example in number 2 : in "T-mode", right click on any eliminated candidate and click on "set candidate" in the pop-up menu -> an invalid puzzle will result where 19 non-overlapping SIS contain less than 19 truths.

I deal with valid puzzles (and valid pencilmarks) that have exactly one solution. A puzzle without a solution is invalid. A puzzle with multiple solutions is a sub-puzzle, also generally considered to be invalid.

JC Van Hay wrote:
ronk wrote:
JC Van Hay wrote: ... concerning Xsudo, I am keeping in mind :
4. A global rank 0 logic is only defined for a base of N non-overlapping SIS having at least one solution.
Also incorrect. The logic sets I posted above are each shown by Xsudo to have effective 0-rank. That the raw rank in the 1st and 3rd instances is also 0-rank is coincidence (I think).
The interpretation of the eliminations in terms of base and cover is however not that easy as it is based on ("overall") "rank N logic", only applicable when the base sets are not overlapping, and ("local") "rank N link" of each cover set (or link) to take into account overlapping base sets and/or overlapping cover sets.

Therefore, in the case of "loops", one should distinguish between "rank 0 logic" and "rank 0 link" :

The logic in number 2 is that of "rank 0 logic" : a valid base of 19 non-overlapping SIS covered by 19 SIS -> the candidates in the cover ouside the base can be eliminated.[/list][list]The logic in number 1 and number 3 is that of "rank 0 link" due to the overlapping of base sets, even if all the cover sets are of rank 0.

When all the links are 0-rank, I see no reason to distinguish between cases of over-lapping and non-overlapping base sets. Are the elimination rules different? Not as far as I know.

JC Van Hay wrote:In number 3 :

Here, fortunately, the overlapping can be removed by replacing the ANT(1234)r3c123 by the AHQ(6789)r3c46789. The logic is then the same as for a base of 23 non-overlapping SIS covered by 23 SIS (-> rank 0 logic is applicable).

The base set overlap in "number 1" can be removed by replacing the 1234C7 A*HS with the "complementary" 34689N7 A*LS. :)

JC Van Hay wrote:Final important note : that the number of cover sets is equal to the number of base sets does not imply that the rank of each link is 0 or that there is even one rank 0 link ! One has to prove it.

Agreed, that's why ...
earlier I wrote:That the raw rank in the 1st and 3rd instances is also 0-rank is coincidence (I think).

Lastly, because none of the links are 0-rank, your two NoFish examples are irrelevant IMO.
Last edited by ronk on Tue Oct 16, 2012 3:24 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Exotic patterns a resume

Postby champagne » Tue Oct 16, 2012 3:22 pm

ronk wrote:champagne, instead of arguing to redefine the pattern used by Steve Kurzhals when he discovered the hidden-pair-loop, your time would be better spent adding box covers to your program. Then most, if not all, of the puzzles in the "04c multi_fish rank 0.txt" file which show "; ; ;X" fish styles would read ";R;C;X". For example ...



Well I have my own priorities and covering all equivalents ways to make eliminations through a "rank 0 logic" is by far not at the top of the list.

Happily, my project is an open source project designed to be implemented by several contributors.

If anybody wants to go in that direction, he is welcome as contributor.
champagne
2017 Supporter
 
Posts: 6454
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby champagne » Tue Oct 16, 2012 3:28 pm

David P Bird wrote:champagne, the collection of cover sets used has similarities with a single digit Franken Fish. As there are no columns covered in stack 1, any if its boxes can be added to cover the (1234) digit set. This may be of help for a redesign of your Multi-fish algorithm.


Thanks a lot David, but in the near future, out of my search of new "potential hardest" in the 25 clues area (and still with less clues), I intend to work more on the the solving process of already seen patterns.

But I follow with interest the discussions taking place here.

I'll restart the search of other multi fish patterns after I get an acceptable situation on the solving side with the new process
champagne
2017 Supporter
 
Posts: 6454
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby ronk » Tue Oct 16, 2012 3:52 pm

champagne wrote:Happily, my project is an open source project designed to be implemented by several contributors.

If anybody wants to go in that direction, he is welcome as contributor.

Considering how difficult it is for me to understand many of your posts, I fear understanding your code would be nigh impossible. Perhaps if I learned French first. :)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Exotic patterns a resume

Postby champagne » Fri Oct 19, 2012 2:08 pm

JC Van Hay wrote:The puzzle : .........1....72...7..84.6...8....93.6..4..7.93....6...9.73..8...59....2.........
contains

+------------------------+--------------------+-------------------------+
[29,188] 52 Candidates, Loop All Cells

The simplest "complementary" multi-fish :

[29,188] 34 Candidates, Loop "2 Rows + 2 Columns"

While the "complementary" Loop All Rows is :

[29,188] 46 Candidates, Loop All Rows

As to the "complementary" Loop All Columns,


All these rank 0 logics (after ronk's adjustment for the columns based one) are very similar to what can be found with a typical SK loop.

my solver does not look for the all cells one, but it is the signature for the "V" loop.
The mixed (base 2 rows + 2 columns) logic has been easily found by my solver, The 2 others have a box cover not yet coded in it

This again push to consider the "V loop" logic as a true super setting logic for the SK loop
champagne
2017 Supporter
 
Posts: 6454
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby ronk » Fri Oct 19, 2012 7:00 pm

champagne wrote:
JC Van Hay wrote:The puzzle : .........1....72...7..84.6...8....93.6..4..7.93....6...9.73..8...59....2.........
contains

All these rank 0 logics (after ronk's adjustment for the columns based one) are very similar to what can be found with a typical SK loop.
...
This again push to consider the "V loop" logic as a true super setting logic for the SK loop

This looks like the French puzzle again which, as I've said before, does not contain a Steve Kurzhals' sk-loop AFAICS.

As to "super-setting", there are many techniques which subsume older techniques, but we generally don't rename the latter.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Exotic patterns a resume

Postby champagne » Fri Oct 19, 2012 10:08 pm

ronk wrote:This looks like the French puzzle again which, as I've said before, does not contain a Steve Kurzhals' sk-loop AFAICS.

As to "super-setting", there are many techniques which subsume older techniques, but we generally don't rename the latter.


amazing comment again.

for sure, it is the example of a puzzle having the "V loop" and not (with your specification) the SK loop.

All puzzles having the SK loop have the "V loop". This is not exactly the scope of a sub.... but of a super...

I have no example that a super ... did not receive a name but you surely have one.

I am convinced there are millions of puzzles having a "V loop" and not the "SK loop" as you describe it
champagne
2017 Supporter
 
Posts: 6454
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby David P Bird » Sat Oct 20, 2012 8:36 am

This argument is ridiculous!

The term 'v loop' has yet to be formally defined.

Steve Kurzahls discovered a continuous chain of AALS where the terms were linked with two digits. He did not define it as a pattern. It could be described either as an AAHS loop (as he did) or as the complementary AANS loop. Whichever is used there are three possible divisions of the truths between alternating terms, which often can be reduced to one or two.

If we wish to continue to honour Steve's contribution we should call any AALS loop an SK loop, otherwise we should just call them AALS Loops. Any other course is unnecessarily confusing.

Anyone so inclined can then identify the sub-types that have been discovered since the original debate.
David P Bird
2010 Supporter
 
Posts: 1039
Joined: 16 September 2008
Location: Middle England

Re: Exotic patterns a resume

Postby champagne » Sat Oct 20, 2012 9:23 am

David P Bird wrote:This argument is ridiculous!

The term 'v loop' has yet to be formally defined.


it is in the second post with the proof still named "SK loop extended definition" in the third one.
That post will be updated to-day.

But for sure, without the pressure made by ronk, I would not have created a different name and I still consider this as a direct inheritance of Steve Kurzhals findings.
champagne
2017 Supporter
 
Posts: 6454
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby David P Bird » Sun Oct 21, 2012 7:36 am

champagne it's difficult to answer you in detail as we have so many differences in language, logical processes, and notation styles.

All I will say is that your 'v loops' appear to be completely contained in AALS loops and so I don't believe a new term is required as it just seems that you've reinvented an existing wheel. Your definition and proof are difficult to follow though. To give one example out of many, you don't make it clear what a1 and a2 describe and so the reader must guess.

As I have shown, these loops are a particular type of Multi-Sector Locked Set. They deserve their own name because expressing them as loops gives us extra inferences about the division of truths between the alternating Boolean nodes.

However we don't need completely different terms to describe the differences we've been discussing when they are all varieties of AALS loops. To justify a new name I think you must show how v loops differ from AALS loops.

I'll leave it there as I don't intend to waste any more time on this subject.

David
David P Bird
2010 Supporter
 
Posts: 1039
Joined: 16 September 2008
Location: Middle England

Re: Exotic patterns a resume

Postby champagne » Sun Oct 21, 2012 9:28 am

well David, some comments to your post


it just seems that you've reinvented an existing wheel.

The "V" loop process has been first described 5 years ago

Post by champagne » Mon Oct 29, 2007 9:53 am in the full tagging thread

full tagging

I can have missed a prior similar definition, your link will be welcome.

All I will say is that your 'v loops' appear to be completely contained in AALS loops

Do you have a link to the description of that logic. Unless I am wrong, the logic I use is only valid for AAHS/AALS chains of 2 cells 4 digits.
BTW, this is the logic included in my old solver

Your definition and proof are difficult to follow though. To give one example out of many, you don't make it clear what a1 and a2 describe and so the reader must guess.

Thanks for your remark. It's always difficult to have a clear wording, especially for a foreigner. I'll work on improvement of the text.



To justify a new name I think you must show how v loops differ from AALS loops.

I don't care about the name except that changing again the name would increase the confusion.
BTW I would not be disturbed if anybody continues to call that a SK loop. I'll use the qualifier "V loop" to avoid endless discussions with ronk.

Regarding the qualifier "AALS loop", I have first to learn what it means before making any comment (see above my request for the appropriate link). As for the JExocet, the "V loop" has the property to be easy to detect by a player.

May be the AALS loop is a super setting pattern of the "V loop"??

PS: I have no comment about the Multi-Sector Locked Set, it is a logic I never studied and I am waiting for examples of a solving power specific to that logic to put it in the to do list.
Last edited by champagne on Sun Oct 21, 2012 9:50 am, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 6454
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby champagne » Sun Oct 21, 2012 9:49 am

Some results for the process of exotic patterns using the code as it is currently in the
google skmpp project

My target remains to find acceptable paths a player has a chance to reproduce
(a player usually can find a better path than the solver) for "potential hardest puzzles.

To make it short, the current code is derived from serate's set of rules with the following deviations :

. no nested level
. Dynamic plus has an extended step adding UR's, kites and sky scrappers
(should be later extended to triplet and sworfish)
. Exotic patterns are considered


Regarding exotic patterns, the strategy, on top of direct eliminations is the following :

"V loop"

The program tries first to eliminate the 2 main belts (stops if it does not work)
The strategy described by JC Van Hay in that thread is then applied. The program collects all "bi locations" (usually 4) and combines them in up to 16 scenario.
note: JC Van Hay used the expression "bi location" for pairs of digits offering only one solution in each AALS/AAHS of one unit of the "V loop".

Exocet

The program first looks for "abi loop" to reduce the number of pairs solution of the base.
Then each scenario or sub scenario is analysed to reduce again the count.
Assignments and eliminations common to residual scenarios are applied.

In both cases, identified pairs eliminations and specific properties are turned to weak links to be included in the standard process.

Multi_fish

So far, I have no specific strategy out of the direct eliminations

the results I got are summarised here

Code: Select all
        number unsolved   
m_fish   2177      81   3.72%
exocet  31528    2712   8.60%
V loop   2013       9   0.45%


Nearly all puzzles having the "V loop" are solved, which confirms the JC Van Hay experience.
Surprise for me, puzzles with a multi_fish and nothing else offer a poor resistance
Exocet pattern appear to be resisting pretty well to that set of rules. The famous hardest as Golden Nugget, Silver Plate are among the unsolved puzzles.
champagne
2017 Supporter
 
Posts: 6454
Joined: 02 August 2007
Location: France Brittany

Re: Exotic patterns a resume

Postby Leren » Sun Oct 21, 2012 12:28 pm

Champagne,

For puzzles like Golden Nugget you can use an Almost Multifish approach for a quick solution.

For example with Golden Nugget, after the usual Exocet eliminations I find the following Almost Multifish:

Multifish 5.1: 16 Truths = { 1R1347 2R1347 4R1347 7R1347 } 17 Links = { 1c24 2c14 4c26 7c16 1n357 3n89 4n78 7n79 }

This leads to the following potential eliminations: r1c3 <> 56, r1c5 <> 6, r2c1 <> 27, r2c2 <> 4, r2c4 <> 2, r3c8 <> 6, r4c7<> 35,
r5c4 <>1, r6c7<> 7, r7c7 <> 3, r8c1 <> 7, r8c4<> 1, r8c6<> 4, r9c2 <> 1.

Because the number of links exceeds the number of truths by 1 then exactly 1 of these 17 eliminations is false ( ie the relevent candidate is true)
Scenario testing is then carried out using this information (ie setting in turn all but one to false and the remaining one to true) plus the possible Exocet Base and Target cell values.

The only test that does not produce an error is when r4c7 = 5, r1c7 = 2, r2c7 = 4, r4c8 = 4, r7c9 = 2. The other 16 eliminations could also be made, although in this case it is not necessary as the
puzzle solves in singles after the 5 assignments.

Most puzzles having an exocet will solve in this manner. For puzzles without an Exocet I use bi-value cell scenarios in lieu of Exocet cell values.

I've also implemented the JC Van Hay method for SK loop puzzles. It applies to all the ones I've tested in your file so far.

Leren
Leren
 
Posts: 3310
Joined: 03 June 2012

PreviousNext

Return to Advanced solving techniques