The New Sudoku Players' Forum

[Mauriès Robert]

If you don't mind, I could post some images of what my process looks like. I don't mean to hijack your thread with GEM stuff, but I think it might visualize this concept quite well.

No problem SpAce, show your resolution with GEM and let's compare.
Robert

[SpAce]

No problem SpAce, show your resolution with GEM and let's compare.

Ok, here goes. Looks like I have to do multiple posts because this only allows three attachments at a time, and I have 11 pics. Sorry about that.
--

GEM Demonstration with Hodoku, Part 1/4

Using the puzzle: ...6..5......39..4.2.8.1....3..24..1..4....5.1......9...6...849.9..8.3..3....7...

0. General

In GEM the candidates form two competing parities, one of which is true and the other false in the solution. In Hodoku, I mark the opposite parities with Dark and Light colors. Within each parity there are three grades of candidates: par-candidates (Blue), super-candidates (Green), and sub-candidates (Red). Each type is explained in more detail below.

In addition, the coloring can depict found but not yet executed eliminations (dark grey), i.e. victims in David's parlance, and placements (cyan). Various kinds of group nodes are also colored specially, but that's not covered here.

1. Par candidates / Initial par cluster (seed)

The process starts by picking a conjugate pair (bilocation, bivalue) or preferably a cluster of them where both options have propagation potential. Those conjugate candidates form the initial par cluster, and they're colored blue (dark or light) in my process. Par-candidates with the same parity are equal (all true or false together), and par-candidates of the opposite parities have an XOR relationship (i.e. one or the other must be true in the solution, but not both). As long as those properties hold, other candidates can also be promoted to par-candidates later in the process (indicates a closed loop).

Notes. Normally the initial par-cluster is similar to a Simple Coloring (single digit) or a 3D Medusa (multiple digits connected by bivalue cells), and as such it can sometimes solve a puzzle by itself. Complex nodes (groups, ALSs, finned fishes, etc) and non-conjugates can also be used for seeding, but that's not covered here.

initial par-candidates: Show

gem01.png (88.36 KiB) Viewed 1004 times

The five conjugate 4s seemed like a potential coloring seed to begin with, forming a Simple Coloring par-cluster.

2. Sub-candidates

When an uncolored candidate sees a par-candidate or a super-candidate it gets colored as a sub-candidate of the opposite parity. In other words, they represent the eliminations that would certainly occur if the other parity were true. Sub-candidates are colored red (dark or light) in my system.

A sub-candidate gets promoted to a par-candidate if it would also get colored as a super-candidate (indicating a closed loop). A sub-candidate gets marked as a victim (elimination) if it would also get marked with the opposite sub-color, representing a trap (pincering) elimination. All sub-candidates of one parity get eliminated if the opposite parity turns out to be true, but their fate is unknown if their own parity is true. If a sub-candidate turns out to be true (or is assumed so) its own parity must be (assumed) true as well (and the other false).

initial sub-candidates: Show

gem02.png (89.57 KiB) Viewed 1004 times

3. Super-candidates

