Need advanced method to solve

Post the puzzle or solving technique that's causing you trouble and someone will help

Need advanced method to solve

Postby Addison » Sat May 02, 2020 3:21 pm

I’m new to using advanced techniques to solve Sudoku puzzles. I have an an app on my phone and the “hard” puzzles never give me an issue, but the “expert” puzzles always get to a point where I can’t see what to do next. Can someone please help me with the puzzle below? I don’t see any hidden pairs or triples or quads. I don’t see any x-wings either. So I don’t know what to do next. Thanks!

7A2FCC13-79C1-4B10-881A-5B44E7B434BB.jpeg
7A2FCC13-79C1-4B10-881A-5B44E7B434BB.jpeg (58.35 KiB) Viewed 433 times
Addison
 
Posts: 2
Joined: 02 May 2020

Re: Need advanced method to solve

Postby SpAce » Tue May 05, 2020 9:46 pm

Hi Addison,

Don't beat yourself up. Basics won't help here, nor do even the easiest non-basics. Hodoku's default solution uses six non-basic moves, including a Sue-de-Coq (which I consider non-trivial). However, it can be solved with a single relatively simple move, but it requires something like a short AIC or an ALS-XZ. For example:

Code: Select all
.---------------------.-----------------.------------.
|  457    3467  34567 |  34     347  1  | 2   8   9  |
| b24     2348  348   | c234    6    9  | 5   7   1  |
|  9      27    1     | d25     8    57 | 4   6   3  |
:---------------------+-----------------+------------:
| a4[5]   36    36    |  9      1    2  | 7   45  8  |
|  147-5  9     47-5  | e34(5)  347  8  | 13  2   6  |
|  12457  2478  4578  |  6      347  57 | 13  9   45 |
:---------------------+-----------------+------------:
|  3      5     9     |  8      2    4  | 6   1   7  |
|  8      47    47    |  1      5    6  | 9   3   2  |
|  6      1     2     |  7      9    3  | 8   45  45 |
'---------------------'-----------------'------------'

AIC: (5=4)r4c1 - (4=2)r2c1 - r2c4 = (2-5)r3c4 = (5)r5c4 => -5 r5c13; stte

...or:

Code: Select all
.---------------------.-----------------.------------.
|  457    3467  34567 | b34     347  1  | 2   8   9  |
| a24     2348  348   | b234    6    9  | 5   7   1  |
|  9      27    1     |  25     8    57 | 4   6   3  |
:---------------------+-----------------+------------:
| a4[5]   36    36    |  9      1    2  | 7   45  8  |
|  147-5  9     47-5  | b34(5)  347  8  | 13  2   6  |
|  12457  2478  4578  |  6      347  57 | 13  9   45 |
:---------------------+-----------------+------------:
|  3      5     9     |  8      2    4  | 6   1   7  |
|  8      47    47    |  1      5    6  | 9   3   2  |
|  6      1     2     |  7      9    3  | 8   45  45 |
'---------------------'-----------------'------------'

ALS XZ: {ALS a: (245)r24c1, ALS b: (2345)r125c4, X=2, Z=5} => -5 r5c13; stte

as an AIC: (5'4=2)r42c1 - (2=34'5)r125c4 => -5 r5c13; stte

Either way the patterns guarantee that there's a 5 in either r4c1 or r5c4 (or both), thus it can't be in r5c13. After that it's just singles.

Btw, if you're new to these kinds of chains and have a hard time seeing why they work, you can always double-check the eliminations by trying to place those candidates. If you place 5 in either r5c1 or r5c3 it should produce a contradiction shortly, which is a valid (though inelegant) way to prove (and even find) any elimination.
-SpAce-: Show
Code: Select all
   *             |    |               |    |    *
        *        |=()=|    /  _  \    |=()=|               *
            *    |    |   |-=( )=-|   |    |      *
     *                     \  ¯  /                   *   

"If one is to understand the great mystery, one must study all its aspects, not just the dogmatic narrow view of the Jedi."
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Wed May 06, 2020 9:29 am

Addison wrote:I’m new to using advanced techniques to solve Sudoku puzzles. I have an an app on my phone and the “hard” puzzles never give me an issue, but the “expert” puzzles always get to a point where I can’t see what to do next. Can someone please help me with the puzzle below? I don’t see any hidden pairs or triples or quads. I don’t see any x-wings either. So I don’t know what to do next. Thanks!
7A2FCC13-79C1-4B10-881A-5B44E7B434BB.jpeg

