Full Tagging

Advanced methods and approaches for solving Sudoku puzzles

Full Tagging

Postby champagne » Thu Sep 13, 2007 8:23 am

EDIT: This thread has been opened six months ago. Meantime things have changed and a lot has been done. To keep an updated situation (French and English) I have opened a website

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'
Last edited by champagne on Thu Mar 20, 2008 1:39 pm, edited 2 times in total.
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Re: Full Tagging

Postby ronk » Thu Sep 13, 2007 11:05 am

champagne wrote: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 

Hmm, it's going to take a while to study your post.

champagne, it would be helpful if you posted tagged pencilmarks with the filled cells (givens and placements) and without the row numbers. Then it's possible to cut & paste the pencilmarks into some solvers, such as angusj' Simple Sudoku. For example, cut and paste is possible with the following:
Code: Select all
 23a8b 5     24t8B | 3A46j 2p46  7     | 1      9      2c6C
 9     24u6c 247d  | 1     23H6C 2O34t | 23A7D  8      5
 23A7D 2c6C  1     | 9     8     5     | 236w7d 23S6   4
-------------------+-------------------+----------------------
 4     3     2e5f9g| 5F7f  7g9G  6     | 8      1      2E7e
 2b8B  28b9K 25F9  | 45f7e 1     3H49g | 234    234V6C 23l6c7E
 1     7     6     | 2     3h4H  8     | 3H4h   5      9
-------------------+-------------------+----------------------
 6     248B  247G8b| 3r47g 5     1     | 9      234    2l3L
 25i7d 1     2479K | 346J  7G9g  2q3A49| 45I6   23r46w 8
 2i5I  249k  3     | 8     2O46j 249K  | 245i6J 7      1

Are you familiar with David P. Bird's Graded Equivalence Marking (GEM)? If so, essentially how does your "full tagging" technique differ?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby champagne » Thu Sep 13, 2007 12:46 pm

Ronk wrote
champagne, it would be helpful if you posted tagged pencilmarks with the filled cells (givens and placements) and without the row numbers. Then it's possible to cut & paste the pencilmarks into some solvers, such as angusj' Simple Sudoku. For example, cut and paste is possible with the following:



Basically no problem, just some time to achieve print adjustment. As you could see, I made a significant step to meet your printing rules. Is it a problem if I use stressed letters to increase tagging capabilities printing with one sign. eg â Â ...


Code: Select all
Ronk wrote
Are you familiar with David P. Bird's Graded Equivalence Marking (GEM)? If so, essentially how does your "full tagging" technique differ?


Not at all, but it’s not a big problem to read it and to give a first feeling about overlapping concepts and differences;
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Thu Sep 13, 2007 5:05 pm

Ronk wrote

Are you familiar with David P. Bird's Graded Equivalence Marking (GEM)? If so, essentially how does your "full tagging" technique differ?


I went thru the Sudopedia file. Here above my feeling.

The philosophy applied in GEM seems closer to “forced chains”. All is done with “six tags” in a dynamic view starting form a specific bi value.

To stay on the safe side towards T&E process, I never used algorithms requesting a starting point.

One exception is the use of alternate chains starting from components of a ‘choice’.

In full tagging, as you noticed, we have a unique and static tagging with only strong links tagged.

At the end, you have some overlapping, but not that much.

I noticed, when I studied Bob Hanson solutions using forcing chains that forcing chains are solving faster than alternate chains.

You have likely the same results with GEM marking.

The power of full tagging compared to GE is more in the capacity to integrate groups, ALS, ACs …, and finally in ‘choice’ handling.

With step 1 alone, full tagging offers likely less capability to solve puzzles than GEM.
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Sat Sep 29, 2007 4:39 pm

Edit one:

I have to introduce a small change in the “full tagging “procedure.

The second logical rule for Choice has to be adjusted.

Original rule:

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}.


New rule:

Let's consider one 'choice' {a,b,c}. 'a' and 'b' are in weak link (directly or thru alternate chains) with 'd', then ‘d’ is in weak link with ‘C’.

Corollary:
If in addition ‘c’ is in weak link with ‘D’ then 'c' and 'd' can be merged.



In fact the old rule is a subset of the new one. The new rule describes among others a situation where one candidate eliminates all candidates in a cell but one.

For historical reasons, the ‘new rule’ has been hidden by the old one. I keep the old one as corollary because in hand solving, it is very easy to handle.

I introduced this new rule in the solver. As we could expect, new paths appeared, shortening the solution. Nevertheless, as far as I could see, it does not change the list of unsolved puzzles.
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Mon Oct 22, 2007 4:17 pm

In the main post I wrote

Code: Select all
a fourth step (which one is relevant?) should be implemented to solve the small number of resisting puzzles.

I followed several paths during the last year, without any success.

The last idea seems to be the good one.

I’ll use for introduction of step four the puzzle DML155 on which I worked.

This puzzle

Code: Select all
100900000020050030004006000600000100030080020007000004000300700000020050080004009

Stays unsolved in that position: (puzzle tagged as of step one)