When an uncolored candidate becomes the sole survivor in any SIS (strong inference set) it gets colored as a super-candidate. In other words, if all other candidates in that SIS are colored as sub-candidates of the same parity, the last one becomes a super-candidate of the opposite parity. (Note: if all candidates of a SIS get colored as sub-candidates of the same parity, it's obviously a contradiction and that parity is false.) The simplest types of SIS are bivalue cells and bilocation candidates. Super-candidates represent potential placements just like par candidates, but with the crucial difference that they don't have a conjugate (XOR) relationship with the opposite parity. It means they can also be true if the other parity is true.

A super-candidate gets promoted to a par-candidate if it would also get colored as a sub-candidate (indicating a closed loop). A super-candidate becomes a placement if it would be marked as the opposite super-candidate as well. All super-candidates of one parity become true placements if their own parity turns out to be true, but their fate is unknown if the opposite parity is true. If a super-candidate turns out to be false (or is assumed so) its own parity must be (assumed) false as well (and the other true).

initial super-candidates: Show

gem03.png (71 KiB) Viewed 1004 times

[SpAce]

GEM Demonstration with Hodoku, Part 2/4

4. Eliminations

Eliminations can happen in two ways. One, if a candidate would get colored as a sub-candidate of both parities it can't be true either way. That would be a normal trap or a pincer elimination. Loop eliminations are seen similarly along their paths. Two, if one parity causes a contradiction of any kind that parity can't be true. In that case all of its par and sub-candidates can be eliminated, and the the par and super-candidates of the opposite parity can be placed. (We won't get to see the latter kind with this example, as neither parity causes a contradiction.)

Before we get to see our first eliminations, let's color some more sub-candidates. This will be the most Dark red we'll get to see, as the Light Side parity won't propagate any further and most of those Dark sub-candidates will get eliminated:

more sub-candidates: Show

gem04.png (76.65 KiB) Viewed 1004 times

Then we add a few more Dark Side super-candidates and get our first three trap eliminations almost simultaneously:

first eliminations: Show

gem05.png (79.92 KiB) Viewed 1004 times

The 8s in r14c3 see both the dark green (super) 8r1c9 or 8r4c8 as well as the light green (super) 8r9c3, so they're marked as victims. Similarly the 5r8c4 sees the light blue (par) 4 in its cell and the dark green (super) 5r2c4. These can be easily written as AICs:

(8)r9c3 = (8-4)r9c2 = (478)r1c259 - r56c9 = (8)r4c8 => -8 r14c3

(5=74)b2p42 - r1c2 = r9c2 - r8c1 = (4)r8c4 => -5 r8c4

--

Here the coloring is progressed almost as far as it goes:

more eliminations: Show

gem06.png (97.44 KiB) Viewed 1004 times

There are now three more eliminations: 1r9c23 and 5r9c3. Can everyone already see why?

If not, it's because of the light blue (par) 4r9c2 and the light green (super) 8r9c3 as well as the dark green (super) 1r9c7 and 5r3c3. Btw, anyone is most welcome to write chains for those eliminations! (I haven't even tried.)

There's also something a bit more interesting available, but we'll get to that in the next part. Hint: look at column 2.

[eleven]

Yes, you didn't understand the interest of theorem 4, but I probably took a bad example to see its interest.
Contrary to what you suggest about SpAce in another comment, there is no coincidence in my choices. I chose the pair of 4s from block 7 because the two tracks are conjuguated (theorem 1 part 2) and because the simple observation of the puzzle shows that one of the two tracks (the blue one) will develop well. From then on, it will be used (theorem 4 part 3) as a support for any track opposite to the other track (yellow). There is no longer any left, with the observation to choose the start of the opposite track carefully. This is obviously the 1 or 2 of r8c4.

I neither understand your theorem nor, what it is for. For this solution you don't need it at all. If you leave out the track steps, it is straightforward guessing.

I give you a sample in this puzzle:
I choose the strong link 1r5c56 for guessing (no coincidence: more candidates than the 4 in b7, which would be eliminated if one turns out to be wrong).
The first one leads nowhere, the second to the same grid as 4r8c1. And then you can take ANY remaining 2 digit cell (there are 16) to continue the guessing process. One will lead to a contradiction, the other to the solution.
This is completeley independant of the "opposite path".

It's not what you or SpAce wanted, but if you accept it as solution path, you accept that obvious guessing procedure too.


Some remarks:

NONE of the commonly accepted solving techniques uses (educated or not) guessing.
If you solve a puzzle with non-uniqueness techniques, you also have proved, that the puzzle has a unique solution.
If you solve it using uniqueness techniques, you have shown on the way, that - if the puzzle is unique - all other but the solution candidates must be false.

Here you have the situation, that you arrive at a solution, but you have not shown on the way, that other candidates must be false. Only when you are finished, you can derive it, if the puzzle was guaranteed to be unique.

If you allow guessing, someone can point to a backdoor candidate of a very hard puzzle, and tell you, that it solves quite simple. It leads to a solution, and if the puzzle is unique, it is the only possible.
Of course there can be more or less educated guesses, but this is a grey, undefined zone (there were long discussions about them).

If a solution technique uses such guesses, this should be noted at the very beginning (like uniqueness requirement is always noted for uniqueness techniques), because it is a basic difference to all the others.
Be sure, that with such a statement the technique is of no interest anymore for many solvers, and they would be very disappointed, if it turns out after spending much time to understand it.

[SpAce]

GEM Demonstration with Hodoku, Part 3/4

5. Loop & Par promotion

As I already said in the first part, a sub-candidate gets promoted to a par-candidate if it would also get colored as a super-candidate (indicating a closed loop). Here we have that kind of a situation. In the image below it's already resolved, though, so see the last pic in the previous post for the situation before.

loop promotion: Show

gem07.png (101.14 KiB) Viewed 995 times

In column 2 we have four candidates of 5s, and three of them were (and are) Light subs and one (r9c2) was a Dark sub. If the last one had been uncolored it could have been graded a super-candidate because all the others in that column were Light subs. However, it was already a Dark sub-candidate. It could thus be promoted to a Dark par candidate because of a closed loop.

It also means that the previously Dark red 8r9c2 got eliminated, which in turn made the 8r9c3 a placement (cyan) with some additional eliminations along the column 3 and its cell. We also got a new Dark super-candidate 5r8c9.

That concludes the basic GEM part.

--

6. Nested coloring

After the previous step, the coloring doesn't progress any further with normal methods. However, with Robert's new trick we can do some more damage. He already demonstrated one way to do it, and I think the GEM coloring makes it clearer why it works. If you look at the previous image, there are only two Dark sub-candidates left, both in r8c4. If we assume either one true it means that the rest of the Dark coloring can (must) be assumed true as well. That's potentially a big help.

For example, we originally had six candidates of 7 in box 4, but now we only have three left within the Dark parity. That makes it much easier to look for any hidden logic within the surviving candidates, because all the Dark blue and Dark green candidates can be considered placements and the Light red candidates as eliminated. For example, if we want to look for a direct contradiction for say 2r8c4, like Robert did, we can build an easy Nishio just by looking at the colored grid:

(2)r8c4 - (2=1)r8c3 - (1=7*)r2c3 - r2c7 = (7)r5c7 -> -7 r5c12,*r6c3 (contradiction, no 7s in box 4) => -2 r8c4

What exactly did that just prove? In fact, it only proved that IF the Dark parity were true, then we could eliminate 2r8c4. But we don't know yet that the Dark parity is true! So how come we can actually eliminate it? Because it's already colored Dark red. It means that it would get eliminated also if the Light parity were true, so now we know that it dies either way. We could not do the same trick for a random uncolored candidate.

However, we can also arrive at the same conclusion with other ways, instead of looking for a direct contradiction which doesn't seem very elegant. For example, it's rather easy to look at the uncolored candidates and see that there's a Kite or a Skyscraper in 7s, which would "eliminate" 7r2c3. However, that is not a real elimination because it only happens within the Dark parity. Yet it does mean that 7r2c3 can be marked as a Light red sub-candidate -- which would conclude our coloring and eliminate the 2r8c4 the normal way!

Or, we can do that with an actual nested coloring. Since we didn't use any group colorings, we have one color pair left (dark and light "yellow"). Let's do a nested Simple Coloring on the 7s with them:

nested simple coloring: Show

gem08_sc.png (110.02 KiB) Viewed 995 times

It's easy to see that the light yellow nested-parity produces a contradiction (two in box 1 and row 2), so all of those light yellow 7s can be "eliminated", i.e. colored light red, and the dark yellow 7s can be turned into dark greens, which again concludes our business.

Or, we could do an even more elaborate nested 3D Medusa coloring (would make more sense in a more complicated situation):

nested 3d medusa: Show

gem09_md.png (110.41 KiB) Viewed 995 times

Again, we have the same and some other coloring contradictions around, so the light yellow candidates can be switch to light red, and the dark yellows into greens. Not much left to do after that.

[SpAce]

GEM Demonstration with Hodoku, Part 4/4

7. Final remarks

So, any of the previously mentioned methods (except for Nishio) should conclude the coloring by bringing us here:

almost last: Show

gem10.png (106.88 KiB) Viewed 990 times

Now we can see that the Dark red 2r8c4 is flanked by two Dark green 2s, which means it can be eliminated. The end result is the same as with the direct Nishio contradiction, but I kind of prefer this approach.

The final state of the coloring:

conclusion: Show

gem11.png (106.9 KiB) Viewed 990 times

Now... the question is what to do with that. It shows that the Dark parity produced a solution with a little help (I'd call it an almost backdoor), and the Light one didn't get even started. Not very satisfactory to me, as it's not really different from guessing. Personally I'd take that one proved placement and the eliminations, and get back to the drawing board with a different coloring. (Like I did when I actually solved this puzzle, though it was mostly because I never got this far with the first coloring round.)

That said, I'd very much like to see another example of TDP in action!

[eleven]

I really tried to follow to the end, but my eyes can't stand that.
And your's seem to have missed the dark green single 5 in r9c2.

[Mauriès Robert]

Hello Eleven.
I think my poor English complicates our communication, I'm sorry.

I neither understand your theorem nor, what it is for. For this solution you don't need it at all. If you leave out the track steps, it is straightforward guessing.

The example I have chosen to explain this theorem is not good, I agree. So I will give you another example at the end of this message.

If you allow guessing, someone can point to a backdoor candidate of a very hard puzzle, and tell you, that it solves quite simple. It leads to a solution, and if the puzzle is unique, it is the only possible.
Of course there can be more or less educated guesses, but this is a grey, undefined zone (there were long discussions about them).

If a solution technique uses such guesses, this should be noted at the very beginning (like uniqueness requirement is always noted for uniqueness techniques), because it is a basic difference to all the others.
Be sure, that with such a statement the technique is of no interest anymore for many solvers, and they would be very disappointed, if it turns out after spending much time to understand it.

Are you saying that the TDP, through what you have seen, seems to you to use the riddle ?

Without waiting for your answer, I would like to tell you that in a puzzle every result found by an advanced technique (except perhaps the MSLS) can be found by the TDP. It's the opposite of the riddle, I think.

Concerning the problem of the uniqueness of the solution found, I will talk about it later on, hoping to provide you with answers.

Here is the example I announced earlier.

G = ..82.......6....3.21..56.8.9..84....7..6.9..8....75..2...58..97.4....8.......16..

After reducing the puzzle with the basic techniques (TB), I choose the pair 3r3 to build two conjugated tracks.
Tracks P(3r3c3) and P(3r3c4) are conjugated because P'(3r3c34) is obviously invalid.
P(3r3c3) ={3r3c3, 8r6c2, 5r9c2, 8r9c1,...}.
P(3r3c4) ={3r3c4, 1r6c4,...} contains the set 3r6c123.
As a result we can eliminate 3r45c3 which sees 3r3c3 and 3r6c123.
This is equivalent to a Finned X-Wing on all 3.

We can also eliminate 3r9c1 because P(3r9c1) is invalid in block b7. This is equivalent to an ALS-XZ.
This is to show you that we can do with TIP, the same as with advanced techniques.

But the subject is theorem 4.

The tracks P(3r3c3) and P(3r3c4) are blocked in development. To unlock I will consider another pair, the one in box r7c6, 4r7c6 and the set 23r7c6. As you say elsewhere, necessarily P(4r7c6) or P(23r7c6) is valid and the other is invalid, because these two tracks are conjugated. So I'm going to build them.
P(4r7c6)={4r7c8,...}
P(23r7c6)=P(2r7r6)∩P(3r7r6), so I build separately P(2r7r6) and P(3r7r6).
To make it easier to explain, I mark all these tracks with colors on the puzzle.
P(3r3c3) in yellow, P(3r3c4) in blue, P(2r7r6) in green and P(3r7r6) in purple.



As can be seen, the two tracks P(2r7r6) green and P(3r7r6) purple are opposed to the yellow track P(3r3c3) by the 5. so according to theorem 4 TDP part 3, the candidates of the blue track P(3r3c4) are candidates of the green and purple tracks, therefore are candidates of track P(23r7c6).
Thanks to this I can develop P(23r7c6) which leads to a contradiction ( I'll let you check it out ).

Finally, 23r7c6 can be eliminated, 4r7c6 is the solution and the blue track can be expanded as shown in the following figure.
Several eliminations are then possible (candidate crossed out in red) and two candidates 8 are solutions.



Of course, I can continue until I completely solve the puzzle, but I'd rather wait for your reaction !

Sincerely
Robert

[Mauriès Robert]

Hello, SpAce,

It's a big article you did on GEM, it will take me time to read and understand everything.

That said, I'd very much like to see another example of TDP in action!

You can already see the example of resolution I made in the message for Eleven.

Sincerely
Robert

[SpAce]

Hi Robert,

It's a big article you did on GEM, it will take me time to read and understand everything.

I completely understand. It's the same for me with your stuff.

The GEM intro turned out to be bigger than I thought, but I'm sure you see why it couldn't really be explained in much less either. However, I do regret that it's taking so much space (no pun intended) in your thread. If you want, I can ask the admins to move it out, or I can hide the text too. Whatever you wish. Nevertheless, I still think it's quite related to your topic, and I'm hoping we could find some synergies from the slightly different approaches.

You can already see the example of resolution I made in the message for Eleven.

Yes, that's great! I'll dig into it later.

[SpAce]

I really tried to follow to the end, but my eyes can't stand that.
And your's seem to have missed the dark green single 5 in r9c2.

Hmm, my eyes still don't see what you're talking about. Which image? Are you saying there is a green 5r9c2 (and shouldn't) or that there isn't and there should? In any case there shouldn't be. In parts 1 and 2 it was dark red, and it turned dark blue between parts 2 and 3 (hinted at the end of part 2, and explained at the beginning of part 3). Then it should have remained that way. The only problem I see is that the dark blue looks too much like the dark grey used for victims.

[SpAce]

Hi Robert,

A couple of observations about your latest puzzle.

We can also eliminate 3r9c1 because P(3r9c1) is invalid in block b7. This is equivalent to an ALS-XZ.
This is to show you that we can do with TIP, the same as with advanced techniques.

That elimination is certainly valid, and relatively easily seen as an ALS-XZ, but I don't see how it's related to TDP. What part of the system did you use to see that?

But the subject is theorem 4.
...
The tracks P(3r3c3) and P(3r3c4) are blocked in development.

Yes, but I think you missed one elimination: -1 r8c3. The 3r3c3 causes a hidden pair (79)r78c3 and 3r3c4 gives a pointing pair 1r45c3, which together eliminate it.

To unlock I will consider another pair, the one in box cell r7c6, 4r7c6 and the set 23r7c6.

To make communication easier, I suggest you use "cell". "Box" means the same as "block" here.

Anyway, what made you choose that cell? I can't see an obvious reason beforehand to target it specifically, though it turns out to be helpful.

As can be seen, the two tracks P(2r7r6) green and P(3r7r6) purple are opposed to the yellow track P(3r3c3) by the 5. so according to theorem 4 TDP part 3, the candidates of the blue track P(3r3c4) are candidates of the green and purple tracks, therefore are candidates of track P(23r7c6).

In my GEM coloring the 2r7c6 is already a sub-candidate in the 3r3c4 parity (i.e. your blue track), because 3r3c3 causes a pointing pair 2r7c23 (due to the same hidden pair that eliminated 1r8c3). So, no need for the green track for me.

Below is my coloring up to this point. Note the "yellow" used for group nodes.

gem, grouped: Show

gem12_grouped.png (72.8 KiB) Viewed 952 times

On the other hand, the purple track does establish that 3r7c6 is also a sub-candidate of the same parity. This gives us an intermediate result that you've skipped: the 4r7c6 can be made a super-candidate in the 3r3c3 parity, i.e. added to your P(3r3c3).

4_as_super: Show

gem13_4.png (74.64 KiB) Viewed 952 times

Do you agree? I thought at first that it doesn't help us much, but actually it does if we look closely. It gives us a UR Type 2 in (79+3)r89c34 which eliminates 3r6c4! In fact, if we continue the coloring it gives us the solution (+3r3c3), though not in the way I would like (same reason as before):

solution: Show

gem15_solution.png (88.65 KiB) Viewed 949 times

Thanks to this I can develop P(23r7c6) which leads to a contradiction ( I'll let you check it out ).

Not a very obvious and quickly achieved contradiction, I think. This is the part that I don't necessarily like in your system anyway, as it seems to depend heavily on nested T&E as a secondary method to the binary coloring. Finding direct contradictions may be efficient, but not exactly elegant. That's why I'd rather look for other ways, like the previous UR, to continue the coloring.

The part I do like is how the established coloring is used to help even when it gets stuck, but it's still T&E if done your way. In fact, in this case the same result (+4r7c6) could be achieved directly without using the coloring (i.e. a contradiction for 23r47c6 is found with basic methods even if the 3r3c4 is not involved). I think there are good insights in this system, but maybe they could be used in slightly different ways to get the same results more elegantly.

[Mauriès Robert]

Hi SpAce,

Thank you for this feedback. Here are my answers.

That elimination is certainly valid, and relatively easily seen as an ALS-XZ, but I don't see how it's related to TDP. What part of the system did you use to see that?

I am referring to the TDP Part 2 property (P2) which states that if P(E) is invalid, all E candidates can be eliminated.

For the other remarks, you're right, going fast I didn't see the possible elimination of 1r8c3, and 2r7c34 jaune which would have saved me some work afterwards by considering only the 34r7c6 pair. But my goal was only to show Eleven how I work with the opposite tracks.
You also say:

Not a very obvious and quickly achieved contradiction, I think. This is the part that I don't necessarily like in your system anyway, as it seems to depend heavily on nested T&E as a secondary method to the binary coloring.

I find this rather simplistic, because for me T&E is like taking a candidate for no specific reason as true and seeing what it looks like.
I always choose the one track with a predefined reason and not to "see".
But then if TDP is hidden T&E, I think other similar techniques are too. There is always a chance when you choose to try a chain or loop without knowing if it will produce a result.
Moreover it is a false problem, because all the techniques are demonstrated by making the T&E, so that when they are used we make the T&E without remembering it!

Finally, I would like to add that I also know how to use UR to show the invalidity of a track, but often I don't do it because for me it's not a acceptable technique if we want to prove that the grid has only one solution.
I will come back to this subject later.

But I hope that our exchanges will bring some positive results.

Sincerely
Robert

[eleven]

Hmm, my eyes still don't see what you're talking about. Which image?

I don't quite understand your method.
In the "first eliminations" picture you can color 9r1c1 green, then (single in box 4) 9r4c3, 1r5c5 and so on, until you have all the greens in "more eliminations".
Here 5r9c2 is the only remaining 5 in box 7, and the 8r9c3 the only 8.
This already gives all eliminations in that picture.

[eleven]

Of course, I can continue until I completely solve the puzzle, but I'd rather wait for your reaction !

Hi Robert,

I see no problem, that your method is correct and efficient - if the starting candidates are well selected. In this case it probably would have been easier, if you had tried 4r7c7 before, which leads to a contradiction. But who knows it in forward ?

I don't solve such hard puzzles for a long time now. It needs a lot of time and techniques like yours - and a lot of rubber, if you would do it on paper.
(And you can be sure, that i would stop with a solution found, rather than trying to disprove all other candidates.)
But i have a basic problem to see my way through markings or colors of 2 or more paths.