You don't need anything more complex than bivalue chains (the basic AICs) :

Hidden Text: Show
***********************************************************************************************
*** SudoRules 20.1.s based on CSP-Rules 2.1.s, config = W+SFin
*** using CLIPS 6.32-r764
***********************************************************************************************
95 candidates, 465 csp-links and 465 links. Density = 10.41%
whip[1]: r4n3{c3 .} ==> r6c3 ≠ 3, r5c3 ≠ 3, r6c2 ≠ 3
whip[1]: r3n5{c6 .} ==> r1c4 ≠ 5
naked-pairs-in-a-row: r4{c1 c8}{n4 n5} ==> r4c3 ≠ 5, r4c3 ≠ 4, r4c2 ≠ 4
biv-chain[3]: r2c1{n4 n2} - b4n2{r6c1 r6c2} - c2n8{r6 r2} ==> r2c2 ≠ 4
biv-chain[3]: r2c1{n4 n2} - r3c2{n2 n7} - r8c2{n7 n4} ==> r1c2 ≠ 4
biv-chain[3]: r6n8{c3 c2} - c2n4{r6 r8} - b7n7{r8c2 r8c3} ==> r6c3 ≠ 7
biv-chain[3]: r6n2{c1 c2} - r3c2{n2 n7} - c6n7{r3 r6} ==> r6c1 ≠ 7
biv-chain[3]: c1n7{r5 r1} - r3c2{n7 n2} - r2c1{n2 n4} ==> r5c1 ≠ 4
whip[3]: r4c1{n4 n5} - r5c3{n5 n7} - r8c3{n7 .} ==> r6c3 ≠ 4
biv-chain[4]: r8c3{n7 n4} - c2n4{r8 r6} - r4c1{n4 n5} - b1n5{r1c1 r1c3} ==> r1c3 ≠ 7
biv-chain[4]: c2n4{r8 r6} - r6c9{n4 n5} - c6n5{r6 r3} - r3n7{c6 c2} ==> r8c2 ≠ 7
singles ==> r8c2 = 4, r8c3 = 7
naked-pairs-in-a-block: b4{r4c1 r5c3}{n4 n5} ==> r6c3 ≠ 5, r6c1 ≠ 5, r6c1 ≠ 4, r5c1 ≠ 5
singles ==> r6c3 = 8, r2c2 = 8
naked-pairs-in-a-column: c2{r3 r6}{n2 n7} ==> r1c2 ≠ 7
x-wing-in-columns: n7{c2 c6}{r3 r6} ==> r6c5 ≠ 7
biv-chain[3]: r5c3{n4 n5} - b5n5{r5c4 r6c6} - b5n7{r6c6 r5c5} ==> r5c5 ≠ 4
hidden-pairs-in-a-row: r5{n4 n5}{c3 c4} ==> r5c4 ≠ 3
whip[1]: b5n3{r6c5 .} ==> r1c5 ≠ 3
finned-x-wing-in-rows: n4{r5 r2}{c4 c3} ==> r1c3 ≠ 4
biv-chain[3]: c3n5{r1 r5} - r5n4{c3 c4} - r1c4{n4 n3} ==> r1c3 ≠ 3
biv-chain[3]: r1n3{c4 c2} - r2c3{n3 n4} - r5n4{c3 c4} ==> r1c4 ≠ 4
stte
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby SpAce » Wed May 06, 2020 11:12 am

Hi Denis,

denis_berthier wrote:You don't need anything more complex than bivalue chains (the basic AICs)

That's true, but why do you need ten of them + an X-Wing + a Finned X-Wing + a number of "whips" (which I don't know what they are, but one of them looks like a chain too)? If your point was to demonstrate that this was a simple puzzle (for a beginner), I think it failed :) How about just one "bivalue chain":

biv-chain[4]: r4c1{n5 n4} - r2c1{n4 n2} - c4n2{r2 r3} - c4n5{r3 r5} ==> r5c13 ≠ 5; stte

? It's the same chain I presented as an AIC, if I translated it correctly. I've never used your notation before, but I'd like to learn it (as it's pretty much the last major sudoku notation I haven't yet). I think I understand you "biv-chains" all right, as they seem to have direct AIC-mappings, but that's about it. (I've actually borrowed your 3D-concept for my own compacted AIC-notation, though it hasn't been well-received). To start with the simplest cases, what's a whip? It would be most helpful if you could point to a mapping in our common system (which I'm sure there is).