Code: Select all
1     56u7   3B568 |9       34A7   2f3O78 |24568  4e678 25678
789   2      6S89  |14a78   5      178    |4A689â 3     1L67 
3b578 579â   4     |12F78   13B7   6      |2589   1m79å 12578
-------------------------------------------------------------
6     4D59   2h8H  |2457    4a79   23c579 |1      7Z89  3C578
4d59  3      1g59  |14D56t7 8      1579   |569    2     567w 
2H8h  1G59   7     |1256    13O6V9 12359  |3c5689 689   4     
-------------------------------------------------------------
259   14e569 12569 |3       169ä   15i8À9 |7      14E68 12j68
34D79 1467y9 1369  |1678á   2      1789à |34e68  5     13c68
2357X 8      12356 |15I67   167    4      |2J3n6  1k6K  9



The new stuff added can be illustrated by:

R1c2;r3c2 // rc3;r2c1;r2c3;r3c1.

The first lot is very simple: two cells, four possible digits, two are good, two are bad.

The second lot is complementary to the first one.
- Four cells,
- 3 and 8 are compulsory,
- The same four digit remaining, among which two are good and two are false.

This is a part of the set of ALS with freedom 2 and their counterpart “almost cells with freedom two”.

There are several reasons why I did not consider the full set. The main one is that entering this field, difficulty and volume are quickly increasing. In that position, you have a total of 290 ALS + ”Almost cells”, with freedom two, you have to consider about 1200 entities. Moreover, as you will see, this limited lot has additional properties.

Any component of this set has the following properties:
- two digits are valid, which gives six possible couples.
- If two digits are valid in one component, the two other digits are valid in the complementary component.

In full tagging, a possible couple is a new kind of tag (couple tag).
- each digit in the component is tagged (group tag) as it was in step two.
- The two sub tags are forming the new tag.
- If the two sub tags are in weak link, the “couple tag” is not valid.
- A “couple tag” is corresponding to at least two groups of sub tags. One for the component and one for the complementary component.
- A “couple tag” is in fact fully defined by the four weak links with elementary tags eg: ABCD couple tag {AB}=X: weak links XC XD Xa Xb.


Let’s consider block one:

1 56u7 3B568
789 2 6S89
3b578 579â 4

We have in that block several entities corresponding to our new stuff
These ones are interesting:
. r1c2 r1c3 r3c1 5678 counterpart r2c1 r2c3 r3c2
. r2c1 r2c3 6789 counterpart r1c2 r1c3 r3c1 r3c2
. r2c1 r3c2 5789 counterpart r1c2 r1c3 r2c3 r3c1

Couples 6;8 are the same in {r2c1 r2c3} and {r2c1 r2c3 r3c2}
Couples 5;7 are the same in {r1c2 r1c3 r3c1} and { r1c2 r1c3 r2c3 r3c1}

This leads to a tight connection of these components.

There is a strong difference between ALS/”Almost cells” used in step two and this stuff.

ALS/”Almost cells” are 100% homogeneous with bi values used in step one. “Almost cell” provides us with weak link necessary to include this stuff in AICs.

Here, we still have strong links, but no direct way to define weak link. As a matter of fact, use of ALS with freedom 2 without use of “couple tags” gives poor results. Using “couple tags”, symmetry is broken. Strong links can still be defined, but seem very artificial.

“Couple tags” will work in several ways:

- The set of six couples is a choice. As such, we can use it as any other choice (see step two).
- “Couples tags” can be processed as any other tag.
- If the choice can be reduced to one component, this component is valid.
- If one “couple tag” can be merged with a basic tag, it becomes a standard component of AICs.
- Rarely, it can enter directly in AICs.



The only new logic in step four is the clearing of a “couple tag” which gives no direct clearing in the candidates.

As far as I could see, this additional power cracks a significant part of puzzles resisting to step three.
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby Mike Barker » Sat Oct 27, 2007 12:53 am

Champange, over on the discussions forum, Adam has created a thread to look at different ways to make an elimination for a difficult, but not hard (~SE 8.0) puzzle. The idea is to look at advantages and disadvantages of different techniques. It would be interesting to see what next step full tagging would make in the following puzzle:
Code: Select all
+----------------+-----------------+------------------+
|   8    37   5  |   1    4    67  |   36     9    2  |
|   2     6   1  |   5    9     3  |    8     7    4  |
|   4     9  37  |   2   67     8  |  136     5   13  |
+----------------+-----------------+------------------+
|   5  1234   6  |  48   18   149  |    7  1234   39  |
|  19   124  47  |   3  157  1459  | 1249     8    6  |
| 139  1347   8  | 469    2    67  |  149   134    5  |
+----------------+-----------------+------------------+
|   6     5  34  |   7  138   149  | 1249  1234  389  |
|  13     8   2  |  49  135  1459  | 1349     6    7  |
|   7   134   9  | 468  368     2  |    5   134  138  |
+----------------+-----------------+------------------+

Thx
Mike
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby champagne » Sat Oct 27, 2007 2:04 pm

Mike wrote
Champagne, over on the discussions forum, Adam has created a thread to look at different ways to make an elimination for a difficult,
but not hard (~SE 8.0) puzzle. The idea is to look at advantages and disadvantages of different techniques.
It would be interesting to see what next step full tagging would make in the following puzzle:


A quick answer to your question. I'll visit later the thread you mentioned.

This puzzle appears in my solver as "limit for hand solving".
At your point, the solver offers 12 clearing sequences thru ternary choices.
These 12 sequences appears at the same moment in the process.
Part of them would be sufficient to crack the puzzle without any other use of tagging.
I kept all of them considering this is more in line with your request

Here is the puzzle tagged as of step one.

