The New Sudoku Players' Forum

[David P Bird]

.
1 Preamble

Graded Equivalence Marking was conceived as an idea in 2006 and I have been using it ever since on a spreadsheet helper. It's more elaborate than other marking systems and allows multiple alternating chains based on the same opening premise to be followed simultaneously. The result is a map of the candidates that must be true, might be true and must be false under two possible conditions. This may then show multiple elimination possibilities stemming from the same opening premise, allowing the most significant ones to be made first.

As a tool it has proved very useful for exploring the different paths available for solving a puzzle and extending the inferences that can be made using unbranched AICs, subjects that have been of particular interest to me.

Below, for the record, I describe the system as I currently use it together with a revised symbol set which has been modified to avoid clashes with the weak and strong link symbols that are now almost universally used in our notations.

David P Bird

TAGdpbGEM

[David P Bird]

.
2. GEM Description

Graded Equivalence Marks allow alternating inferences to be marked on a grid using two parities each with three regular grades of equivalence marks. Starting from either a single opening link or a set of conjugate ones it allows the network different pincer chains to be marked and followed to locate possible candidate eliminations. From any eliminated candidate the grade marks then provide the means to track the inferences involved back to the seed nodes enabling the deduction to be notated either as an AIC or an AI net.

Equivalence Grades and their Revised Symbols
In the pencil-marked grid grade marks are added as suffixes to the digits as and when their equivalence to one of the seed nodes is determined. Considering parities 1 and 2 (p' and p") to represent which of the seed nodes is considered true, the grades are split into two p' and p" families.

Code: Select all

Equivalence  Parity 1  Parity 2  At own      At other    Comment
  Grade       Mark      Mark     Parity      Parity
   
Par            0†        0‡       True        False      Identifies conjugate candidates
Super          0'        0"       True        Unknown    Must be true at own parity
Sub            0.        0:       Unknown     False      Possibly true at own parity
Victim         0!        0!         -           -        Candidates that can be eliminated
                                                                     
Optional                                                           
ParGroup       0¹        0²       Group True  All False  Par-graded group nodes       
SuperGroup     0,        0;       Group True  Unknown    Super-graded group nodes

Marking Rules
Linked nodes are always be given marks from opposite parity sets
From par nodes weakly linked nodes are sub-graded and truly conjugate* nodes are par-graded.
From super nodes only weak links can be followed when the other nodes are sub-graded
From sub nodes only strong links can be followed when the other nodes are super-graded

When links from different chains would cause a candidate to be marked twice with opposite parity marks a deduction has been identified.
1) Opposite sub-grades - it is false and can be marked as a victim
2) Opposite super-grades – it is true and its peers can be marked as victims
3) Opposite sub- and super-grades – it is a par candidate and the two chains form a conjugate closed loop

* The internal strong links in most ANSs are not conjugate but 'strong-only' as they cannot be used as weak links.

Group nodes although easily handled by computer are very inconvenient for a manual marking system as members of the group may carry individual grade marks as well. However, using focus colouring for single digits on a helper program, it's easy to spot when one is needed to provide a bridge between graded candidates. Consequently they are considered optional as in use they serve only as memory aids. This topic is discussed later.

The new 0† and 0‡ symbols for par grades are a rather unsatisfactory compromise as they aren't available on the keyboard. However they can be achieved in MSWord and Excel using auto-correct as can the optional 0¹ & 0² marks for par-graded group nodes.

Benefits
GEM can be used both for quick explorations, which is the best way to become familiar with it, or for systematic investigations when every available link is followed. Once the significance of the grade marks is appreciated their use becomes self-evident in the vast majority of cases. The increased complexity of the system gives the following pay-backs:
1) A coherent network of chains stemming from the set of conjugate seed nodes can be mapped.
2) Nodes that must be true or can't be true at each parity are identified giving a good appreciation of a puzzle's structure.
3) The direction followed by the pincer segments marked with super- and sub-grades is clear.
4) All possible eliminations are shown allowing the most significant ones to be prioritised.
5) The marking are persistent and as the grid is reduced they can be edited and extended.
6) The user can choose whether to allow branched deductions or not.
.

