SEclone tagging basics
Starting with “aligned pair exclusion” solving technique, the program use the “tagging” process of my solver adjusted to Sudoku Explainer specifications.
The first adjustment to comply with SE is that no group of candidates exist (at least not directly), so we only consider single candidates in the tagging.
In the tagging process, all candidates linked thru a strong link chain are forming a “layer”.
A layer is reduced to 2 “tags”, one for each set of candidates simultaneously “in” or “out” of the solution.
These tags are binary indicators (printed as lower case upper case letters eg a;A) such as a=A^1.
Tags 0;1 are unused and show untagged candidates.
Tagging core process
The core of the process in the tagging procedure is the table of “primary weak links.”
Primary weak links are shown in 2 ways:
A table storing one occurrence of each couple of tags for which a weak link has been found;
A bit field table in which the primary link field is shown as an implication.
If “a” - “b” then a -> B and b-> A
In the bit field dedicated to “a”, “B” is set to 1
In the bit field dedicated to “b”, “A” is set to 1.
The primary table is expanded to find all chains in a very simple way
If “x” -> “y” then “x” -> “bit field x” | “ bit field y”
Usually, a small number of iterations gives the final table where all loop and discontinued loop can be found.
Extending the specifications
To add new properties, as in our example induced locked pairs, induced alignment …, the general way is to make a “vicinity analysis”, detecting all local conditions creating the property and generating a new set of weak links.
In my solver, I do this partially, and I also generate new strong links with groups. In SE clone, only the generation of new weak links will be authorized.
Nested chains is quite another story and will be considered in due time
Sets of candidates and derived weak links
The next feature common to SE and to my solver is the use of sets of candidates.
In SE, a set of candidates can be
All candidates of a cell
All candidates of a digit in a row; column; box.
They are shown in the program as a set of tags.
Such a set (choice in my program) has 2 main uses
If a tag is in conflict with all tags of a set, then that tag is not valid
If a tag “a” is in conflict with all tags of a set but one “b”, then we have “a” -> “b”, a new implication, also called a new derived weak link if shown as “a” - “B”.
Several iterations can be made in derivation till the moment where nothing more appear.
If no more derivation comes, the process is locked.
Cloning SE, we will have to play on several parameters to be in the right condition of a specific step.
Typical lay out for a step in the search of chains
The typical process will be
Collect all strong links (and “equivalence links” if relevant x <-> y )
Switch to tagging
Collect weak links and expand as required in the context
(here some derivations should be made in general)
Look for results
What takes place in layers
A problem, to clone Sudoku Explainer using tagging comes from the layers.
Generally speaking, part of the chains are included in specific layers,
Sometimes, especially when the solving path is close to the end, a layer has all the chain included in it.
Both cases have to be seen carefully, especially to come to the length as defined in SE rating.
It will be easy to detect if eliminations or “nice loops” have been found. It will be slightly more difficult to compute the length.
When we reach a quasi BUG situation, we usually have a very small number of layers, but many loop in the main ones. Even if an action has been proven, the process to identify the shortest loop must still be written with care.
Here is also a processing time issue, especially in “Y” mode. To overcome the difficulty, a reasonable limit has been set in the overall authorized length.
Computing the length of a chain/loop
No surprise, we need 2 interleaved process
One coming from the tags giving the mains bridges between layers
One to fill the gap within a layer.
The first process is not needed if all takes place within a layer, the second one is not needed in “Y” mode since we have no layer of more than one strong link.
As we store only one bridge (weak link) per couple of tags. The code had to be revisited to find the shortest path. This must be done with care knowing that at the end of each game we can end with many bi value cells that could lead to a very high number of paths .
As far as performances are concerned, out of the problem mentioned earlier at the end of a game, there is no key issue looking for the shortest chain. We are in a situation where eliminations have been established, so, at best, .5/1000 of the possible starts from one specific candidate.