Code: Select all
8     3a7A   5    |1     4     6A7a  |3A6a    9     2     
2     6      1    |5     9     3     |8       7     4     
4     9      3A7a |2     6a7A  8     |1b36A   5     1B3b 
---------------------------------------------------------
5     12c3p4 6    |4D8d  1d8D  149e  |7       12C34 3e9E 
1I9i  12C4   4a7A |3     15f7a 145F9 |12c49   8     6     
13h9I 1347a  8    |46A9j 2     6a7A  |149     13p4  5     
---------------------------------------------------------
6     5      3a4A |7     138g  149t  |12C49   12c34 38G9e
1h3H  8      2    |4j9J  135F  145f9 |13b4Q9t 6     7     
7     1H34a  9    |46a8D 36A8  2     |5       134   1b38g

Complementary tagging is done in the folowing way :
- 6r9c4-a 4r9c4 8r9c4-D cell r9c4
- 4r9c2-a 4r9c4 4r9c8 => 4r9c8 tagged D

- 1r9c9-b 1r9c2-H 1r9c8
- 3r8c7-b 3r8c1-H 3r8c5 => 1r9c8 3r8c5 same tag

- 9r4c6-e 9r7c6-t 9(r5c6r8c6)
- 9r7c9-e 9r7c6-t 9r7c7 => 9r7c7 9(r5c6r8c6) same tag

And the 12 clearing sequences:

#1(r5c5r5c6)
[]9r4c6==9r7c9-e/8r7c9-G_8r7c5-g/8r4c5-D_1r4c5-d/1(r5c5r5c6)
[]1r4c6/1(r5c5r5c6)
[]4r4c6/4r4c4-D_1r4c5-d/1(r5c5r5c6)

#[]b
[]8r7c5==8r9c9-g/1r9c9-b
[]3r7c5/3r7c3-a_3r1c7-A/3r3c9-b
[]1r7c5/1r4c5-d_8r9c4-D/6r9c4-a_3r1c7-A/3r3c9-b

#[]8r9c5
[]8r7c5-g/8r9c5
[]3r7c5/3r7c3-a_6r9c5-A/8r9c5
[]1r7c5/1r4c5-d_8r4c5-D/8r9c5

#[]L
[]9r7c6-t/9r8c4-J_9r6c4-j/6r6c4-A_3r1c2-a/3(r4c2r6c2)-H_1r8c1-h/1(r8c5r8c6)-L
[]1r7c6/1(r7c7r7c8)-L
[]4r7c6/4r7c3-A_3r1c2-a/3(r4c2r6c2)-H_1r8c1-h/1(r8c5r8c6)-L

#[]M
[]9r7c6-t/9r8c4-J_4r8c4-j/4r4c4-D_1r4c5-d/1(r7c5r8c5)-M
[]1r7c6/1(r7c5r8c5)-M
[]4r7c6/4r7c3-A_6r9c4-a/8r9c4-D_1r4c5-d/1(r7c5r8c5)-M

#[]j
[]1r9c8==3r8c5/5r8c5-F_5r5c5-f/7r5c5-a_6r6c4-A/9r6c4-j
[]3r9c8/3(r4c8r6c8)-E_9r4c6-e/9r6c4-j
[]4r9c8==4r4c4-D/4r8c4-j

#[]3r9c5
[]1r9c8==3r8c5/3r9c5
[]3r9c8/3r9c5
[]4r9c8==8r9c4-D/6r9c4-a_6r9c5-A/3r9c5

#[]3r3c7
[]1r9c9==1r3c7-b/3r3c7
[]1r9c2==3(r4c2r6c2)-H/3r1c2-a_3r1c7-A/3r3c7
[]1r9c8==3r8c5/5r8c5-F_5r5c5-f/7r5c5-a_3r1c7-A/3r3c7

#[]4r7c6
[]1r9c9==3r8c7-b/4r8c7_4(r8c4r8c6)-q/4r7c6
[]1r9c2==3(r4c2r6c2)-H/3r1c2-a_4r7c3-A/4r7c6
[]1r9c8==3r8c5/5r8c5-F_5r5c5-f/7r5c5-a_4r7c3-A/4r7c6

#[]3r9c8
[]3r7c5/8r7c5-g_8r7c9-G/9r7c9-e_3(r4c8r6c8)-E/3r9c8
[]3r8c5==1r9c8-Ô/3r9c8
[]3r9c5/3r9c8

#[]9r5c7
[]3r7c5/8r7c5-g_8r7c9-G/9r7c9-e_9r4c9-E/9r5c7
[]3r8c5/3r8c1-H_3r6c1-h/9r6c1-I_9r5c1-i/9r5c7
[]3r9c5/6r9c5-A_3r1c2-a/3(r4c2r6c2)-H_3r6c1-h/9r6c1-I_9r5c1-i/9r5c7

#[]p
[]9r4c6==3r4c9-e/3r4c2-p
[]9r6c4-j/6r6c4-A_3r1c2-a/3r4c2-p
[]9r5c6/9(r4c6r7c6)_9r7c7/2r7c7-C_2r4c2-c/3r4c2-p

Nota : 9r7c7 9(r5c6r8c6) same tag =>9(r4c6r7c6)_9r7c7

r1c7=3 .... to the end
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Mon Oct 29, 2007 8:53 am

Analysis of Easter Monster cracking has revealed a very interesting pattern, easy to detect visually and performing well under specific conditions.

I will call it “Virus Pattern”

Here after Ronk post for the start of Easter Monster.

