The New Sudoku Players' Forum

by **Mike Barker** » Fri Mar 14, 2008 2:41 pm

Ron, I was thinking about trying to limit the number of ALS by coming up with a restricted definition for those used in grouped nice loops. For example, can we get by with ALS which limit the restricted common being in a box, boxrow, or boxcol? If we can reduce their numbers ALS will become even more attractive.

Strmckr, I only meant that it was more complicated than I would find on my own. I never doubted that you had found the elimination by hand using your yielding chains. Because of your posts, I'm getting a better understand of what you are doing. Thanks.

by **StrmCkr** » Fri Mar 14, 2008 2:51 pm

removed

by **Draco** » Sat Mar 15, 2008 7:25 am

I've been lurking here for many weeks whilst working on my own solver program. The board has been a great source of test puzzles. I guess I am about to find out just how good my toy is. Apologies if my terminology is not up to snuff yet.

Starting from Mike's puzzle code (all results from my solver), I have a solution that uses 2 forcing chains with a couple of simple steps in between. It looks much nicer (and simpler) with the color/graphics on my screen, but here's a shot at translating that.

First forcing chain in R1C1, R1C8 on 2's. The chain relies on bivalue squares as well as bivalue color pairs (does that make it a net?). The color chains needed are:

Blue/Red color chain of 2's in R1/3C1/2 (B/R) & R1/3C9/8 (R/B)
Blue/Red color chain of 9's in R5C8/9 (B/R) & R2C8/9 (R/B)

Code: Select all: First path on forcing chain: r1c1=2 > (r2c1=1 & r3c8=2) > r1c9=1 r3c8(2) > r5c8=9 r5c8(9) + r1c9(1) > r2c8=8 Second path: r1c9=2 > r1c7 = 4

This lets us make the exclusions r1c7 <> 8 & r1c8 <> 4, 7, 9, delivering a hidden single R1C7, and leading to locked 9's in box 3 (knocking out the 9's in box 2):

Code: Select all: 1238 5 1378 | 13789 3789 1379 |+47 6 12 168 1678 4 | 15678-9 2 1567-9| 3 18*9 178*9 9 2678 1378 | 13678 4 1367 | 78 128 5 ---------------+--------------------+--------------- 248 9 6 | 1237 37 1237 | 5 248 2478 123 127 137 | 4 5 8 | 67 29 2679 248 2478 5 | 2679 79 2679 | 1 3 2478 ---------------+--------------------+--------------- 7 148 189 | 589 6 459 | 2 1458 3 4568 468 2 | 37 1 37 | 9 458 468 456 3 189 | 2589 89 2459 |-468 7 1468

One more chain finishes the job. This time it's off the bivalue in r5c8 (those color chains on 2's and 9's are going to play a role here too):

Code: Select all: First path: r5c8=2 > r2c8=9 > r5c9=9 > r5c7=6 > r3c8<>2 > r1c9=2 > r3c2=2 Second path: r5c8=9 > r2c9=9 > r3c7=7

These two chains knock the 7's out of r3c2 and r5c7. From this point the puzzle reduces to singles (here it is after the second chain is applied):

Code: Select all: 1238 5 1378 | 13789 3789 1379 | 4 6 12 168 1678 4 | 15678 2 1567 | 3 189 1789 9 268 1378 | 13678 4 1367 | 78 128 5 ---------------+-----------------+------------- 248 9 6 | 1237 37 1237 | 5 248 2478 123 127 137 | 4 5 8 | 6 29 2679 248 2478 5 | 2679 79 2679 | 1 3 2478 ---------------+-----------------+------------- 7 148 189 | 589 6 459 | 2 1458 3 4568 468 2 | 37 1 37 | 9 458 468 456 3 189 | 2589 89 2459 | 68 7 1468

Whew... hope I caught the typos and that this makes sense to someone other than me. I had no idea how much time it would take me to create and proof this post. Makes me appreciate all the posts I've been reading all the more

.

Cheers - Draco

[edit] : Hmm... this looks a lot like Steve R's solution posted on 3/11.

by **champagne** » Sat Mar 15, 2008 9:23 am