Btw, most people here would expect a "bivalue chain" to mean a normal XY-Chain (using bivalue cells only). I know your concept is generalized to all strong links (including bilocals), but I don't think that can be expected of most people, especially beginners. Using names for other purposes than their well-established meanings (in that particular context) is not generally helpful. (Don't take this personally -- it's one of my pet peeves in general.) It's good that you specified that they're basically the same as AICs (thus more general than mere xy-chains), but it's still confusing (perhaps even more). Since you probably don't want your chains to be called AICs either (even though you just did), could you possibly have any other more specific name for your (AIC-equivalent) chains? I think that would make accurate communication easier for all parties. If not, no big deal. Just a suggestion.
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Wed May 06, 2020 11:44 am

SpAce wrote:
denis_berthier wrote:You don't need anything more complex than bivalue chains (the basic AICs)

That's true, but why do you need ten of them + an X-Wing + a Finned X-Wing + a number of "whips" (which I don't know what they are, but one of them looks like a chain too)? If your point was to demonstrate that this was a simple puzzle (for a beginner), I think it failed :) How about just one "bivalue chain":biv-chain[4]: r4c1{n5 n4} - r2c1{n4 n2} - c4n2{r2 r3} - c4n5{r3 r5} ==> r5c13 ≠ 5; stte

Because in any rational approach, people look for short chains before longer ones.
There isn't "a number of whips". There are whips[1] (and they were already eliminated in the first PM), which I've recalled million times are no more than intersections (which BTW have no standard name either).


SpAce wrote:I've never used your notation before, but I'd like to learn it (as it's pretty much the last major sudoku notation I haven't yet). I think I understand you "biv-chains" all right, as they seem to have direct AIC-mappings, but that's about it. (I've actually borrowed your 3D-concept for my own compacted AIC-notation, though it hasn't been well-received).

It's quite easy to learn. Just read the small part of PBCS introducing it. The main ideas are:
- a CSP-Variable and its possible values being included in curly braces (straightforwardly inspired by set notation) after the name of the variable
- a link (= a direct contradiction) between two candidates (represented as a "—" )


SpAce wrote:To start with the simplest cases, what's a whip? It would be most helpful if you could point to a mapping in our common system (which I'm sure there is).

There are only whips[1]. See above. For longer whips, like any pattern, you can't expect to know what they are if you don't read their definition.


SpAce wrote:Btw, most people here would expect a "bivalue chain" to mean a normal XY-Chain (using bivalue cells only). I know your concept is generalized to all strong links (including bilocals), but I don't think that can be expected of most people, especially beginners. Using names for other purposes than their well-established meanings (in that particular context) is not generally helpful. (Don't take this personally -- it's one of my pet peeves in general.) It's good that you specified that they're basically the same as AICs (thus more general than mere xy-chains), but it's still confusing (perhaps even more). Since you probably don't want your chains to be called AICs either (even though you just did), could you possibly have any other more specific name for your (AIC-equivalent) chains? I think that would make accurate communication easier for all parties. If not, no big deal. Just a suggestion.

Most people, especially beginners, must learn the proper concepts. "Strong link" is the worst concept one can imagine. As I said above, the proper two basic concepts are that of a CSP-Variable and of a link.
As I've always said also, there is an obvious mapping from my bivalue-chains to basic AICs. Only the notation is different.
Now, learning the proper concepts implies that you don't make any major difference between bivalue and bilocal. I don't know much about the AIC notation, but if it does it's one more terrible failure for it.


The reason for not adopting Sudoku-specific names is, all these patterns are meaningful in a much more general setting, as you can see from all the other examples I've developed in PBCS.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby Addison » Wed May 06, 2020 3:01 pm

Thanks for the help Space and Denis!

Now I just need a translation of all these abbreviations and notations!

I looked around the forum a little and couldn't find anything definitive. Could either of you provide a link to some of the following? I don't expect you to explain it all here since I'm sure it's all explained in more detail elsewhere.

Hodoku
Sue-de-Coq
AIC
ALS-XZ
How to read this notation (I know "rxcy" means row x, column y, but I'm lost as to the rest of it; and what does "r5c13" mean? Aren't there only 9 rows and 9 columns?):
Code: Select all
(5=4)r4c1 - (4=2)r2c1 - r2c4 = (2-5)r3c4 = (5)r5c4 => -5 r5c13; stte