Code: Select all
  1      A478     34578   | 3567    3689    5678    | 3489   I369    2
 L238     9      L378     | 4      K12368  K12678   |J138     5      J368
 23458  A248     6       | 1235    12389   1258    | 7      I139     3489
--------------------------+-------------------------+---------------------- 
 2468    5       1478    | 9       1246    3       | 128    H1267    678 
 234689 B12468   13489   | 126     7       1246    | 123589 H12369   35689 
 2369   B1267    1379    | 8       5       126     | 1239    4       3679
--------------------------+-------------------------+---------------------- 
 7      C148     14589   | 1235    12348   12458   | 6      G239     3459
 D456    3      D145     |E12567  E1246    9       |F245     8      F457 
 45689  C468    2        | 3567    3468    45678   | 3459   G379     1


And the "Kurzhals loop" attached

(27)r13c2=(27-16)r56c2=(16)r79c2-(16)r8c13=(16-27)r8c45=(27)r8c79-(27)r79c8
=(27- 16)r45c8=(16)r13c8-(16)r2c79=(16-27)r2c56=(27)r2c13 - loop

In a first step, the loop itself is not the topic. In place, we will study the components.


The first “virus pattern” is in column c2. The second one is in box one.

In both cases, three digits are known. Two separate sets of two cell are forming
. AALS (four digits, 2 are not valid) in Ronk preferred way,
.AC2 (four digits, 2 are valid) in my preferred way.
Consequently, two others AC2 are formed merging the two additional cells with anyone of the previously defined AC2.

Eg :
Code: Select all
||*r1c2r3c2  ||*r1c3r2c1r2c3r3c1 
||*r2c1r2c3  ||*r1c2r1c3r3c1r3c2
----
||*r1c2r3c2  ||*r5c2r6c2r7c2r9c2
||*r7c2r9c2  ||*r1c2r3c2r5c2r6c2


To describe the virus pattern, it’s easier to work on the three separate sets

Code: Select all
||*r1c2r3c2   {r1c3r3c1 )  ||*r2c1r2c3   (2478) (234578) (2378)
||*r1c2r3c2   (r5c2r6c2)   ||*r7c2r9c2   (2478) (124678) (1468)



In the first pattern, we have the same three digits in both ends (278), in the second one, we have only two (48).

Let us assume that {(2;7)||*r1c2r3c2)} is a strong link (what the computer shows).
Then
- {(4;8)||*r1c2r3c2} is a strong link as well.
- {(4;8)||*r7c2r9c2} is a weak link (not both but maybe none)
- consequently {(1;6)||*r7c2r9c2} is in OR status (at last one, maybe two).


If such structure can be chained, we have the capacity to expand links (that’s why I called “virus pattern” that structure). You can also get a pincers effect.

eg: {(2;7)||*r1c2r3c2)} => {(4;8)||*r7c2r9c2} => NOT{(4;8)||*r7c2r9c2} => OR{(1;6)||*r7c2r9c2} => NOT{(1;6)||*r7c1r7c3) => OR{{4;5)||*r7c1r7c3)=>NOT{(4;5)||*r7c7r7c9}=>OR{(2;7)||*r7c7r7c9}

At that point, if you can prove for example (what did the computer) that {(2;7)||*r7c8r9c8} is a strong link, you have a reverse expansion starting with:
-NOT{(2;7)||*r7c7r7c9} => {(2;7)||*r7c7r7c9} strong link ; {(4;5)||*r7c7r7c9} strong link=>
-NOT{{4;5)||*r7c1r7c3)....

That open chain is now entirely made of strong links.
.

Moreover, as Kurzhals has brightly shown, if you can chain this two “virus patterns” to form a loop, then you have identified strong links and the entire loop can be cleaned.

A Kurzhals loop is always a chain or 8 “virus pattern” is the sequence raw,box,column,box,raw,box,colum,box.


This is performing much better than the basic approach I described, It is easy to detect, limited in volume and manageable in hand processing.

There is still a lot of work to cover the entire field, here is for example dml155 where step three of my process fails.


Code: Select all
1     56u7   3B568 |9       34A7   2f3O78 |24568  4e678 25678
789   2      6S89  |14a78   5      178    |4A689â 3     1L67 
3b578 579â   4     |12F78   13B7   6      |2589   1m79å 12578
-------------------------------------------------------------
6     4D59   2h8H  |2457    4a79   23c579 |1      7Z89  3C578
4d59  3      1g59  |14D56t7 8      1579   |569    2     567w 
2H8h  1G59   7     |1256    13O6V9 12359  |3c5689 689   4     
-------------------------------------------------------------
259   14e569 12569 |3       169ä   15i8À9 |7      14E68 12j68
34D79 1467y9 1369  |1678á   2      1789à |34e68  5     13c68
2357X 8      12356 |15I67   167    4      |2J3n6  1k6K  9


A third pattern in Box 4 (four digits common to both ends). No evidence of Kurzhals loop but a long chain of “virus patterns” :

Column5,Box2,Raw2,Box1,column2,Box4,row5,box6,column8,Box9

Edit 1 2007 10 30
- correction of mstake "no autoclearing"
- better analysis of virus effet in chains
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby Mike Barker » Fri Nov 02, 2007 2:48 pm