Hi Mike,

May be the following extract of my solver proposal is good for you

I skip the start to come here

Code: Select all: 12a3E8 5 1378 |13789 3n7Å8o9 1379 |4b78 6 12A4B79í 16Á8 1678 4 |15c6789 2 15C679 |3 189G 1789 9 2A6Z78 13U78 |13678 4 1367 |7Î8 12a8 5 -------------------------------------------------------------------- 24v8Æ 9 6 |1d237 3N7n 1D237 |5 24y8Ë 247â8 1Q23e 127 13E7Ä |4 5 8 |6f7F 2G9g 26F79G 248 24X7ã8ê 5 |26h79 79 26H79 |1 3 24v78Æ -------------------------------------------------------------------- 7 1r48 189m |58Ì9 6 4p59 |2 1k45j8 3 45j68 46Á8 2 |3i7I 1 3I7i |9 45J8 46à8 45J6à8 3 1k89M |2l589 8O9o 2L4P59 |4B6F8é 7 1K468

two key ALS/AHS/AC structures:

r4c456 giving 2r4c46 = 7r4c456 and the chain 2r6c46 = 7r6c456 = 7r4c456 = 2r4c46 = 2r4c189 = 7r4c9
r5c789 giving 2r5c89 = 7r5c79

now

#2r6c9 []2r6c9 - 2r6c46 = 7r4c9 - 7r5c79.s = 2r5c89.S - 2r6c9

and the chain of strong links 7r6c2 = 7r5c23 = 7r5c79 = 2r5c89 = 2r4c89 => 7r6c2==2r4c89

two kraken blossoms based on r9c7

Code: Select all: #8r1c1 []4r9c7==4r1c9 - 2r1c9 = 2r1c1 - 8r1c1 []6r9c7==7r5c7.F - 7r5c23 = 7r6c2 - 8r6c2 = 8r46c1 - 8r1c1 []8r9c7 - 8r9c5 = 8r1c5 - 8r1c1 #2r4c1 []4r9c7==4r1c9.B - 2r1c9 = 2r1c1 - 2r4c1 []6r9c7==7r5c7.F - 7r5c23 = 2r4c89 - 2r4c1 []8r9c7 - 8r9c5 = 9r9c5 - 9r6c5 = 7r6c5 - 7r4c456 = 2r4c46 - 2r4c1

then thru ALS/AC r15c1=123 strong link 1r2c1 = 2r6c1

[]1r2c89 - 1r2c1 = 2r6c1 - 2r1c1 = 1r3c8 - 1r2c89

->LS2 digits 12 cells 38 box 3

1 r1c7=4

by **ronk** » Sat Mar 15, 2008 10:40 am

Mike Barker wrote:I was thinking about trying to limit the number of ALS by coming up with a restricted definition for those used in grouped nice loops. For example, can we get by with ALS which limit the restricted common being in a box, boxrow, or boxcol?

Ah, maybe I see. If you look at it in constraint set terms -- like fish with base\cover constraint sets -- with the base containing all the ALS cells and the cover containing all the restricted common candidates, can any of the following be eliminated?

box\box
box\line
line\box
line\same_line
line\intersecting_line

Off the top of my head, I don't know.

by **champagne** » Sat Mar 15, 2008 10:59 am

Mike Barker wrote:

I was thinking about trying to limit the number of ALS by coming up with a restricted definition for those used in grouped nice loops. For example, can we get by with ALS which limit the restricted common being in a box, boxrow, or boxcol?

I red Ronk answer; I can bring some experience that can be applied here.

Very often, in such middle class puzzles, you have a possible solution with the following limitations:

ALS/AHS two digits in excess of the number of cells,
Choices limited to ternary choices.

Here combinng the two possibilities, you have among others the solution I proposed.

Moreover, in the class ALS/AHS, the best performing are those with two cells (one bi value included), and more selective, especially when one digit is a single candidates connected to others thru bivalues

by **ronk** » Sat Mar 15, 2008 11:26 am

champagne wrote:Very often [...] you have a possible solution with the following limitations:

ALS/AHS two digits in excess of the number of cells,
Choices limited to ternary choices.

By "limited to ternary", do you mean limit ALS size to three candidates in two cells ... and limit AHS size to two candidates in three cells?

by **champagne** » Sat Mar 15, 2008 11:40 am

Ronk wrote

By "limited to ternary", do you mean limit ALS size to three candidates in two cells ... and limit AHS size to two candidates in three cells?

Sorry Ronk, I thought my post was clear. I use two quite different limitation to stay withiin what can be achived without computer help

AHS/ALS limited to 2 free digits. With two free digit, an ALS is an AHS and vice versa.

Normally, they are seen with a small number of cells; two or three, but the complementary AHS/ALS can have more.

The second limitation refers to "kraken blossoms". I am not using more than three branches which means:

cells of thre candidates,
three candidates or groups of the same digit in one unit.

In the posted solution, we have two kraken bloosoms starting from R9c7, a cell of three digits and we use three ALS/AHS groups

r4c456 complemantary r4c189; r6c456
r5c789 complementary r5c123;r4c79r6c9

and later on

r15c1 complementary r23489c1

by **daj95376** » Sat Mar 15, 2008 11:41 am

Mike Barker wrote:As far as Danny's Kraken Swordfish, I'm biased, but I like anything Kraken.

Hindsight: The Kraken Swordfish is more than just a novelty.

1) The Kraken Swordfish reduces [r3c8] to a bivalue cell through the elimination [r3c8]<>8.

2) Candidates 1 & 3 are locked in [r5c123].

3) Candidates 6 & 9 are locked in [r5c789].

4) This forces one of candidates 2 & 7 to be in [r5c123], and the other to be in [r5c789].

5) Assuming [r5c8]=2 forces [r3c8]=1, and its network forces the contradiction [r5c7]=7.

Step (5) doesn't happen as long as [r3c8]=128.

by **Mike Barker** » Sat Mar 15, 2008 9:47 pm

Draco, welcome. Your forcing chains are fine except I would have included r5c1=3 as a step in the first chain. Your first elimination is a network, but the second can also be seen as a Nice Loop or an Alternating Inference Chain (AIC) . The idea in these are to use the structure of the puzzle (strong links and bivalue cells in the simplest case) to help find eliminations. For this elimination all that is needed are strong links (rows, columns, or boxes with only two occurances of a digit), for example "9" occurs twice in column 9. Forcing chains make implicit use of these, while nice loops and AICs use them explicitly. Without going into much detail (if you are interested I'd be happy to), your second elimination can also be seen as:

Code: Select all: r5c7=6=r5c9=9=r2c9=7=r3c7-7-r5c7

which reads if r5c7<>6 then r5c9=6, r2c9=9, r3c7=7, r5c7<>7. At this point, probably the easiest perspective is to say if r5c7=6 then r5c7<>7, thus r5c7<>7. (Actually nice loops and AICs usually use the reversible nature of these chains to estabilish the elimination, but as Danny has pointed out this is a nice simple way to look at it). Anyway, hope this alternative way of looking at things provides some food for thought, otherwise, nice first solution on the forum.

Champagne, thanks for the solution. I guess the biggest idea I'd take away is the vicinity analysis which establishes, for example, 2r4c46=7r4c456. In looking at what is going on, the conjugate links you are creating result because of ALS which are also AHS (an idea David Bird floated a while back). This means that two of the numbers (in a three cell ALS) must occur in the cells, thus only one of the other two can. They thus form a conjugate pair which you put to good use in your first elimination. Danny does as well in his. I guess another interesting area to explore would be how effective these ALHS(?) are in general solutions.

by **champagne** » Sun Mar 16, 2008 8:55 am

Hi Mike,

Before commenting your last post, I forward a nice solution proposed by "soryu" a French player.
Soryu uses a small solver based on triangular matrix method to analyse the puzzle.

As hand solver, he uses the full tagging method.

The proposal has been found thru the triangular matrix process.
I show it as it could have been found by the solver.
One can also translate it in a form of 'T' chain.

This very short sequence establishes r1c7=4 as in my solution, without using any ALS.
It's likely not so far from forcing chains seen earlier

We start from the same point as in my solution

Code: Select all: 12a3E8 5 1378 |13789 3n7Å8o9 1379 |4b78 6 12A4B79í 16Á8 1678 4 |15c6789 2 15C679 |3 189G 1789 9 2A6Z78 13U78 |13678 4 1367 |7Î8 12a8 5 -------------------------------------------------------------------- 24v8Æ 9 6 |1d237 3N7n 1D237 |5 24y8Ë 247â8 1Q23e 127 13E7Ä |4 5 8 |6f7F 2G9g 26F79G 248 24X7ã8ê 5 |26h79 79 26H79 |1 3 24v78Æ -------------------------------------------------------------------- 7 1r48 189m |58Ì9 6 4p59 |2 1k45j8 3 45j68 46Á8 2 |3i7I 1 3I7i |9 45J8 46à8 45J6à8 3 1k89M |2l589 8O9o 2L4P59 |4B6F8é 7 1K468

And a clearing chain defined in three steps

Code: Select all: 1)[]a - ~1r2c1 1r2c1 []1r1c1 - 2r1c1.a []1r5c1 - 3r5c1 == 3r1c1 - 2r1c1.a 2)[]a - ~1r1c9 1r1c9 []1r2c89 - 1r2c1 = ~1r2c1 -a []1r3c8 - 2r3c8.a 3) 479r1c9 - 2r1c9 = 2r1c1.a - ~1r1c9 = 1r1c9 - 479r1c9