whip

Thanks!
bi-value chain
PBCS
Addison
 
Posts: 2
Joined: 02 May 2020

Re: Need advanced method to solve

Postby SpAce » Thu May 07, 2020 6:06 am

denis_berthier wrote:Because in any rational approach, people look for short chains before longer ones.

Really? That's quite a bold and presumptuous statement. How do you back that up? What makes you think that your "simplest first" strategy is the only (or even the most) rational one, or that short chains are always the simplest to find anyway? You must make an awful lot of assumptions to do that. To me it seems like a very simplistic and rigid strategy, hardly fulfilling typical goals of experienced human solvers. For example, how does it help to find the shortest path to a solution, or the quickest solution, or the most elegant solution, or the most fun solution, etc? Are those irrational goals to you? Perhaps they are, but you don't get to choose for other people. In fact, you can't determine anything about the rationality of someone's strategy unless you know intimately what their personal goals and skills and other tendencies are. What's crazy to you might be wisdom for another, and vice versa.

What in fact are goals which make such a strategy the most rational choice? I can see its value as an easy-to-implement strategy for a software solver, and as a standardized solve path for rating purposes, but those things have nothing to do with human solving. That said, I did find value in such an approach a couple of years ago when I had just started to learn advanced methods and couldn't care less about efficiency or elegance (*). Back then I actually wanted to find as many chains as possible to gain more experience (and because novelty made it fun), so I sometimes deliberately delayed making any killer moves even if they were obvious. Obviously my goals have changed since then, as I predicted. Haven't yours?

(*): Show
Sep 14, 2017:

SpAce wrote:I'm not yet in the level that I'd try to optimize or restrict the solving path too much, but I'll keep in mind those additional challenge options. My first priority is to find at least one working path, but especially with simpler puzzles I try to find some alternate ways as well. So far I've been aiming more for simplicity and repeatability than maximum efficiency or elegance. I'm sure priorities will change with improving skills.

I'm also interested in how you, as a human player, actually look for short chains specifically. Personally I (and probably most other human players) use coloring to find all but the most obvious chains, and there's usually no telling beforehand how long and complex chains the process will reveal. In fact, there's no real difference in the difficulty of finding chains of various lengths. Other aspects of complexity matter much more. That's why I'm curious why you think length is so important that it should even determine the rationality of solving strategies. If I were to prioritize short chains above all, it would complicate instead of simplify my solving process. Needless to say that it would almost always lengthen the solve paths and solving times considerably as well. Where's the upside?

I'll get back to the notational stuff later, thanks for replying. Your first sentence just happened to be so interesting that it got my full attention :)
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Thu May 07, 2020 7:54 am

Hi Space,

You're making much ado about nothing. I never said that human solvers had to stick to a rigid approach. Indeed, every time the topic appears, I explicitly say the opposite. Probably, the wording of my first sentence didn't take into account the itchiness of some players when it comes to their way of playing.
The fact is, apart from my simplest-first search, no consistent approach has ever been developed to define "a shortest path" or a "quickest solution". I personally don't consider a path A shorter than B because A has only 2 chains and B has 3, if the chains of A are longer than those of B.
Providing a consistent way to define the "length of a path" is a challenge that no one has been able to deal with.

As for "most elegant" or "most fun solution", I'm eager (not really) to read how you would define these in terms of rationality. They are personal appreciations and they should stay so.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby denis_berthier » Thu May 07, 2020 8:39 am

Here are two alternative paths.

1) if you are not at ease with mixing (rc-)bivalue and bilocation relations in a sigle chain, this is a solution where each of the bivalue-chains is in a single 2D-space:

Code: Select all
naked-pairs-in-a-row: r4{c1 c8}{n4 n5} ==> r4c3 ≠ 5, r4c3 ≠ 4, r4c2 ≠ 4
biv-chain-rc[3]: r2c1{n4 n2} - r3c2{n2 n7} - r8c2{n7 n4} ==> r1c2 ≠ 4, r2c2 ≠ 4
biv-chain-cn[4]: c4n5{r5 r3} - c4n2{r3 r2} - c1n2{r2 r6} - c1n1{r6 r5} ==> r5c1 ≠ 5
biv-chain-rn[4]: r3n7{c2 c6} - r3n5{c6 c4} - r5n5{c4 c3} - r1n5{c3 c1} ==> r1c1 ≠ 7
whip[1]: c1n7{r6 .} ==> r5c3 ≠ 7, r6c2 ≠ 7, r6c3 ≠ 7
naked-pairs-in-a-block: b4{r4c1 r5c3}{n4 n5} ==> r6c3 ≠ 5, r6c3 ≠ 4, r6c2 ≠ 4, r6c1 ≠ 5, r6c1 ≠ 4, r5c1 ≠ 4
stte



