ALS chains with overlap/cannibalism

Advanced methods and approaches for solving Sudoku puzzles

Postby champagne » Wed Feb 18, 2009 3:20 am

ronk wrote:What is the origin of this puzzle:?:


This is an old puzzle published on the wayne gould site and imported on a French forum in November 2005.
I published that loop end of summer 2007, when the solver became efficient using AC/AHS.

I have seen recently a similar loop in another puzzle (likely in the last lots form coloin), but I can't remember which one.



ronk wrote:Wow! That's an SK-loop variant (this one with 13 eliminations) I've not seen before.
However, in order that the nice loop reflect the 6 eliminations in b1, b3 and b7,
I would prefer triply-linking AALSs as follows: . . .



I agree that linked ALS AALS ... can produce very nice things.
For many reasons, (basically redundancy for easy cases and lack of efficient process for other cases)I do not use that method.

I just appreciate when nice examples are produced;

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby ronk » Wed Feb 18, 2009 4:01 am

champagne wrote:
ronk wrote:What is the origin of this puzzle:?:

This is an old puzzle published on the wayne gould site and imported on a French forum in November 2005.
I published that loop end of summer 2007, when the solver became efficient using AC/AHS.

Do you have any links:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Wed Feb 18, 2009 6:07 am

ronk wrote:
champagne wrote:
ronk wrote:What is the origin of this puzzle:?:

This is an old puzzle published on the wayne gould site and imported on a French forum in November 2005.
I published that loop end of summer 2007, when the solver became efficient using AC/AHS.

Do you have any links:?:


Certainly not so easy to link to the figaro forum, but I posted that solution in that thread

http://forum.enjoysudoku.com/viewtopic.php?t=5628&postdays=0&postorder=asc&start=15

In October 2007, likely one month later than on the figaro forum if I am right. I can dig in the forum, but I don't think it is worth the time to be more accurate.

I don't have the link to the Gould site, It was not given on the figaro forum.

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby tarek » Wed Feb 18, 2009 6:42 am

champagne wrote:
ronk wrote:What is the origin of this puzzle:?:

This is an old puzzle published on the wayne gould site and imported on a French forum in November 2005.
.
.
.
In October 2007, likely one month later than on the figaro forum if I am right. I can dig in the forum, but I don't think it is worth the time to be more accurate.
.
.
.
I don't have the link to the Gould site, It was not given on the figaro forum.

I found the mystery puzzle.
http://www.setbb.com/phpbb/viewtopic.php?mforum=sudoku&t=359&postdays=0&postorder=asc&start=21
ronk might find it interesting to know that the exact answer to the mystery is in the last post of that thread:D
Code: Select all
6...4...3.1.....7...5...8.....5.2...3...9...2...1.3.....8...9...7.....5.2...3...4
6 . .|. 4 .|. . 3
. 1 .|. . .|. 7 .
. . 5|. . .|8 . .
-----+-----+-----
. . .|5 . 2|. . .
3 . .|. 9 .|. . 2
. . .|1 . 3|. . .
-----+-----+-----
. . 8|. . .|9 . .
. 7 .|. . .|. 5 .
2 . .|. 3 .|. . 4


also see: http://www.dailysudoku.com/sudoku/forums/viewtopic.php?t=219&sid=dae2c2133114ee9513a6a37124374e7c & http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?p=1180&highlight=#1180

dukuso confesses that he has collected puzzles from the net to include in his hadest lists at the time.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby ronk » Wed Feb 18, 2009 7:40 am

tarek wrote:
champagne wrote:
ronk wrote:What is the origin of this puzzle:?:

This is an old puzzle published on the wayne gould site and imported on a French forum in November 2005.
...
In October 2007, likely one month later than on the figaro forum if I am right. I can dig in the forum, but I don't think it is worth the time to be more accurate.

I found the mystery puzzle.
http://www.setbb.com/phpbb/viewtopic.php?mforum=sudoku&t=359&postdays=0&postorder=asc&start=21
ronk might find it interesting to know that the exact answer to the mystery is in the last post of that thread:D [code]

champagne and tarek, thanks for the searches. My fgrep effort had no chance with that extra clue in r6c6. The fact that I've had prior involvement with this puzzle is simultaneously embarrassing and funny.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby JPF » Wed Feb 18, 2009 9:03 am

See also this puzzle posted here:

Code: Select all
 1 . . | . 2 . | . . 3
 . 4 . | . . . | . 5 .
 . . 6 | . . . | 7 . .
-------+-------+-------
 . . . | 5 . 7 | . . .
 8 . . | . 6 . | . . 1
 . . . | 8 . 9 | . . .