Champagne, thanks. Let me see if I can summarize what you are doing. The first step is to label the alternating inference chains that exist in the puzzle using mostly bivalues and conjugate pairs. In this case, starting layer aA with (3)r2c1=(7)r2c1 the net seems pretty straight forward. For the bB layer there is actually an AHS 36=r13c7 which results in 3=r8c7b. Once no more eliminations can be made at this level grouped strong links, ALS, and AHS are added.
Code: Select all
8     3a7A   5    |1     4     6A7a  |3A6a    9     2     
2     6      1    |5     9     3     |8       7     4     
4     9      3A7a |2     6a7A  8     |1b36A   5     1B3b 
---------------------------------------------------------
5     12c3p4 6    |4D8d  1d8D  149e  |7       12C34 3e9E 
1I9i  12C4   4a7A |3     15f7a 145F9 |12c49   8     6     
13h9I 1347a  8    |46A9j 2     6a7A  |149     13p4  5     
---------------------------------------------------------
6     5      3a4A |7     138g  149t  |12C49   12c34 38G9e
1h3H  8      2    |4j9J  135F  145f9 |13b4Q9t 6     7     
7     1H34a  9    |46a8D 36A8  2     |5       134   1b38g

Complementary tagging is done next based on the two rules:
1) Given two strong inferences (choices), {a,b,c} and {a,b,d} (same tags but one), then 'c' and 'd' are identical and can be merged. For example:
Code: Select all
6=r9c4a 4=r9c4 8=r9c4D
4=r9c2a 4=r9c4 4=r9c8  => 4=r9c8 tagged D

2) Given a strong inference (choice) {a,b,c} and tag 'd' such that 'a-d' and 'b-d' (weakly linked directly or thru alternate chains), then ‘d-C'. If in addition ‘c-D’ then 'c' and 'd' can be merged (are the same tag).
Code: Select all
1=r9c9b 1=r9c2H 1=r9c8
3=r8c7b 3=r8c1H 3=r8c5 => 1=r9c8, 3=r8c5 same tag

9=r4c6e 9=r7c6t 9=r58c6
9=r7c9e 9=r7c6t 9=r7c7 => 9=r7c7, 9=r58c6 same tag 

One question would be why these complementary tags? Are these all there are or just those that where used?

The 12 clearing sequences are based on what I'd call kraken cells (3 or more candidates in a cell such that one must be true) or kraken units (3 or more candidates in a row, column or box such that one must be true). I've modified the loops to look more like multi-inference nice loops. A "==" implies the link is via a chain and both nodes are either true or false since they have the same label or are complementary tagged. A "||" represents the strong inferences in the kraken node.

In the first case r4c6={149} results in r5c56<>1:
Code: Select all
#r5c56<>1
9=r4c6e==9=r7c9e-8-r7c9G=8=r7c5g-8-r4c5D=1=r4c5d-1-r5c56
||
1=r4c6-1-r5c56
||
4=r4c6-4-r4c4D=1=r4c5d-1-r5c56


In the next two cases all candidates labeled "b" are false and r9c5<>8 since r7c5={138}:
Code: Select all
#b
8=r7c5g==8=r9c9g-1-r9c9b
||
3=r7c5-3-r7c3a=3=r1c7A-3-r3c9b
||
1=r7c5-1-r4c5d=8=r9c4D-6-r9c4a=3=r1c7A-3-r3c9b

#r9c59<>8
8=r7c5g-8-r9c5
||
3=r7c5-3-r7c3a=6=r9c5A-8-r9c5
||
1=r7c5-1-r4c5d=8=r4c5D-8-r9c5 

Grouped strong link layers L* and Mm (little L = * to avoid confusion with the number one) which were not shown in the original tagged puzzle are eliminated based on the kraken cell r7c6={149} and tagging of the grouped strong link r6c1h=3=r46c2H. r4c9e=3=r46c8E also appears here. I haven't done it, but I imagine something needs to be done do indicate these are grouped nodes. I assume based on their letters that they were tagged in the initial process. Why weren't they shown?
Code: Select all
8      3a7A    5    |1     4      6A7a  |3A6a    9      2     
2      6       1    |5     9      3     |8       7      4     
4      9       3A7a |2     6a7A   8     |36A     5      1
-----------------------------------------------------------
5      12c3Hp4 6    |4D8d  1d8D   149e  |7       12C3E4 3e9E 
1I9i   12C4    4a7A |3     5f7a   45F9  |12c49   8      6     
1m3h9I 1m3H47a 8    |46A9j 2      6a7A  |1M49    1M3Ep4 5     
-----------------------------------------------------------
6      5       3a4A |7     1*38g  1*49t |1L2C49  1L2c34 38G9e
1h3H   8       2    |4j9J  1L35F  1L45f9|14Q9t   6      7     
7      1H34a   9    |46a8D 36A8   2     |5       134    38g 

#L
9=r7c6t-9-r8c4J=9=r6c4j-6-r6c4A=3=r1c2a-3-r46c2H=1=r8c1h-1-r8c56L
||
1=r7c6-1-r7c78L
||
4=r7c6-4-r7c3A=3=r1c2a-3-r46c2H=1=r8c1h-1-r8c56L

#M
9=r7c6t-9-r8c4J=4=r8c4j-4-r4c4D=1=r4c5d-1-r78c5M
||
1=r7c6-1-r78c5M
||
4=r7c6-4-r7c3A=6=r9c4a-8-r9c4D=1=r4c5d-1-r78c5M

Elimination of set "j" uses two of the complementary tags (r9c8==3=r8c5 and r9c8==4=r4c4D)
Code: Select all
#j
1=r9c8==3=r8c5-5-r8c5F=5=r5c5f-7-r5c5a=6=r6c4A-9-r6c4j
||
3=r9c8-3-r46c8E=9=r4c6e-9-r6c4j
||
4=r9c8==4=r4c4D-4-r8c4j