2) if you are not at ease at all with bilocation, here is a solution totally in rc-space, but it requires slightly longer and more complex chains:

Code: Select all
biv-chain-rc[3]: r2c1{n4 n2} - r3c2{n2 n7} - r8c2{n7 n4} ==> r1c2 ≠ 4, r2c2 ≠ 4
whip-rc[3]: r8c3{n4 n7} - r5c3{n7 n5} - r4c1{n5 .} ==> r6c3 ≠ 4
t-whip-rc[4]: r3c2{n7 n2} - r2c1{n2 n4} - r4c1{n4 n5} - r1c1{n5 .} ==> r1c2 ≠ 7, r1c3 ≠ 7
naked-pairs-in-a-column: c2{r1 r4}{n3 n6} ==> r2c2 ≠ 3
finned-x-wing-in-rows: n7{r1 r5}{c5 c1} ==> r6c1 ≠ 7
t-whip-rc[4]: r4c1{n5 n4} - r2c1{n4 n2} - r3c2{n2 n7} - r1c1{n7 .} ==> r5c1 ≠ 5, r6c1 ≠ 5
t-whip-rc[4]: r2c1{n2 n4} - r4c1{n4 n5} - r1c1{n5 n7} - r3c2{n7 .} ==> r2c2 ≠ 2
singles ==> r2c2 = 8, r6c3 = 8
whip-rc[4]: r2c1{n4 n2} - r3c2{n2 n7} - r1c1{n7 n5} - r4c1{n5 .} ==> r5c1 ≠ 4
whip-rc[4]: r2c1{n4 n2} - r3c2{n2 n7} - r1c1{n7 n5} - r4c1{n5 .} ==> r6c1 ≠ 4
whip-rc[5]: r6c6{n7 n5} - r6c9{n5 n4} - r6c2{n4 n2} - r3c2{n2 n7} - r3c6{n7 .} ==> r6c5 ≠ 7
x-wing-in-columns: n7{c1 c5}{r1 r5} ==> r5c3 ≠ 7
hidden-single-in-a-column ==> r8c3 = 7
naked-single ==> r8c2 = 4
whip-rc[3]: r5c3{n4 n5} - r5c4{n5 n3} - r6c5{n3 .} ==> r5c5 ≠ 4
hidden-pairs-in-a-row: r5{n4 n5}{c3 c4} ==> r5c4 ≠ 3
whip[1]: b5n3{r6c5 .} ==> r1c5 ≠ 3
finned-x-wing-in-rows: n4{r5 r2}{c4 c3} ==> r1c3 ≠ 4
biv-chain-rc[4]: r2c3{n3 n4} - r5c3{n4 n5} - r5c4{n5 n4} - r1c4{n4 n3} ==> r1c2 ≠ 3, r1c3 ≠ 3, r2c4 ≠ 3
stte
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby SpAce » Thu May 07, 2020 9:51 am

Hi Denis,

denis_berthier wrote:You're making much ado about nothing.

Accepted. Perhaps I read too much into your wording. Thanks for explaining.

I personally don't consider a path A shorter than B because A has only 2 chains and B has 3, if the chains of A are longer than those of B.

All other things being equal (complexity of the chains etc), I probably would consider path A shorter, if the path length is supposed to be proportional to solving time/complexity/efficiency. At least with my methods, it's usually faster to find two longer chains than three shorter chains (unless they're so short and simple that they can be found by mere eyeballing). If finding each chain requires its own coloring, the overhead of the context switching is much more than tracking a bit longer chains. Besides, more steps (usually, not necessarily) implies that more eliminations were required to crack the puzzle, and that implies a less efficient strategy (from that point of view, at least).

Providing a consistent way to define the "length of a path" is a challenge that no one has been able to deal with.