note : ~1r2c1 means any group in strong link with 1r2c1. Here it was 1r15c1

From that example and thru the basic work I am doing to prepare my website, I raise a question.

At the end of the cleaning, the chain becomes a nice loop. Normally, in a nice loop, any weak link switches to a strong link. Is it still valid in a net of AICs?

If we apply that rule, all intermediate weak links would switch to strong links

EDIT: unhappily, it seems that the rule applied to use kraken blossoms is not compatible with that statement

Mike wrote

I guess another interesting area to explore would be how effective these ALHS(?) are in general solutions.

As I said before, this push ahead the limit of unsolvable puzzles without use of ALS with a limited quantity of additional stuff.

For a computer, it is of no interest. For human solver, it's important to have intermediate levels.

The net produced by soryu for example is quite accessible to a human player. It is far in the hierarchy of my solver and I have no chance to produce it thru it.

by **Mike Barker** » Sun Mar 16, 2008 2:04 pm

Champagne, thanks for translating from the French site. I wanted to involve them, but don't speak French. Here's what I believe is an alternative version for the t-chain. The first t-link (-1-r1c1) corresponds to (a - ~1r2c1) and the second (-1-r3c8) to (a - ~1r3c1)

Code: Select all: 5-element NRCT chain: r1c9 =2= r3c8 -2- r3c2 =2= r1c1 =3= r5c1 =1= (-1-r1c1)r2c1 -1- r2c89 =1= (-1-r3c8)r1c9 => r1c9=12 +-------------------+----------------------+--------------------+ | 1238* 5 1378 | 13789 3789 1379 | 478 6 12-479* | | 168* 1678 4 | 156789 2 15679 | 3 189* 1789 | | 9 2678* 1378 | 13678 4 1367 | 78 128* 5 | +-------------------+----------------------+--------------------+ | 248 9 6 | 1237 37 1237 | 5 248 2478 | | 123* 127 137 | 4 5 8 | 67 29 2679 | | 248 2478 5 | 2679 79 2679 | 1 3 2478 | +-------------------+----------------------+--------------------+ | 7 148 189 | 589 6 459 | 2 1458 3 | | 4568 468 2 | 37 1 37 | 9 458 468 | | 456 3 189 | 2589 89 2459 | 468 7 1468 | +-------------------+----------------------+--------------------+

I've also wondered at what the conditions for conjugancy in a multi-inference nice loop. So far I've only come up with the sufficient condition that it occurs at points in the loop with only a single path connecting the right section of the chain to the left.

by **Draco** » Mon Mar 17, 2008 1:19 am