#r9c5<>3
1=r9c8==3=r8c5-3-r9c5
||
3=r9c8-3-r9c5
||
4=r9c8==8=r9c4D-6-r9c4a=6=r9c5A-3-r9c5

Eliminations are not done sequentially, but by considering all implications of the original tagged board, thus even though "b" was eliminated it still shows up here. The elimination is thus shown as a Kraken Row when, because of the elimination of "b", there is a new strong inference r9c2=1=r9c8 thus 1=r9c8 and 3=r8c5 are "h" and it could be reduced to a nice loop.
Code: Select all
#r3c7<>3
1=r9c9b==1=r3c7b-3-r3c7
||
1=r9c2H==3=r46c2H-3-r1c2a=3=r1c7A-3-r3c7
||
1=r9c8==3=r8c5-5-r8c5F=5=r5c5f-7-r5c5a=3=r1c7A-3-r3c7

#r7c6<>4
1=r9c9b==3=r8c7b-4-r8c7=4=r8c46q-4-r7c6
||
1=r9c2H==3=r46c2H-3-r1c2a=4=r7c3A-4-r7c6
||
1=r9c8==3=r8c5-5-r8c5F=5=r5c5f-7-r5c5a=4=r7c3A-4-r7c6

#r9c8<>3
3=r7c5-8-r7c5g=8=r7c9G-9-r7c9e=3=r46c8E-3-r9c8
||
3=r8c5==1=r9c8Ô-3-r9c8
||
3=r9c5-3-r9c8

#r5c7<>9
3=r7c5-8-r7c5g=8=r7c9G-9-r7c9e=9=r4c9E-9-r5c7
||
3=r8c5-3-r8c1H=3=r6c1h-9-r6c1I=9=r5c1i-9-r5c7
||
3=r9c5-6-r9c5A=3=r1c2a-3-r46c2H=3=r6c1h-9-r6c1I=9=r5c1i-9-r5c7

The next elimination is based on the final complementary tag (9=r7c7==9=r58c6) and thus r47c6=9=r7c7:
Code: Select all
#p
9=r4c6e==3=r4c9e-3-r4c2p
||
9=r6c4j-6-r6c4A=3=r1c2a-3-r4c2p
||
9=r5c6-9-r47c6=9=r7c7-2-r7c7C=2=r4c2c-3-r4c2p

r1c7=3 .... to the end. Thanks for the solution. Its a nice demonstration of full tagging.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby champagne » Sat Nov 03, 2007 5:47 pm

Hello Mike,

Small adjustments and answers to your questions.

Fisrt I need one definition. What is AHS. Is it the same as "Almost cells" I defined in this thread?


1) Basic tagging as of step one.

Code: Select all
8     3a7A   5    |1     4     6A7a  |3A6a    9     2     
2     6      1    |5     9     3     |8       7     4     
4     9      3A7a |2     6a7A  8     |1b36A   5     1B3b 
---------------------------------------------------------
5     12c3p4 6    |4D8d  1d8D  149e  |7       12C34 3e9E 
1I9i  12C4   4a7A |3     15f7a 145F9 |12c49   8     6     
13h9I 1347a  8    |46A9j 2     6a7A  |149     13p4  5     
---------------------------------------------------------
6     5      3a4A |7     138g  149t  |12C49   12c34 38G9e
1h3H  8      2    |4j9J  135F  145f9 |13b4Q9t 6     7     
7     1H34a  9    |46a8D 36A8  2     |5       134   1b38g 


Several points in your post that need comments.

1.1) Basic tagging includes "grouped strong links". But nothing else that strong links coming out of bivalues and conjugate pairs.
Groups are limited to the common part of two units (row box, row column).
1.2) As you noticed, groups are not shown in the print. We have tried several ways to show groups, nothing convincing.
The print is here just to help in understanding the clearing chains. If necessary, we give additional comments on used groups.
Groups are visible mainly in grids limited to candidates of one specific digit.
1.3) Some examples of groups :
Code: Select all
  - 3(r3c79) is a group tagged 'a'
  - 3(r13c7) is a group. r3c9=3=(r13c7) is a strong link. No use of  AHS 36=r13c7  is needed.
  - 9(r7c79) is a group tagged 'T' ( as 9(r8c46).
  - 1(r46c2)==1(r56c1) tagged 'h'
  as you assumed
  - M,m layer is for digit 1 , r45c5 r78c5 r78c6 r45c6
  - L,l layer is for digit 1 , r8c56 r7c56 r7c78

Mike wrote
Once no more eliminations can be made at this level grouped strong links, ALS, and AHS are added.


Basically you are right. I did not comment on a "half step two" which is the status here.
Tagging is extended using ALS and "Almost cells", but clearing capacities are limited to ternary Choices out of cells and "kraken units"
This limitation refers to what is done in "solving without computer assistance".

With full step two, choices are not limited in size, and the choice can be done out of an "almost cell".
On top of it, "almost cells" generate weak links as cells do. Consequently, AICs can cross "Almost cells". I gave a nice example of such a chain recently in a thread initiated by Denis Berthier.
In step 4 Choices can also be done out of AC2 (AALS) as you can see in the solution of Easter Monster proposed by the solver (thread call fro contribution).

Mike wrote

Complementary tagging is done next based on the two rules:
1) Given two strong inferences (choices), {a,b,c} and {a,b,d} (same tags but one), then 'c' and 'd' are identical and can be merged. For example:
2) Given a strong inference (choice) {a,b,c} and tag 'd' such that 'a-d' and 'b-d' (weakly linked directly or thru alternate chains), then ‘d-C'.
If in addition ‘c-D’ then 'c' and 'd' can be merged (are the same tag).

