http://pagesperso-orange.fr/gpenet/
a first draft can be seen, but the last topics are still in that thread;
Full tagging is for the time being one among few process that can crack all known puzzles without T&E The logic applied is very simple
end of edit
"full tagging" is a powerful way to approach puzzle solving excluding Trial&Error processing.
"Full tagging" belongs to the multi-colouring family.
The process is highly progressive, and can be divided (up to now) in three levels.
- Code: Select all
level 1 : more or less equivalent to MEDUSA 3D. Major differences are :
- No use of forcing chains,
- extended to groups,
- intensive use of Alternate Chains.
level 2
- expanding strong links and weak links thru ALS and their counterpart which I call "Almost Cells".
- looking for multi-chains starting from an Almost Cell and killing candidates
level 3 (looping process as long as you can expand)
- expanding weak links thru multi-chains starting from an Almost Cell
a fourth level (which one is relevant?) should be implemented to solve the small number of resisting puzzles.
One simple way to evaluate increasing difficulty is to consider processing time.
- level one lasts 0.5 to 1 second.
- entering level 2 leads normally to 1 to 4 seconds processing.
- With level 3, processing time can exceed 40 seconds (maximum seen 68 seconds).
Before entering these levels, the process is standard :
- locked sets, "Fishes" XWING..., XYWing, XYZwing and Unique Rectangle (basic cases).
I never tried to enter in derived patterns for "fishes" ...
Let's start with level one which is very simple and dedicated to "manual processing".
The stuff used in level one is limited to "bi values":
- cells containing two candidates .
- twin digits within an object
. Object : a Row, a Column or a Box (3x3)
. twin digits : only two candidates for that digit in the object.
This stuff is forming "strong links". (see here below)
Group extension (not included in MEDUSA 3D) is in fact very simple.
a group is any useful set of candidates of a specific digit inside the same object.
- wider definitions of groups can be done. This process is limited to groups of one digit in one object.
- in level one groups are limited to sets belonging to two objects (row/box, column/box)
From now on, within level one, to make it simple, a 'group' is any valid (not empty) combination (digit/row/box) or (digit/column/box).
A candidate is a 'group' of one member.
Like twin digits, twin 'groups' are forming "strong links".
- Code: Select all
- Strong Link : An exclusive couple of 'group's having the following properties
- if one is part of the solution, the other is not,
- at least one is part of the solution.
- Weak link : only the first statement of the previous definition is valid.
as a matter of fact, a strong link can replace a weak link in a chain (see below)
If strong link can be "chained" we create a "layer".
Chaining all available stuff lead to several layers. The smallest layer is limited to one strong link.
Tagging of a "strong link" is equivalent to applying polarity +/- to both 'group's of the link.
In a chain parity switch from + to - along the chain which become +/-/+/- ...
If several chains (implying loops in the layer) can lead from one 'group' to another one, parity is always the same using exclusively strong links. This can be demonstrated for any valid puzzle.
Each layer receive a couple of tags specific to that layer.
. Internally a couple of odd and even numbers,
. In writing
- when the number of layers is small enough, each layer receives a letter upper and lower case.
- Later on, to stick to 'one character tag' as long as possible, I use European accentuation which could be a problem for non European users.
- and finally one letter with a prefix £ $ & .... .
In fact, this applies generally to layers containing only one strong link.
Then, in writing I try to use directly the group in the chain, shortcutting the underlying tag.
In MEDUSA 3D (at least when I visited the web site), layers are connected thru forcing chains.
Here, we are connecting layers exclusively thru "weak links" which is fully compatible with well known "Alternate chains".
An "Alternate chain" is a sequence "strong link" "weak link" "strong link" ....
In such a chain, any weak link can be in fact a strong link.
In writing the sequence is .._../.._..
where (_) shows a strong link and (/) shows a weak link (..) shows the appropriate group.
Reduced to tags, an alternate chain should be something as :
A/a_A/B_b/B_b/C or A_a_A/B_b_B_b/C
here
- two "weak links" have been identified : A/B and b/C
- two "strong links" have been use in place of two "weak links".
Our "canonized form" for such a chain will be : [] AB bC
In such a chain, both end are defining a 'distant weak link'. [AC] is a weak link.
One remark to answer a question raised by Ronk.
. in Canonized form, weak links and strong links are fully balanced.
. the list of weak link is necessary and sufficient to work out possible chains.
this is done sorting weak links in the appropriate way.(a kind of graph oriented structure)
We could also have the "canonic form" [] a _ AB bC _ c
In fact, we have full equivalence for action with the following logic rule :
=>If we have a "weak link" [AB] then we have a logic OR {ab}. (a, b or both)
I am using the combination
. []AB bC and
. [AC] implies {ac}.
We now have all necessary material to start clearing of the puzzle.
As I mentioned, clearing is done exclusively thru "alternate chains".
Tagging offers shortcuts, but one can rebuild the relevant chain.
Clearing happen within a layer or with "Alternate chains" crossing layers.
It can also be done out of "open Alternate chains" or out of "closed Alternate chains".
The concept of "open" or "closed" chain is easier to describe with chains crossing layers.
A closed chain would be of the form :
[] AB bC ... za known as "Nice loop"
[] AB bC ... zA , a conflicting loop clearing All 'A' tagged 'group's.
An open chain is any other chain eg: [] AB bc CD
Open chains appear only in level one. Later on, as all candidates will be tagged, all useful chains will be closed.
Open chains allow clearing thru processing of logical OR condition.
Here for example [] AB bc CD gives logical OR {}ad.
- Any pair of 'group's of the same digit tagged 'a' and 'd' respectively will work as XYWing ends (including all group extension).
- in addition if we have the following pattern (any object, here a row)
__ 2a+ ___ 5d+ (+ any other candidate(s))
. 5 can be cleared in the cell containing 2a
. 2 can be cleared in the cell containing 5d
. clearing is still valid in cell 2a with a 'group' for 5.
A) Within a layer
Chains within a layer are normally not shown. A specific pattern is known as "Turbot",
The rules for clearing are the following:
. if a tag appears twice in one object for exclusive 'group's, this tag is discarded.
(normally twice the tag in a cell or two 'group's of the same digit in the same object)
. If associated tags are fully complementary, candidates in excess are cleared
(eg: two associated tags in one cell with other candidates)
. and the "logical OR" is applied to pairs of 'groups' with associated tags.
B) With chains crossing layers.
Simple cases have been described as "Kites", Sky-scrappers", "Empty Rectangles"
. Priority is given to actions deriving from "Nice loops" and "Clearing chains"
. second priority is given to Weak link logical OR processing
. last priority is given to logical OR processing out of a chain.
These priorities refer to increasing difficulty in manual processing.
Last point to mention regarding level one is a specificity in a box.
Let's assume the following pattern. ( box 1 and digit 6)
6 6 6
6 - -
6 - -
In addition to 'group's 6(r1c1 r1c2 r1c3) and 6(r1c1 r2c1 r3c1), the program takes
groups 6(r1c1 r1c2 r1c3) and 6( r2c1 r3c1) in strong link,
groups 6(r1c1 r2c1 r3c1) and 6(r1c2 r1c3) in strong link as well.
This gives full compatibility with "Empty Rectangle" analysis.
This "level one" solves a lot of puzzles.
Second step
The second level is the most important to start solving resisting puzzles.
The third level, although time consuming is just a loop expanding "weak links"
In that level we introduce additional stuff and some logic.
The new stuff includes :
- Almost locked sets ALS ( with one digit in excess).
- Almost Cells : the complementary cells of an ALS in an object
- "Choices" , sets of tags with only one valid tag.
Let us start with an example.
This is r6 somewhere in a puzzle.
r6||12467 125 4567 |_ _ 45 |4567 _ 12467
- (r6c3 r6c6 r6c7) is an ALC containing digits 4567. One of these digits is not valid.
- Complementary cells (r6c1 r6c2 r6c9) is an "almost cell" (hereafter 'AC').
. Digits 1 and 2 are part of the solution,
. One among digits 4567 is valid.
digits 4567 are forming 'groups' in each entity. These 'group's will be tagged unless they are compulsory.
If we assume tags Bb,Cc,Dd,Ee are free, tagging could be
{4b 5c 6d 7e} for ALS and {4A 5B 6D 7E} for 'AC'.
In the process, this is reduced to {b c d e} and {B C D E}.
A cell is the simplest 'AC' (the counterpart of a cell is always an ALS).
A cell and an almost cell, both reduced to tags have the same properties in that process. Any pair of tags in an 'AC' is a weak link. That's why I chose the name 'AC'.
The set of tags representing a cell or an 'AC' is called a 'Choice'.
The general definition for a 'Choice' is :
"A set of tags in which one an only one tag is valid".
A 'Choice' can be materialised by a cell or an 'AC'. It can also be done combining 'group's of a digit in an object (no overlapping, all candidates included).
Any other way to define 'Choice's would be valid. In level two, we are limited to cells, 'AC' and "'group's of a digit".
If several cells have the same tag pattern, 'Choice's made out of these cells are identical for processing.
'Choice's play a key role in this process.
Lets consider another example, commonly found. Hereafter a puzzle after basic tagging.
It will be used later on to illustrate another topic; :
- Code: Select all
1||23a8b _____ 24t8B_ |3A46j 2p46_ ______ |______ ______ 2c6C
2||_____ 24u6c 247d__ |_____ 23H6C 2O34t_ |23A7D
3||23A7D 2c6C_ ______ |_____ _____ ______ |236w7d 23S6
4||_____ _____ 2e5f9g |5F7f_ 7g9G_ ______ |______ ______ 2E7e
5||2b8B_ 28b9K 25F9__ |45f7e _____ 3H49g_ |234___ 234V6C 23l6c7E
6||_____ _____ ______ |_____ 3h4H_ ______ |3H4h
7||_____ 248B_ 247G8b |3r47g _____ ______ |______ 234___ 2l3L
8||25i7d _____ 2479K_ |346J_ 7G9g_ 2q3A49 |45I6__ 23r46w
9||2i5I_ 249k_ ______ |_____ 2O46j 249K__ |245i6J
(r4c3 r5c3) is an ALS containing digits 259. As '5' is compulsory, one of two digits (2 9) have to be cleared.
(r4c3 r5c3) is also an AC. One of two digits (2 9) is valid.
(r1c3 r2c3 r7c3 r8c3) is as well AC and ALS.
9(r4c3 r5c3), in strong link with 9r8c3 is in fact a 'group' tagged 'k' ('group' tags are not shown in the print).
So :
. 2(r4c3 r5c3) must be tagged 'K',
. 2(r1c3 r2c3 r7c3 r8c3) must be tagged 'k'.
These (ALS/AC)s are an important tools to spread strong links. Very often, weaknesses of hard puzzles are found in (ALS/AC)s.
Another remark can be done regarding cells. As a cell is complementary to several ALS. In that process, any cell is fully tagged.
Consequently, any candidate is, in the process, replaced by the appropriate tag. (no more open chain is needed)
Before entering the process itself, let's introduce a new concept and some additional logic use in the tagging phase.
Merging layers :
When in the process two tags are proven to be simultaneously in and simultaneously out of the solution, they are identical. The two corresponding layers are merged.(the layer having the highest tags is merged in the other
And now two logical rules :
Let's consider two 'choice's {a,b,c} {a,b,d} (same tags but one). Then 'c' and 'd' are identical and can be merged.
It's easy to demonstrate, but the easiest way is to group the subset set of identical tags. The 'choice's has then the form {Xc} {Xd}.
As one tag and only one is valid ...
Our puzzle produces several cases. Let's take three.
1). 3r2c7-A 7r2c7-D 2r2c7 cell r2c7
. 3r3c1-A 7r3c1-D 2r3c1 cell r3c1
2r2c7 and 2r3c1 must have the same tag.
2). 2r2c9-c 2(r2c7 r3c7) 2r3c8
. 2r3c2-c 2(r3c1 r3c7) 2r3c8
2(r2c7 r3c7) and 2(r3c1 r3c7) must have the same tag.
3). 2(r2c2 r2c5 r2c6) 2r2c7 2r2c3
. 2(r1c1 r1c3 r2c2 r3c2) 2r3c1 2r2c3
2(r2c2 r2c5 r2c6) and 2(r1c1 r1c3 r2c2 r3c2) must have the same tag.
(don't forget we have seen that 2r2c7 and 2r3c1 have the same tag).
The second rule is requesting use of alternate chains.
Let's consider one 'choice' {a,b,c}. 'a' and 'b' are in weak link (directly or thru alternate chains) with 'd', 'c' is in weak link with 'D'.
Then 'c' and 'd' can be merged. Again, easy to demonstrate in the form {Xc}.
Normally, it should be possible to implement a tagging process avoiding merging of tags.
(No conflict can occur in the tagging procedure with a valid puzzle)
In my process, tagging of 'AC's,'ALS's is done starting from basic tagging.
This leads sometimes (generally in connection with ALS/AC of two tags) to merging of tags
To give a rough idea of increasing difficulty, in basic tagging, the number of tags is in the range of 30 to 80 (15 to 40 layers).
Introducing ALS, we are somewhere between 100 and 150 layers.
All tools used in basic tagging can produce results here.
In fact, more often, we have to use additional tools, based on 'Choice's.
Processing of 'choice's includes the following topics :
- checking saturation
- checking subsets (not yet seen in puzzles),
- Forced tag in a 'choice' (could be applied to any set of tag if at least one is valid)
and for level 3
- Extending Weak links (could be applied to any set of tag if at least one is valid)
Some more details regarding the three topics.
=> checking saturation (If in a choice two tags are in 'OR' condition (opposite to weak link), other tags are cleared.)
This seems to be a safety procedure with small chances to have a positive effect
In fact, it's a useful way to achieve clearing when ' Nice Loops' are crossing 'AC's.
=> checking subsets
Again, checking evidence.
If a choice has another choice as a subset, all complementary tags can be cleared.
I never encountered up to now that situation.
=> Forced tag in a choice
if all tags belonging to a choice are forcing another tag, the forced tag is valid. (still thru appropriate alternate chains)
As mentioned, this is valid with a set of tags in which "at least one tag is valid". Such a set could generated for example out of Unique rectangle patterns. This is not done in my program.
The last topic is a key point.
The process is looping on it, checking at each loop if new alternate chains or ‘Nice loops’ appear.
The process is looping back to basic analysis as soon as some clearing of candidates is done.
The process fails if no extension occurs in a step.
=> Extending Weak links
we consider a choice eg:{abcd}
. 'a' and 'b' are forcing 'e'
. 'c' and 'd' are forcing 'f' (still thru appropriate alternate chains)
then we have a 'OR' condition between 'e' and 'f', that is a weak link between 'E' and 'F'.
As far as I could check, this process fully covers standard use of ALS.
Printing rules.
The main tool, as I mentioned is the Alternate Chain.
Most common writing of Alternate chains is in the form : /_/_/_/ where
/ indicates a weak link
_ indicates a strong link.
The corresponding chains using tags could be : A/B_b/C_c/D. I write it [] AB bC cD
As a strong link is also a weak link, any / can be replaced by _.
Using tags, corresponding form would be []AB bB bB bC ...
I skip these steps.
When we get out of the basic tagging, reading is easier with the classic form. So tags are replaced by the relevant group of candidates.
In such a case, if a starting point doesn't appear in the chain, I show the starting point using the == link ex :
1r2c3==2r2c7/.._.. means start point 1r2c3, same tag as 2r2c7, 2r2c7 actual start of the chain.
=> Identifying weak link extension.
let's assume we discover a new weak link 1r5c4/8r4c7.
explanation will be printed
#[] 1r5c4/8r4c7 followed by the list of chains
use is shown either 1r5c4/8r4c7|# or 8r4c7/1r5c4|# depending on the context.
=> Identifying 'AC' as source of choice or source of weak link.
|*r4c3 r5c3 indicate a 'AC' effect from 'AC' r4c3 r5c3. it can be
. a choice analysis eg : #[]1r5c4/8r4c7 |*r4c3 r5c3 ...(list of chains) weak link generated out of the 'AC' r4c3 r5c3
. a weak link eg : 2(r4c3 r5c3)/9(r4c3 r5c3)|*r4c3 r5c3 (in a chain)
=> group simplification
If we have a weak link between two 'group's, we have also a weak link between any component extracted from each 'group'.
This is a way to shorten printing.
If I am using a 'group' of an extended weak link with necessity to stress on one specific component, I am using ';' separator.
eg :
# [] 1(r5c4 r6c4 r7c4)/1r4c2
... []1(r6c4;r5c4 r7c4)/1r4c2|# (here 1r6c4 would be one component of a 'choice').
Conclusion
I hope I have covered the field. At least, it's enough to understand most of prints of puzzles solutions.
In level 2, I have an artificial limitation to stay in the philosophy of what could be achieved in hand processing.
In that "half level", 'Choice's are limited to three tags, and no 'choice' is generated out of AC's.
edit 1 2007 11 06 change 'step' to 'level'