-------+-------+-------
 . . 7 | . . . | 6 . .
 . 5 . | . . . | . 4 .
 3 . . | . 4 . | . . 8


JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby champagne » Wed Feb 18, 2009 4:12 pm

PIsaacson wrote:
Thanks to Champagne's example, light bulbs are starting to form...

I think Champagne has been trying to lead me to the conclusion that I have to treat ALSs/AHSs as pairs, and then follow the implications of their interactions. If an ALS converts to a LS, then the complement AHS should also convert to a hidden LS. If I'm right, then ALS loops can trigger more eliminations than what I am currently generating -- sorry for the mental meandering but at least that's something I can easily code/test.

So, at any point in an ALS chain, the paired AHS is likewise collapsing into a hidden LS and the implication chain can take alternative paths if the hidden LS can be RCD linked to another ALS? This is exactly what I have been looking for!!! I have GOT to try this!!!

Cheers,
Paul


Hi,

I think you got my point. My first code has been to apply ALS interactions.

This does not fit with the AIC logic, so it appeared to be a very limited impact in the overall process

Using conjugates ALS/AHS:

1) You achieve the same resuts as linking 2 ALS
2) You can produce AIC's mixing the vicinity properties of the conjugated ALS/AHS and the rest of your AIC logic.

The way my solver has been implemented, if I except the addition of Allan Barker model, is to use new "vicinity rules" to create new tags linked to existing ones or to extend the content of existing tag.

Efficiency is in the choice of the new stuff and I am still working on optimizing my own choices.

What is for sure is that just adding the rule I indicated, you should solve all puzzles except the list of true "Hardest" ones.

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby PIsaacson » Wed Feb 18, 2009 5:45 pm

Champagne,

I finally read your full-tagging pages, especially "Level 2 adding ALS ACs and Choices". So thanks tremedously for leading me to the dml155 puzzle and full-tagging! Yikes!!! More coding on my to-do list...

Here are my preliminary findings on using the interactions of ALS/AHS within continuous/looping ALS chains:

There are two types of eliminations produced by an ALS loop:

Type 1 - the standard RCD elimination within peers of both the left and right hand ALSs for each leg of the loop.
Type 2 - those generated as a result of the interaction between the ALS and its complementary AHS.

My current algorithm for generating type 2 eliminations:

1) For each ALS in the loop, generate a set of elimination candidates from the ALS candidates, less the in/out RCDs.
2) All cells that are peers of the ALS can be reduced by the elimination set from step (1). This includes all the AHS complementary cells and can span 2 sectors for ALSs that are aligned on a row/column and contained within a box.

This has increased the number of eliminations in loops that contain ALSs > size 2. A bi-value cell can only be placed in a loop using 2 different in/out RCDs, which results in an empty type 2 elimination set. This confines them to type 1 eliminations, which agrees with the XY-ring/loop definition and makes me happy!

I'm haven't excluded cannibalism, but I haven't vigorously tested it yet, so I'm not sure whether or not it's allowable.

This was probably obvious to everyone but me, and worst of all, previously discussed and documented! Ouch!!! Mea culpa... My bad...

More later as statistics report in,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby champagne » Wed Feb 18, 2009 6:14 pm

PIsaacson wrote:
There are two types of eliminations produced by an ALS loop: ....
1) For each ALS in the loop, generate a set of elimination candidates from the ALS candidates, less the in/out RCDs. .....
2) All cells that are peers of the ALS can be reduced by the elimination Paul


I am very busy on another topic, so I did not read carefully that thread and my reaction can be ignored.

For me, once the conjugated ALS;AC/AHS have been entered, I have nothing special in the processing.

The new stuff enters indiferently loops of "clearing chains" (I should likely say nrzt chains).

The only constraint is to give back in the print the origin of the strong/weak links contributing to the AIC; AIC net; nrzt chain ...

So I have the feeling that you can still do it "simpler" but i can be wrong.

champagne
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Postby PIsaacson » Sat Feb 21, 2009 5:10 pm

New insight into why my ALS engine currently cannot duplicate XY-chains exactly, but theoretically should.

In reviewing my code and looking at various XY chains produced by my XY engine vs my ALS engine, it finally hit me over the head, duh!!! Without the Allan Barker modification to allow dual-linked ALSs to participate in chains, the current ALS RCD adjacency rules do not allow for naked pairs to exist as "extentions" to an incoming RCD. I have previously stated that the Allan Barker RCD extension is valid, but expensive in terms of increasing run times beyond what I thought was reasonable considering its slight increase in producing eliminations. I need to rethink this since it's the only way to truly allow the ALS engine to exactly duplicate XY-chains. What I need to allow in the ALS engine is:

ALS1.{...x} -x- ALS2.{xy} -xy- ALS3.{xy} -x- The RCD x is "extended" by the xy naked pair
ALS1.{...y} -y- ALS2.{xy} -xy- ALS3.{xy} -y- The RCD y is "entended" by the xy naked pair

This was covered in the original ALS chaining thread on the Eureka forum http://www.sudoku.org.uk/SudokuThread.asp?fid=4&sid=9448
and replicated here http://forum.enjoysudoku.com/viewtopic.php?t=6443 with the 7th graphic example.

This conflicts with what I had reported previously and I'm trying to reconcile my prior findings with the concept of "extension" of an RCD via naked pairs. In grouped nice-loops, there are many ways to allow an RCD constraint to "extend" and link to another ALS. To what extent should we allow this? I can live with a naked pair since that's just two dual-linked bi-value ALS cells, but should we also allow other b/b links or ERs/hinges/almost-things to exist in ALS chains? I think not, but I'm willing to be convinced otherwise -- especially if you can come up with other clever ALS/AHS types of linkages.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby ronk » Sat Feb 21, 2009 6:35 pm

PIsaacson wrote:In grouped nice-loops, there are many ways to allow an RCD constraint to "extend" and link to another ALS. To what extent should we allow this? I can live with a naked pair since that's just two dual-linked bi-value ALS cells, but should we also allow other b/b links or ERs/hinges/almost-things to exist in ALS chains? I think not ...

I most-heartedly agree. With the elimination cell(s) being the only exception, an ALS chain or ALS loop should be 100% ALS, where ALS includes the simple bivalued cell.

Allan Barker wrote:... but I'm willing to be convinced otherwise -- especially if you can come up with other clever ALS/AHS types of linkages.

Since every AHS has an ALS complement this allowance seems tempting, but what's wrong with the accurate ALS/AHS chain term?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Sun Feb 22, 2009 4:31 pm

Hi Ron,

I'm in the midst of syncing the ALS engine with my nrczt engine and my Nice-Loops/AIC engine. In doing so, I ran across a really interesting chunk of code that I had written for nrczt group extensions involving what I commented in the code as "Almost Fish". It was nothing more than using my then current ALS engine to walk the RN/CN/BN spaces looking for single digit ALSs in those respective spaces. This is a fairly well documented feature and I took advantage of it to build weak-linked relationships when a left-linking candidate (read as incoming RCD) caused the fishy ALS to convert to a fish-n LS. The resulting eliminations are all the weak-linked right-hand side outgoing RCDs.

So, does this qualify as something that "looks/feels" like it belongs in the ALS/AHS chaining school of inquiry? I'm giving it the duck test. If it looks like a duck, walks like a duck, quacks like a duck, then chances are it's a duck. These fishy ALSs are quacking at me and I'm having a hard time ignoring them...

Cheers,
Paul

P.S. I agree - they should henceforth be called ALS/AHS chains or loops. I like the continuous/discontinuous qualifiers in nice loops, but it sounds strange to state "This is a continuous ALS/AHS chain" for a loop, just like it sounds ridiculous to assert "This is a discontinuous Nice Loop" for a chain.
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby DonM » Wed Feb 25, 2009 5:16 am

Paul:

I came across my 'Overlapping cells' manilla envelope and although they might not be of much help, these are some other links (these don't come up in a Google search):

note ronk's first post:
http://forum.enjoysudoku.com/viewtopic.php?t=5580&highlight=form+als

(The following doesn't even come up in a forum search using the exact title of the article):
http://forum.enjoysudoku.com/viewtopic.php?t=5614
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby PIsaacson » Wed Feb 25, 2009 6:07 pm

Don,

Thanks for the additional links. It helps to read what has already been discovered about this. A preliminary skimming confirmed that others had already discovered that overlap is permitted, as long as the RCDs are not participants in the overlapping cells.

What has been interesting is finding out that overlapping ALSs are far more common that I think was previously believed. I'm finding that about a third of all possible ALS chains involve overlap, once you allow for it to occur. That's a pretty high percentage to not take seriously. Unfortunately, it's something that is more interesting from a programming POV since they are a bear to find manually. I've studied hundreds of ALS chains involving overlap and cannibalism, and I highly doubt I could find one on my own, even if you told me what rows/cols/boxes to search.

Nonetheless, they are fascinating and they obviously appeal to me for some inexplicable reason. BTW, my wife thinks sudoku is an addiction rather than a hobby...

Cheers,
Paul
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby tarek » Wed Feb 25, 2009 8:05 pm

OFF TOPIC
PIsaacson wrote:BTW, my wife thinks sudoku is an addiction rather than a hobby...


A Sudokoic wrote:A new netbook can buy you some peace for some time
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

PreviousNext

Return to Advanced solving techniques