One question would be why these complementary tags? Are these all there are or just those that where used?


rule 1 is without any doubt complementary tagging. It can be applied to any set of tags with at least one tag valid. I am only considering choices and up to now, it worked only with three tags (may be I should check the code).

rule 2 should be classified in the family of derived weak link and nice loop processing.

In that specific case, we had only the three shown cases.



Mike wrote

Eliminations are not done sequentially, but by considering all implications of the original tagged board, thus even though "b" was eliminated it still shows up here
.


These 12 sequences appears at the same moment. They must be seen independently.

If I had had to propose a solution, I would likely have selected only 4 of the 12: #b #j #L #M.
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Mon Nov 05, 2007 6:39 pm

Adding memory to the solver


Going thru the solution proposed by the solver for Easter Monster was an interesting task.

It revealed a strong weakness in the process, the lack of memory.

Each time cleaning actions has been done, the process restart from nil.
As long as you are limited to levels one and two, it’s not really a problem.

With level three, it starts being one compared to hand processing.

Let’s take the example of kurtzhals loop in Easter Monster (it’s level four, but we have similar effects in step three).

Code: Select all
1     47A8  345h8  |3567Ã 389f 5678  |34j89 36k9  2     
2g38  9     37a8   |4     126  1267A |1i38  5     36K8 
345H8 2G48  6      |1235  389F 1258  |7     1I39  34J89
-------------------------------------------------------
24b68 5     14B7Â8 |9     126  3     |128   1267D 678   
389   126   389    |126   7    4     |35c89 126   35C89
2369  1267a 1379   |8     5    126   |1239  4     367Â9
-------------------------------------------------------
7     1l48  4589n  |1235  34e8 1258  |6     2o39  3459 
456m  3     1L45   |1267d 126  9     |2O45  8     457D 
4589N 46M8  2      |3567  34E8 567Ã8 |3459  37d9  1


In hand processing, the loop is established and you know it. You have in mind all strong links attached to the loop. Using full tagging, you would have tagged definitely the component of the loop having same tags.

Code: Select all
G is a
L is M
D is o
I is K



The computer does not.

Consequently, he can not take benefit of the known loop. He will in fact when the processing of virus patterns will be implemented, but there are other loops in levels 3 and 4 creating the same problem. Any loop having no effect in clearing has to be discovered again with actual process.

The same happens, with smaller effect, when there is some complementary tagging.

I am convinced that the path proposed to solve Easter Monster will change significantly including that memory function and sticking to a kind of human behaviour.

Moreover, virus pattern processing without a loop will request memory of weak links.

I am working on creating that memory function, and I hope I’ll be in a position to propose an improved solution for Easter Monster in one month, when I’ll be back from a three weeks trip.
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby champagne » Tue Nov 20, 2007 11:07 am

Before revising Easter Monster solution including new capabilities, I have to comment Kurtzhals loop and virus patterns links

Here is the start of Easter Monster shown by Ronk limited to used cell.


Code: Select all
  1     A478    34578   | 3567    3689    5678    | 3489   I369    2
 L238    9      L378    | 4       12368   12678   |J138     5      J368
 23458  A248    6       | 1235    12389   1258    | 7      I139     3489
------------------------+-------------------------+----------------------- 
 2468    5      1478    | 9       1246    3       | 128    1267    678 
 234689 12468   13489   | 126     7       1246    | 123589 12369   35689 
 2369   1267    1379    | 8       5       126     | 1239    4       3679
------------------------+-------------------------+----------------------- 
 7      C148    14589   | 1235    12348   12458   | 6      G239     3459
 D456    3     D145     | 12567   1246    9       |F245     8      F457 
 45689  C468   2        | 3567    3468    45678   | 3459   G379     1


A shortcut of the Kurzhals loop is the following:

AA(r13c2) CC(r79c2) DD(r8c13) FF(r8c79) GG(r79c8) II(r13c8) JJ(r2c79) LL(r2c13)

Each peace is a AALS/AHS/AC2 with a virus pattern.

I thought first (likely influenced by the solver solution) that the loop would clarify (explained later) the virus chain.

In fact, the loop is self clearing in a very simple way.

If we consider a chain of two pieces eg 27AA48 48BB16
both ends are forming a set of four digit groups 2;7AA 1;6BB in which at least two are valid.
With the chain 27AA.....LL27, we finish with exclusive groups digits 2 and 7. 2 and 7 must be within AA,LL in Box1.

This is just a specific case of ALS nets. Cutting at any place in the loop, we can clear boxes 1,3,7,9; rows 2,7; columns 2,8. ( box 9 is already cleared).