Mike Barker wrote:Your forcing chains are fine except I would have included r5c1=3 as a step in the first chain.

Oops... thanks for catching that. I am still tuning how I display the chains/nets. Maybe once I get that right I ought to write an "auto-transcriber" to go with it.

Mike Barker wrote:Without going into much detail (if you are interested I'd be happy to), your second elimination can also be seen as:

Code: Select all
r5c7=6=r5c9=9=r2c9=7=r3c7-7-r5c7

which reads if r5c7<>6 then r5c9=6, r2c9=9, r3c7=7, r5c7<>7.

Yes, details please (here or by PM as you prefer). I don't quite follow your notation. I do see a forcing chain that could start in r5c7... is that what you're showing? Doesn't seem like it, but since I am not sure I'm reading your notation properly, hard for me to say.

As I read your response, I found another transcription error in my original post. The initial elmination in box 3 was listed as r1c8 <> 4, 7, 9. That should be r1c9 <> 4, 7, 9. That transcriber is sounding better all the time...

Cheers,

- draco

by **Mike Barker** » Tue Mar 18, 2008 3:26 am

There is an ongoing debate about what the best advanced solving techniques are. Probably no one would argue that patterns such as X-wings, XY-wings, and URs are some of the best because they are relatively easy to recognize. After that there are many options. Some techniques such as trial & error, forcing chains, and tabling can be very effective at solving a puzzle, but there is a big random aspect to them. If you choose right you could solve the puzzle in a cascade of singles (Ariadne's thread), you might find an elimination, or you might be left with nothing and have to backtrack out the changes that were made. T&E, etc might be thought of as a "what if" or "what may be" approach. What if this candidate is true or false? An alternative was proposed by Eppstein, ScottH, Jeff, and with a modification, Myth Jellies. What was proposed was to look at "what is", that is, characteristics of the puzzle which are true independent of the veracity of any candidate.

At the simplest level these characteristics are found in bivalue cells (cells with only to candidates) or bilocal units (aka strong links or conjugate pairs - rows, columns, or boxes with only two instances of a candidate). In either case one or the other of the candidates must be true. It turns out that bivalue cells and bilocal units can be linked together to establish eliminations based on a simple set of rules to form nice loops or alternating inference chains. In the nice loop constructed from your elimination (r5c7=6=r5c9=9=r2c9=7=r3c7-7-r5c7) there are three strong links (r5c7=6=r5c9, r5c9=9=r2c9, and r2c9=7=r3c7) where the strong link is indicated by the "=". In a strong link if one candidate is false then the other must be true.

The construction rules say that strong links can be linked together if they share a common cell and their "labels" (the digit defining the link) are different. This is the case here. It is also possible to connect strong links with the same labels as long as the end cells share a house ("see" each other), but are not the same cell. Bivalues can be linked to other bivalues or to strong links. These last links are examples of weak links. In a weak link if one candidate is true then the other must be false. Two of the key characteristics of linking bivalues and bilocals in this way are that the linking relationships are always true regardless of which candidates are true or false and that the resulting chain is reversible (you can start at either end and get to the other with a valid set of if/then statements).

Having constructed a nice loop or AIC it is then possible to eliminate candidates again according to a set of rules. In this case the rule states that if a cell has a strong link with one label and a weak link with another and contains a candidate with the weak link label then that candidate can be eliminated, thus "7" can be eliminated from r5c7. There are other rules for cases with two strong links into a cell or two weak links.

Is this better than T&E, forcing chains, etc? Many think so because the random element is reduced. On the other hand keeping track of bivalues and bilocals is more work. I tend to be in the nice loop/AIC camp, but ultimately it boils down to what is the most fun for you. It may be that reducing the random element leads to a quicker solution. I'm not convinced of this, but I do know that I like to understand why things work and nice loops/AICs definitely provide that. Nice loops won't solve all puzzles, but we keep looking for ways to better use them (thus my questions on which ALSs are effective, how Champagne's "AHLS" might be used more effectively than an ALS, or what other characteristics exist in a puzzle which we are not utilizing). On the other hand, another alternative is what I'd call intelligent T&E - finding ways to limit the amount of T&E by selecting cells or units with certain "to be determined" characteristics. I think these unanswered questions are one of the things that keeps Sudoku fun and interesting.

by **Draco** » Tue Mar 18, 2008 5:30 pm

Thanks for the detailed reply!

I keep looking at "(r5c7=6=r5c9=9=r2c9=7=r3c7-7-r5c7)" and feel I must be dense because I still read the opening as "r5c7 is 6" yet your text in your first post states "r5c7 is not 6" (or more exactly "r5c7<>6" which I read as "r5c7 not equal to 6"). Feel free to sigh and tell me to just reread posts referenced in your first reply if my questions become too annoying.

As to the debate on advanced solving techniques... this is a very interesting area to me.

Before I constructued my Forcing Chain/Net code, I spent a lot of time looking at color chains. I'll be damned if I can spot entire color chains without the computer or a lot of T&E-like work (and VERY light pencil marks or overlays). It is not something I can do in my head (as I can, for instance, scanning for hidden or naken doubles or triples or locked sets).

Once I had the computer finding them for me, I noticed that color chains provided great candidates for "good guesses"; long color chains are a great place to try Nishino or Ariadne's thread (something that, because of my background, I think of as "recursion"). Because there are so many strongly-linked cells, giving one or the other of the bi-values a go often collapsed the puzzle significantly (if not completely). It is, after all, the same target-rich environment one would use to search for nice loops or AIC's. The coloration makes it that much clearer (to me) where the really target-rich veins lie in the puzzle.

I think of this as "guided guessing", and it seems to be along the same lines as your intelligent T&E.

In considering "solving" versus "guessing", the line of demarcation on which I settled was the point where I can no longer just recognize a pattern (for me that line happens at XY Wings, and that is stretching it) and must instead undertake a lot of work to find candidates, "feed them" to the technique, and see what comes out. Take color chains as an example.

One must first find the bi-value pairs in houses and link them. Then look for overlaps of various kinds to arrive at cancellations. Just coloring the puzzle for any given square value is something, as I noted previously, I find time consuming (relative to finding patterns, locked sets & fishy patterns). So for me, even color chains are over the edge of things I can "see" versus things I need to "work through several steps" before I know if I am on to something.

Not too much difference, then, between Nice Loops or AIC's (in my own view) and color chains (both rely on bi-values and you start out with a thought along the lines of, "hmm, this looks promising...").

I would specifically call out patterns such as sky scrapers, deadly pattern and other sequences one can recognize by sight as being on the pattern/locked set side of things. I would also note that exactly where one draws this line depends very much on how obvious such patterns seem to them within puzzles. As I noted, for me XY-Wings are pushing it.

When I decided to play with forcing chains, I started implementing an algorithm that would find only changes in bi-value cells (including color chains). I noticed quickly that lots of one-way forces would occur... creating singles along one path but not another. It is clear that tracking these leads to quicker cancellations and (with some tuning) still tends to mostly find chains that involve only bi-value squares. But not always (and when it doesn't, the information is very useful if somewhat harder to see). To me this seems little different than finding singles as one goes through general puzzle solving. So why leave them out?

What it does make harder, in my experience, is reconstructing the chain of events after the cancellations are made

. Getting better at that too as time goes on.

One thing that I have observed in the Sudoku community is a distinct preference for what I might call ABAT or ACR (Anything But Ariadne's Thread or Anything But Recursion). Which is cool... it's pushing the envelope with new techniques. Yet now that I've implemented color chains and forcing chains, there is so much trial and error in those that I see little difference insofar as the work required.... except that Guided Guessing often leads to a solution faster than the T&E approach required for chains of any kind.

And both start with a Guided Guess ("hmm, this looks promising...").

I still have a lot of testing to do against puzzles and a lot more to learn about solving techniques. I appreciate the time you've taken to respond to my posts so far, and look forward to your (and anyone else's) thoughts on the above.

Cheers...

- Draco

The New Sudoku Players' Forum

Challenge Puzzle #10

Challenge Puzzle #10 solution