You're right. A mere step count is not an accurate measurement of anything. I guess a simplistic way to calculate the overall length would be summing up the lengths of all chains (using your definition of length; i.e. the number of strong links in our terminology). That, however, wouldn't take into account that it probably takes more time to find two unrelated short chains than a single longer chain. That's why each step should have a constant added to the actual length of the chain. Another difficulty is that it's not straightforward to compare the lengths of individual AICs, as the number of strong links depends heavily on the level of ALS-compression (perhaps not a problem with your chains). Either all lengths should be calculated for fully uncompressed chains, or otherwise compressed chains should receive a suitable penalty for extra complexity. It gets even more hairy with things like split-node AICs which actually have two parallel chains packed into one. So yeah, not a trivial problem.

As for "most elegant" or "most fun solution", I'm eager (not really) to read how you would define these in terms of rationality. They are personal appreciations and they should stay so.

Indeed they are mostly subjective (the latter more than the former), but I chose not to mention the obvious. That said, personal appreciations are very important aspects in any human rationality calculations, so I don't see them as any less worthy in principle. They're just harder to measure, being both fuzzier and less objective. Wouldn't you agree that, all other things being equal, it's more rational for a person to pursue paths that they consider more fun to follow and which produce more emotionally/intellectually satisfying results?
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Thu May 07, 2020 10:23 am

SpAce wrote:If finding each chain requires its own coloring, the overhead of the context switching is much more than tracking a bit longer chains. Besides, more steps (usually, not necessarily) implies that more eliminations were required to crack the puzzle, and that implies a less efficient strategy (from that point of view, at least).

I don't use colouring (though, of course, it would be possible). Partial-whips are intrinsic structures that don't have to be erased (unless some part of them is deleted by another rule).

SpAce wrote:
Denis_Berthier wrote:Providing a consistent way to define the "length of a path" is a challenge that no one has been able to deal with.

You're right. A mere step count is not an accurate measurement of anything. I guess a simplistic way to calculate the overall length would be summing up the lengths of all chains (using your definition of length; i.e. the number of strong links in our terminology).

There are no strong links in my terminology. The length of a chain is the number of CSP-Variables it involves.

SpAce wrote:That, however, wouldn't take into account that it probably takes more time to find two unrelated short chains than a single longer chain. That's why each step should have a constant added to the actual length of the chain.

I thought of something like this at the time of HLS. But the constant is totally arbitrary and it's impossible to turn the whole thing into any practical way of finding the shortest path.

SpAce wrote:Another difficulty is that it's not straightforward to compare the lengths of individual AICs, as the number of strong links depends heavily on the level of ALS-compression (perhaps not a problem with your chains). Either all lengths should be calculated for fully uncompressed chains, or otherwise compressed chains should receive a suitable penalty for extra complexity. It gets even more hairy with things like split-node AICs which actually have two parallel chains packed into one. So yeah, not a trivial problem.

Not sure what a compressed chain is. If you mean it includes some Subsets (or any other pattern), it's not a problem for me, because the sizes of the Subsets (or any other pattern) are included in the total length of the chain. That's one more place where the notion of a strong link is totally useless and misleading.

SpAce wrote:
Denis_Berthier wrote:As for "most elegant" or "most fun solution", I'm eager (not really) to read how you would define these in terms of rationality. They are personal appreciations and they should stay so.

Indeed they are mostly subjective (the latter more than the former), but I chose not to mention the obvious. That said, personal appreciations are very important aspects in any human rationality calculations, so I don't see them as any less worthy in principle. They're just harder to measure, being both fuzzier and less objective. Wouldn't you agree that, all other things being equal, it's more rational for a person to pursue paths that they consider more fun to follow and which produce more emotionally/intellectually satisfying results?

I would avoid using the word rational here. People behaviours don't have to be rational (and most often they aren't). Rationality isn't the measure of everything.

Recently, I've re-introduced old 2D patterns in SudoRules. They do not add any resolution power, as they are particular cases of the general ones. But the readers of HLS were used to them (some of them use my Extended Sudoku Board) and they repeatedly asked about them.
Do you think I asked myself if it was rational or not to do it? It's fun to see these 2D patterns and the alternative paths they allow. See my previous post for an example.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby SpAce » Thu May 07, 2020 12:29 pm

Just a quick reply for now...

denis_berthier wrote:Not sure what a compressed chain is.

See my solution here. In this case the difference in strong links is 3 (compressed) vs 6 (uncompressed).