The loop is also a “virus pattern chain”. I you assume for example
Code: Select all
. (4|8)||* (r13c2)  (4 or 8 digit in AC2 (r13c2)  ) then you have
. !(4&8)||* r79c2  (not (4 and 8 digits) in r79c2
.(1|6)||* r79c2
.(!1&6)||* r8c13
.(4|5)||* r8c13
…….
.(3|8)||* r2c79
.!(3&8)||*r2c13
.(2|7)||*r2c13   loop


Another seed in any of the second part of the loop will give in any AC2 eg AA r13c2:

Code: Select all
. (2|7)||*r13c2 and  !(2&7)||*r13c2
.(4|8)||*r13c2 and  !(4&8)||*r13c2


Which means in fact:

Code: Select all
. (2^7)||*r13c2 (exclusive OR == strong link)
.(4^8)||*r13c2.



In the solution already posted for Easter Monster, the first step done by the solver has been to show:

!(4&8)||*r1c2r3c2} and!{3&8}||*r2c1r2c3}

These are two seeds allowing the full expansion of the loop.

“full tagging” solutions are commonly simplified when you add new strong links (merger of tags) or new weak links in existing field., I don’t yet know what will happen in that specific case.

The new process will:

- detect the loop and make the corresponding clearing,
- unless easier ways appear, find the two seeds for the virus chain and expand the chain (as done in step one published, may be in a shorter sequence),
- look for new clearing sequences keeping in mind the loop structure

Unless I missed something, the clearing of the loop keep all options open (which mean for example in AA 2&7 2&4 2&8 7&4 7&8 4&8). Finding the two seeds is unavoidable to take benefit of the loop structure on top of the clearing.


Ps: the loop could be seen as an example of ALS nets. Handling ALS nets leads as far as I could see to unworkable procedures. The loop will appear here as a virus chain effect, easy to handle including without a computer; In fact it is somehow by chance that both ways end in the same loop. In DML155 for example we still have very interesting virus patterns but no loop.
champagne
2017 Supporter
 
Posts: 5652
Joined: 02 August 2007
Location: France Brittany

Postby Myth Jellies » Tue Nov 20, 2007 8:24 pm

Here is a nice simple example of some ternary coloring logic that can easily be spotted by hand...
Code: Select all
 .     .     .     .     .     .     .     .     .
 .     245b8 .     4A568 .     .     .     .     3568
 .     .     .     .     .     .     .     .     .
 .     .     .     .     .     .     .     .     .
 .     .     .     .     .     .     .     .     .
 .     .     .     .     .     .     .     .     .
 .     .     .     .     .     .     .     .     35b6
 .     .     .     .     .     .     .     .     1a3568
 .     .     .     .     .     .     .     .     .


This situation actually occurred in a jigsaw I was working. Note that the cells shown are the only ones containing candidate fives in r2 and c9. One five is colored 'b' in the row and column as shown.

You can arbitrarily color the five in r2c4 as 5x and the five in r2c9 as 5y. This gives you a complete color set of (b, x, y) from which exactly one must be true. If you have two of those colors, and only one unmarked candidate left, then that candidate must be the remaining color. Note that in c9, we already have r2c9 arbitrarily colored as 5y, and we have a 5b in r7c9. Therefore we can safely color r8c9 as 5x.

But wait! The two cells colored 5x also contain conjugate colors (a,A). One of those conjugate colors must also be true so we can eliminate 5x because it can't be true.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Wed Nov 21, 2007 7:10 pm

Ravel mailed me this real world example yesterday...

ravel wrote:Hi Myth,

nice thing, your post today.
I could use it with todays helpme puzzle

But since im dead, i cannot post it myself ;)
Code: Select all
 *-------------------------------------------------*
 | 5     2679  169  | 3  67  4  | 1-79 1267   8    |
 | 1267  8     136  | 5  67  9  | 13-7 12467 B46   |
 | 679   3679  4    | 1  8   2  | 5   B67     369  |
 |------------------+-----------+------------------|
 | 4     5     2    | 7  9   6  | 8    3      1    |
 | 69    69    7    | 8  3   1  | 4    5      2    |
 | 3     1     8    | 4  2   5  | 6    9      7    |
 |------------------+-----------+------------------|
 | 167   367   5    | 9  4   8  | 2    16-7   36   |
 | 129   249   139  | 6  5   7  | 139  8     A49   |
 | 8     4679  69   | 2  1   3  |A79   467    5    |
 *-------------------------------------------------*
ALS
Code: Select all
 *------------------------------------------------*
 | 5     2679  169  | 3  67  4  | 19   1267   8   |
 |#1x267 8    @13A6 | 5  67  9  |@1A3a 12467  46  |
 | 679   3679  4    | 1  8   2  | 5    67     369 |
 |------------------+-----------+-----------------|
 | 4     5     2    | 7  9   6  | 8    3      1   |
 | 69    69    7    | 8  3   1  | 4    5      2   |
 | 3     1     8    | 4  2   5  | 6    9      7   |
 |------------------+-----------+-----------------|
 |#1b67  367   5    | 9  4   8  | 2   @1B6    36  |
 |#1y2   24   #1x3a | 6  5   7  |#1b39 8      49  |
 | 8     469   69   | 2  1   3  | 7    46     5   |
 *------------------------------------------------*
r8c3<>1, r2c1<>1

cheers,
ravel


In this case, once again, color 'x' sees both conjugate colors (a & A) and must be false. Actually, because of the bivalue in r8c3, we know that the color x is really the color A, and we see that forces two 1A's in row 2.

Perhaps we need to give this pattern a spiffy name. Something like a Ternary Corner Pin or a Tri-Coloring Corner Pin.

Of course it could be expanded to more than 3 colors. Also the chain which forces the inhibit could be an AIC consisting of multiple conjugate colors.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Next

Return to Advanced solving techniques