[David P Bird]

.
3. Example GEM Mark-ups

Example 1 Single Digit Mark-Up

.6......5....6....8....21.418.9.......3.4.5.......6.484.53....7....7....9......2.

Single Digit GEM.png (5.87 KiB) Viewed 2094 times

(2,)r6c13 = (2:)r56c2 - (2†)r7c2 = (2‡)r7c5 - (2.)r4c5 = (2")r4c7 => r6c57 <> 2

The conjugate digits in r7c2 & r7c5 were chosen as the seed candidates which appear in the middle of the chain with the † & ‡ grade marks.
Following the p" right hand segment of the chain, the weak links in c5 causes (2.) to be marked for r46c5 as these can only be true at p". Next, the strong link (2.)r4c5 = (2")r4c7 causes (2") to be marked as it must be true at p" - but at p' it could be either true or false.
For the p' left segment the weak link to (2:)r56c2 means they can only be true at p', from which the strong link to the group node (2,)r6c12 shows that one of these instances must be true at p'. This causes (2:)r6c457 being marked as only possibly true at p'. However the opposite (2.) grade has already been marked in r6c57, so these instances can never be true and their grades are changed to (2!) indicating they can be eliminated.
The other grade marks on the grid show that there are no other eliminations available.

Observing the various links on the grid, if they have candidates marked (2.) they come from the p' chain segment and with (2:) they come from p" one, so from any elimination it is possible to back-track two chain segments to the seed candidates where they will link to provide the elimination chain. However there may be a choice of paths.

Example 2 Multi Digit Mark-Up

Multi Digit GEM.png (22.23 KiB) Viewed 2094 times

(2†)r5c9 = (2‡)r4c7 – (2†)r4c5 = (2‡)r7c5 – (2†=1‡)r7c2 – (1.)r7c8 = (1")r5c8 => r5c9 <> 1 (singles to the end)

This is the full puzzle grid for the previous example after the two eliminations that were found have been made.
The previous grade markings for (2) have been updated and the starting conjugate set extended.
The paths starting with weak links from each of the par-graded nodes were then followed to grade the grid as fully as possible.

When the markings are taken to completion they show all eliminations arising from chains that include the links between the conjugate nodes considering them either as weak or strong. Here seven eliminations are revealed of which (1!)r5c9 is the most significant as it leaves (1)r5c8 as a single. Because multiple chains were being followed simultaneously, the elimination chain needs to be picked out. In this case the p" segment is a single link (2†-1:)r5c9 so only the p' segment needs to be back-tracked from (1")r5c8, at the other end of the elimination chain. Once a digit with a conjugate grade is reached the conjugate seed chain then completes the connection.

The grid illustrates two points of detail regarding marking.
1) (4:)r8c4 & (4:)r9c4 have been marked which could lead (4')r1c4 being graded. However because these (4:)s seem to have been marked for different reasons this might need a branched path to achieve. If branching isn't acceptable then a check should be made to see if r89c4 is part of a pattern which allows them to be reached on a single chain. In this case they are as (2‡)r7c7 = (2†6-4:)AHS:r89c4 is available, so the grading could be extended. However this would need to be remembered or noted somewhere as if this segment is required to notate a deduction it might not be so obvious later.
2) (9,)r3c3 has been marked as being part of a group node (9,)r123c3 that must be true at p' but clearly this doesn't allow the companion (7) to be graded as which (9) will be true at p' isn't known. The 0, and 0; markings therefore have limited value and slow down grading by hand. Consequently they are considered optional memory and colouring aids as it's usually obvious when a group node is needed to provide a bridge.

Finally, before leaving this grid, note that the un-marked digits give a very good indication of the links yet to be explored.
.

[David P Bird]

.
4 Practical Considerations

In Use
GEM was designed for use in a spreadsheet helper which supports various colouring schemes to help identify different patterns. Without colouring a fully graded grid could overload the user with the information available, so for GEM grids the spreadsheet works with a single focus digit at a time. It greys the cells missing the focus digit and in the others it colours the digit's graded instances in different colours for the p' and p" marks. This makes marking the grades for a digit at a time easy, but for back-tracking it's slower as at each change of linking digit the focus digit needs to be changed.