The compressed chain also has an example of my non-standard "3D" notation for bilocation links: (4)r6=3c8 (in your notation: c8n4{r6 r3}). I normally avoid using it these days because everyone hates it :) The normal way of writing it is (4)r6c8 = r3c8, which has a lot of redundancy plus it's not consistent with the compact bivalue notation (4=6)r1c1. What I like about your notation is that all three axes (r,c,n) are treated the same way. What I don't like is that it's awkward to read quickly because the elements (r,c,n) switch places in every node (perhaps a matter of getting used to, I don't know).

Btw, I also prefer our box-position notation to your use of the rc-coordinates within a box context. For example, I'd rather write this: b4n3{r4c1 r5c3} like this: b4n3{p1 p9}. It's easier to visualize plus it's shorter and more consistent with the other types. The downside is the extra complexity of another coordinate system, and possibly some unknown incompatibilities with the rest of your system (I can't know).
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Re: Need advanced method to solve

Postby denis_berthier » Thu May 07, 2020 12:51 pm

SpAce wrote:Just a quick reply for now...
denis_berthier wrote:Not sure what a compressed chain is.

See my solution here. In this case the difference in strong links is 3 (compressed) vs 6 (uncompressed).
The compressed chain also has an example of my non-standard "3D" notation for bilocation links: (4)r6=3c8 (in your notation: c8n4{r6 r3}). I normally avoid using it these days because everyone hates it :) The normal way of writing it is (4)r6c8 = r3c8, which has a lot of redundancy plus it's not consistent with the compact bivalue notation (4=6)r1c1. What I like about your notation is that all three axes (r,c,n) are treated the same way. What I don't like is that it's awkward to read quickly because the elements (r,c,n) switch places in every node (perhaps a matter of getting used to, I don't know).

I don't like the AIC notation because it doesn't treat all the CSP-Variables the same way.
I don't like your box notation, because it's still harder to read than the usual one. Some amount of redundancy is not a problem. Every language, natural or not, has redundancy.
In my notation, the n/r/c letters are always present; there can be no ambiguity.

SpAce wrote:Btw, I also prefer our box-position notation to your use of the rc-coordinates within a box context. For example, I'd rather write this: b4n3{r4c1 r5c3} like this: b4n3{p1 p9}. It's easier to visualize plus it's shorter and more consistent with the other types. The downside is the extra complexity of another coordinate system, and possibly some unknown incompatibilities with the rest of your system (I can't know).
At the time of HLS, I hesitated about writing b4n3{r4c1 r5c3} or b4n3{s1 s6} . The second seems to be simpler. However, it makes it very difficult to see the link with the previous and next CSP-Variables. In the notation I finally chose, you have the 3 coordinates.
Another reason is that the p or s coordinate is of no use. There's no bs (bp for you) duality, contrary to the rc duality.
denis_berthier
2010 Supporter
 
Posts: 1672
Joined: 19 June 2007
Location: Paris

Re: Need advanced method to solve

Postby ghfick » Thu May 07, 2020 2:10 pm

Hi Addison,
From your post, it sounds like you are familiar with Naked/Hidden and X Wings but maybe you are just now exploring the many steps available for hard puzzles.
Steps like XY Wings and XYZ Wings should be learned. While there is a huge amount of material on this forum, I might advise you to look at sudokuwiki.org by Andrew Stuart, hodoku.sourceforge.net by Bernhard Hobiger and philsfolly.net.au by Phillip Beeby
These sites feature approachable writing and quite well designed solvers. While it is true that these sites are 'works in progress', they can give many hours of valuable study. You may want to search out Andrew Stuart's book 'The Logic of Sudoku'. Andrew has a friendly engaging writing style that keeps you wanting to learn more.
Quite recently, a new solver has been released called YZF_Sudoku. This solver is very up-to-date but it is still very definitely a work in progress. Worth checking out too [through the forum].
I tried your puzzle with each of these solvers. They each give essentially the same solution path. However, it is interesting to note that, after the XY Wing and XYZ Wing steps, each solver offers an apparently different next step. In Andrew's solver, it is an WXYZ Wing. In HoDoKu, it is a Sue de Coq. In YZF_Sudoku, it is an Almost Locked Pair. In each case, the exclusions are similar. Lots to learn from this. Maybe even more to the point, a step called an XY Chain can be tried that makes the WXYZ Wing / Sue de Coq / ALP step unnecessary. An XY Chain step solves the puzzle. Phillip's solver makes this clear. For me, learning the XY Chain was so valuable. It is definitely usable by humans and it is arguably 'easier' than many steps. Once you get the hang of searching for XY Chain exclusions, the length of the chain is a comparatively minor matter. Not trivial but not brutal either.
David P Bird has contributed many original documents to the forum. Outstanding but not easy.
Denis Berthier's two books are really scholarly and advanced. A distinctive view. Maybe not for early in one's Sudoku study.
John Welch has a blog that offers a huge amount of material. His blog is written in a highly personal style. He will send you templates that are remarkable and meticulous.
All the best
Gordon
ghfick
 
Posts: 102
Joined: 06 April 2016

Re: Need advanced method to solve

Postby SpAce » Fri May 08, 2020 1:55 am

ghfick wrote:I tried your puzzle with each of these solvers. They each give essentially the same solution path.

Of course, because by default they all use the "simplest first" strategy, just like Denis' solver. For this puzzle in particular that strategy yields an unnecessarily long and complicated solve path. To get something different you have to disable simpler techniques, or in Hodoku's case use the 'Find all steps' function. Btw, SudokuWiki's hierarchy seems to be broken: XY-Chain is listed before WXYZ-Wing but gets executed after it; thus to see its one-stepper with the XY-Chain one has to switch off not only Y-Wing and XYZ-Wing but also WXYZ-Wing. To see my solution, you also have to turn off XY-Chain, Unique Rectangle, Hidden Unique Rectangle, and Aligned Pair Exclusion.

Did you try to solve this by hand? It's much easier than what the software solvers' long paths imply. It took me less than five minutes to find the two relatively simple single-step solutions I presented (and another variant I didn't list because it was a bit longer) using the most obvious coloring seed. I never even saw the Y-Wing, XYZ-Wing or the WXYZ-Wing because I didn't need them (and finding them would have actually been much harder). That's why blindly following software solvers' default advice is not a great idea for efficient manual solving. (On the other hand, efficiency shouldn't be a primary concern for beginners. Finding many different patterns in the same puzzle state is good practice, even if many of them are relatively useless.)

For me, learning the XY Chain was so valuable. It is definitely usable by humans and it is arguably 'easier' than many steps.

Yes, we know you love them. I almost never use them because nicer options are usually available. XY-Chains are usually long, tedious to read and write, and mostly actually less easy to find than other AIC-types (if you have a good technique to find any AICs).

Btw, in this case, the SudokuWiki's XY-Chain (9 strong links!) is one of the most inefficient chains I've seen in a long time. Most XY-Chains are inefficient anyway but this one is especially dumb:

xychain.png
xychain.png (98.85 KiB) Viewed 305 times

(2=4)r2c1 - (4=5)r4c1 - (5=4)r4c8 - (4=5)r9c8 - (5=4)r9c9 - (4=5)r6c9 - (5=7)r6c6 - (7=5)r3c6 - (5=2)r3c4 => -2 r2c4,r3c2

Notice that it takes a very unnecessary detour in box 9. Clipping that gives us:

(2=4)r2c1 - (4=5)r4c1 - (5=4)r4c8 - (4=5)r6c9 - (5=7)r6c6 - (7=5)r3c6 - (5=2)r3c4 => -2 r2c4,r3c2

That's still 7 strong links and 4 digits. We can further streamline it by mixing in bilocal links:

(2=4)r2c1 - (4=5)r4c1 - r4c8 = r6c9 - r6c6 = r3c6 - (5=2)r3c4 => -2 r2c4,r3c2

That's 5 strong links and 3 digits -- clearly simpler, except for the mixed link types (but that shouldn't be a problem for anyone who uses chains regularly). Easier to read too without so many unnecessarily flip-flopping digits. Yet it's still a bit longer than my chain that had four strong links.

compressed variants: Show
Using the "3D" notation it can be written a bit shorter still (though the number of links remains the same):

(2=4)r2c1 - (4=5)r4c1 - b6p2=9 - r6=3c6 - (5=2)r3c4 => -2 r2c4,r3c2

With ALS-compression we can reduce it to three strong links:

(2=45)r24c1 - b6p2=9 - r6c6 = (52)r3c64 => -2 r2c4,r3c2

That's more than 60% shorter than the original XY-Chain in both characters and strong links.
User avatar
SpAce
 
Posts: 2559
Joined: 22 May 2017

Next

Return to Help with puzzles and solving techniques