Seed Conjugates
In a network of conjugately linked par nodes it is always possible to connect two opposite parity nodes with a linear AIC that starts and ends with strong links. So if AIC chains or nets that start with weak links from opposite parity nodes converge to show a candidate must be true or false, it will always be possible to construct chain or net to prove the deduction. As the AICs from the opposite parity par nodes are marked using different pairs of symbols, the direction they followed is known which helps identify the paths back to a pair of par nodes when the linear chain segment between them will complete the elimination chain.

There may be a choice of paths back from a deduction node to either the same par node or to different ones, allowing either the shortest or the simplest one to be notated. The bigger the conjugate net, the more options there will be.

For tough puzzles conjugate links may be scarce but then chains through a single link such as (a'=b") for a strong-only link in an ANS or (a.-b:) for two candidates in a multi-candidate cell with strong external links can be explored. It's therefore sensible to prioritise eliminations that will create new conjugate links to extend the starting net. When it appears no further progress can be made and a scan for patterns fails, it's time to consider what strong links in the puzzle have never been fully used and start mark-ups from those.

Marking Group Nodes
While users must follow the marking rules for single candidate nodes they are free to choose how to mark group node members according to their own needs as they only serve as reminders. In particular, for a candidate that could carry two grades, one from a direct link and the other from a group link, the grade from the direct link should be given priority. Usually one of the other group members will still be group graded and will continue to provide the reminder.

It is recommended that before any group node is marked, the need for it is checked by considering if there would be a more natural way of notating the bridging connection it provides, as there often is.

Code: Select all

 *----------*----------*----------*
 | -  -  1† | 1: 1: 1: | -  -  -  |
 | -  -  -  | -  -  -  | 1  -  -  |
 | -  1‡ -  | -  1† -  | -  -  -  |
 *----------*----------*----------* 

(1)r1c456 in this grid is a group node that could be par-graded, but there would no benefit from this as (1†)r1c3 ^ (1‡)r3c2 ^ (1†)r3c5 is available. Therefore the node has been sub-graded as these grade marks are stronger and can be used individually to show further links. In other circumstances before deciding how to mark a par group node, if there are multiple instances of the digit in the same house they should be sub-graded with the opposite grade first which should help reach a decision.

If (1)r3c1 existed in the grid then (1)r3c12 could be either graded as (1²) or (1:). If (1:) were used then when notating an elimination chain, the bridge from (1†)r1c3 to (1†)r3c5 should be apparent even if that decision isn't remembered.

Code: Select all

 *----------*----------*----------*
 | -  -  1. | 1; 1; 1; | -  -  -  |
 | 1  1  -  | -  1. -  | 1  1  -  |
 | 1  1  -  | -  1. -  | -  1  1  |
 *----------*----------*----------*

In this example of an empty rectangle with a super-group node, it is more a matter of personal style to decide how the candidates in the super group (1)r1c456 should be marked. As the bridge between (1.)r1c3 and (1.)r3c5 is easy to see, an experienced user may opt to save time and leave the group node unmarked.

Fortunately, as the members of a sub-graded group node can be considered false either individually or in combination, there is no need for any special marking for sub-graded group nodes.

Branched Paths
When all the candidates for a digit in a mini-line carry the same sub-grade if net methods are acceptable any strong link from this group can be followed. Otherwise before the link can be used, a check should be made to see if either they all link to the same par- or super-graded candidate, or if a pattern exists that would allow these candidates to be marked together. Such a case has already been illustrated in example 2.

However branched paths can also be followed when different chains have caused all but one of the set of [candidates in a cell] or [instances of a digit in a house] carry the same sub-grade mark so allowing the last one to be super-graded. It can even happen that they all carry the same parity sub-grade which would prove by contradiction that that parity must be the true one.

This makes GEM marking a powerful way to find net-based solutions. For purists who won't use nets, such tell-tale markings will often highlight key target eliminations to make to arrive at a more elegant solution.

Marking Order
The different ALSs chains away from the par-graded candidates can be graded in any order so it is possible to mark-up the links for individual chains, digits, or box bands that lead an investigation in the chosen direction. However the resultant markings won't always be the same and may depend on the order used. A typical example of this is when two chain legs meet to form a closed loop when the meeting point will depend on the how far along each leg the nodes were previously graded. For elimination chains this can result in different victim candidates being identified when they are equivalent so that if one was eliminated the elimination of the other would follow. In these cases it's possible to adjust the notation to suit the player's preference.

Marking Pattern Based Inferences
As for simpler marking systems, while GEM grading will successfully identify eliminations for chain based patterns, that's as far as it goes. It is up to the user to spot a pattern that provides a non-chain inference that can be used to extend the grade markings, after which GEM will display the outcome. However, to back-track a path through a derived inference, its source must be remembered. So when a marked grid contains several of them it's worth jotting them down on a scratch pad.

These other patterns can either be spotted 'on the fly' as the inferences are being followed or by making a scan for them after the candidates linked by simple chains have been graded. Most common are ANS/AHS combinations in a house where the tell-tale sign to look out for is a floating candidate that must be false in an ANS at one parity; this will allow the external instances of the other floating candidates that see those in the ANS to be marked false at the same parity as they must be true in the ANS.

When an ANS contains exactly two floating candidates it is also qualifies as being AHS and the internal link between them becomes conjugate. When this is recognised it provides a way to extend the net of par graded digits.
| <3> 1†4‡ <7> | 2"4. 2.4.5‡ 68 | 689 1:5†6:9: 1:689 |
In this row (1†4‡)c2 have been par-graded. Cells (245)c45 now hold a par group node for (4) so, as (4) and (5) are conjugate, (5) can be par-graded too.

This sub-grid shows that an eye for chain based patterns is still needed when they exist in their Almost form.

Code: Select all

 *-------------------*-------------------*-------------------*
 | 234:  *     *     | -     4'7:  -     | -     -     13    |
 | -     -     -     | -     -     -     | -     -     -     |
 | -     -     12    | -     -     -     | *     *     *     |
 *-------------------*-------------------*-------------------*

There is an Almost X-Y wing (4)r1c1 = (123)XYWing:r1c19,r3c3 - (1)r1c23,r3c789
As (4:) r1c1 is false at p' it means the (1:) could be marked in the starred cells as at p' it would be eliminated by the wing. The GEM marking rules could only produce these gradings if another chain from the seed candidates enabled a further candidate in r1c1 to be graded, which isn't guaranteed.

Partial and Complete Mark-ups
GEM grading can be used either to quickly follow-up individual observations or to systematically follow all the inferences available stemming from a linked set of par-graded candidates.

The partial mark-up approach is useful when a particular weakness has been spotted in a puzzle that has the potential to open it up. In this case there is no point in following inference trails away from this until later when hopefully more paths will be available.

If the systematic approach is taken, initially it will be impossible for the pincers from one set of par candidates to completely cover all the cells and different starting points will produce different clusters grade marks and of possible eliminations - some of which will be insignificant. If a computer is being used then alternative mark-ups can be made, evaluated, and saved before deciding which eliminations to prioritise*. Having made some eliminations from one of the mark-ups another one can be recalled and the grade marks revised to reflect any changes made. All the other gradings will be unaffected (an advantage of using AICs rather than forcing chains). It is only when the set of par candidates used in a mark-up has been resolved that that mark-up will serve no further purpose.

The earlier examples 1 & 2 illustrated a typical mixed strategy being used where a single digit mark-up for (2) was extended to a complete mark-up once the set of par graded nodes had been extended.

* Obviously, until a candidate marked as a victim is actually eliminated, no inference should be used that depends on its absence.

Computerising GEM
Clearly it would be possible to utilise the GEM approach in a chain based solver/helper when the limitations regarding grading group nodes in a limited work space could be overcome. However, as the only programming I do nowadays is coding Sudoku worksheet functions, this isn't something that I'm contemplating.
.