Sudoku Players' Forum (clone)

.
HOW TO DEAL WITH LARGE NUMBERS OF PATTERNS

1) Motivations
A large number (630) of impossible 3-digit patterns has recently been published by eleven. And this number is only for impossible patterns in two bands. Totuan and marek have also used patterns in three bands in some solutions of T&E(3) puzzles.
What can one do with such long lists?

I've already shown that:
- all the puzzles in this list can be proven contradictory in restricted T&E(2) (i.e. by using only candidates in the pattern) - except ten of them;
- all the puzzles in this list can be proven contradictory in full T&E(2) - except one, the famous Tridagon;
- all the puzzles in this list can be proven contradictory in restricted T&E(3).
Such a result provides a first idea of what to expect of resolution rules based on them. If a pattern can be proven contradictory in T&E(n), it may be useful to solve a puzzle that requires T&E(N+1) or more, but it will not be enough.

However, this doesn't provide much concrete help in solving real puzzles.

2) Purpose of this thread
The purpose of this thread is to analyse the different questions one must consider when faced with such large numbers of patterns, e.g.
- how to classify them (e.g. which of them have row-col symmetry?)
- how to eliminate some of them a priori;
- how to write associated detection rules and resolution rules for the remaining ones;
- how to select/eliminate some of them a posteriori, based on their resolution power wrt some relevant collection of puzzles;
- how to define a "reasonable" number of guardians, above which the pattern is not taken into consideration;
....

Eleven's 630 impossible list is the natural reference in the current context, but this thread is not limited to it, or even to k-digit patterns.
.

.
As an example of the topics of this thread, in the category "how to eliminate some them a priori?"

Can the patterns appear in any real puzzle (of course, with guardians) - but in their non-degenerate form, i.e. with all the k digits in all the cells of the pattern? This is an important question because degenerate forms:
- may be much harder to find,
- may not have the same complexity.
Patterns can be doubly impossible, if I dare say so.

Notice that, in a k-digit pattern, the k digits of the pattern can appear as givens nowhere in any row, column or block that has a cell in the pattern.
Let me call free cells those that remain after eliminating all the previous ones.
In any unique puzzle, at least 8 different digits must appear somewhere as givens.
For a k-digit pattern not to be super-impossible, it must therefore have at least k-1 free cells.

In eleven's list of 630 3-digit patterns, there are 38 with 0 free cells:

Code: Select all

in 10-cell list (among 31 patterns): none
in 12-cell list (among 38 patterns): none
in 13-cell list (among 290 patterns): 207 211 217 218 219
in 14-cells list (among 159 patterns): 23 33 36 73 92 112 113
in 15-cells list (among 102 patterns: 11 16 18 30 32 36 38 40 42 45 47 49 51 53 56 57 66 68 69 80 83 85 100 101
in 16-cells list (among 10 patterns): 9 10

Patterns with 1 free cell: none

Example : #207 in 13-cells. It's easy to see that the X's span all the columns.

Code: Select all

     +-------+-------+-------+
     ! . . . ! . . . ! . . X !
     ! . . . ! . . X ! . . X !
     ! . . . ! X X . ! . X . !
     +-------+-------+-------+
     ! . . . ! . . . ! . . X !
     ! . . X ! . . . ! X X . !
     ! X X . ! . . X ! . . . !
     +-------+-------+-------+
     ! . . . ! . . . ! . . . !
     ! . . . ! . . . ! . . . !
     ! . . . ! . . . ! . . . !
     +-------+-------+-------+
     ........X.....X..X...XX..X.........X..X...XX.XX...X..............................

   0 cells free for pattern digits
   3 rows with no cell in the pattern
   4 blocks with no-cell in the pattern
   0 columns with no-cell in the pattern

Eliminating 38 patterns from 630 is a small step, but there still remain 592.

.
I have now coded a first draft of all the rules for detecting eleven's 630 (minus 38) 3-digit impossible patterns and writing the ORk-relations that allow to use them automatically in conjunction with the generic ORk-chains.

It took me two full days to make this work.
Errr. Written this way, no one can believe me. Of course, I didn't write 1184 rules manually in two days. What I wrote manually is a rule generator (pattern => resolution rule). Even so, it took me only two days because I had previous experience in:
- writing rules generators (for all my classical chain rules);
- writing manually the tridagon rule and the rule for eleven's #97 pattern in 15 cells. I knew how the other rules should look like (i.e. the target of my generator).

Because row-column symmetry is not automatically taken into account by pattern-matching, this makes 1184 new rules with rather complex conditions (not counting 592 easy activation rules).
The current coding is far from perfect:
- patterns with diagonal symmetry happen to be coded twice (which cannot hurt, except slowing resolution);
- the logical output of the rules (i.e. the ORk relations they assert) is complete but their printed output (i.e. the printed information about these ORk relations) is still sketchy (which doesn't put any restriction on the output of the ORk-chains based on these ORk relations).

For programmers, about the second point, I don't remember too much about C, but the problem is to have some print function within a print function. I've never been in love with print functions. I think it's easier for me than in C (I've written the rule generator in CLIPS of course), but it's still terribly boring.

If anyone (eleven?) can complete the definition of the 630 patterns with a symbol for stating whether they are symmetric or not, I'm very interested. I don't have any program for putting a pattern into standardised form (whichever form one takes for "standardised", and this is a necessary ingredient for checking symmetry.

This is only one of the steps mentioned in my previous posts. My next step is running all this on mith's collection in order to find which of these rules allow interesting eliminations.

denis_berthier wrote:.
The current coding is far from perfect:
- patterns with diagonal symmetry happen to be coded twice (which cannot hurt, except slowing resolution);
- the logical output of the rules (i.e. the ORk relations they assert) is complete but their printed output (i.e. the printed information about these ORk relations) is still sketchy (which doesn't put any restriction on the output of the ORk-chains based on these ORk relations).

For programmers, about the second point, I don't remember too much about C, but the problem is to have some print function within a print function. I've never been in love with print functions. I think it's easier for me than in C (I've written the rule generator in CLIPS of course), but it's still terribly boring.

Hi Denis,
I don't understand what you mean. The "Simplest-First" program I wrote in Java, using ORk-chains for the Tridaggon, works for any
"3 digits impossible pattern" and it would be the same thing in C or C++

DEFISE wrote:

denis_berthier wrote:.
The current coding is far from perfect:
- patterns with diagonal symmetry happen to be coded twice (which cannot hurt, except slowing resolution);
- the logical output of the rules (i.e. the ORk relations they assert) is complete but their printed output (i.e. the printed information about these ORk relations) is still sketchy (which doesn't put any restriction on the output of the ORk-chains based on these ORk relations).

For programmers, about the second point, I don't remember too much about C, but the problem is to have some print function within a print function. I've never been in love with print functions. I think it's easier for me than in C (I've written the rule generator in CLIPS of course), but it's still terribly boring.

Hi Denis,
I don't understand what you mean. The "Simplest-First" program I wrote in Java, using ORk-chains for the Tridaggon, works for any
"3 digits impossible pattern" and it would be the same thing in C or C++

Hi François
The problem is not using the generic ORk-chain rules. It's writing for each pattern a specific rule that asserts the corresponding specific ORk-relation.

.
Here's some update of my work on generating rules.
Generation is now complete: I've found a solution to my printed output problem and all the rules associated with the (630-38) patterns are now generated in such a way that they can produce fully detailed information about their output (an ORk relation), adapted to each puzzle.
An example of the output is available in the Puzzles section: http://forum.enjoysudoku.com/350-in-mith-s-63137-t-e-3-min-expands-t40902.html

I had to make some decisions, e.g. about how to assign priorities:
- impossible patterns are looked for after W2 and S3 (this may change in the future, but it's unlikely);
- patterns with fewer cells are looked for before patterns with more cells this (may change in the future if some patterns appear to be more useful than others);
- all these patterns are looked for after Tridagon (this may change in the future, but it's very unlikely);
- patterns with the same number of cells are looked for in no particular order (this may change in the future if some patterns appear to be more useful than others);
- rules don't allow degenerate forms of the patterns, i.e. missing candidates (this will not change);
- parametric ORk chain rules based on them (the rules that do the real elimination job) are generic and they are used at their place in the rules hierarchy, defined by their length and independent of the internal complexity of the ORk-relation they use (this will not change).

Notation: a pattern in eleven's 630 list is mentioned as EL<xxx>c<yyy>, where <xxx> is the number of cells in the pattern and <yyy> is its place in the original <xxx> list.
When an ORk relation based on such a pattern is found, it appears as e.g.:
EL13c259-OR2-relation for digits: 2, 4 and 9
in cells (marked #): (r3c5 r1c2 r1c4 r2c7 r2c1 r2c6 r5c2 r4c7 r4c1 r4c5 r6c7 r6c3 r6c5)
with 2 guardians (in cells marked @) : n6r2c7 n1r6c5

Code: Select all

   +----------------------+----------------------+----------------------+
   ! 12489  249#   3      ! 249#   5      6      ! 7      128    149    !
   ! 249#   5      7      ! 1      8      249#   ! 2469#@ 23     3469   !
   ! 12489  6      2489   ! 3      249#   7      ! 5      128    149    !
   +----------------------+----------------------+----------------------+
   ! 249#   8      1      ! 6      249#   3      ! 249#   7      5      !
   ! 56     249#   56     ! 249    7      8      ! 1249   123    1349   !
   ! 7      3      249#   ! 5      1249#@ 1249   ! 249#   6      8      !
   +----------------------+----------------------+----------------------+
   ! 35689  7      5689   ! 89     169    159    ! 136    4      2      !
   ! 2469   249    2469   ! 7      3      1249   ! 8      5      16     !
   ! 234568 1      24568  ! 248    246    245    ! 36     9      7      !
   +----------------------+----------------------+----------------------+

Cells "in the pattern" are automatically marked with a # and cells with a guardian are automatically marked with a @

Chain rules appear in standard nrc notation, with the prefix EL<xxx>c<yyy>-OR<k>-<chain-type>[<chain-length>], e.g.:
EL13c259-OR2-whip[3]: OR2{{n1r6c5 | n6r2c7}} - b9n6{r7c7 r8c9} - r8n1{c9 .} ==> r6c6≠1

I've started to run all these rules + Tridagon on a small part of mith's larger collection of 158,276 T&E(3) min-expand puzzles. I have concentrated on puzzles with a smaller W+OR5W rating when the 630 patterns are activated (Tridagon being always activated).
It's too early to provide interesting results, but it already seems that:
- a lot of ORk-relations are found, but most of them have large numbers of guardians; this has led me to restrict the relations to 6 guardians, but this is a parameter that can be changed by the user in the config file;
- some patterns appear much more often that others. Indeed, in 1000 puzzles, I've seen only a few lead to effective eliminations;
- one might have wondered if adding 3*(630-38) = 1176 resolution rules to SudoRules would crash it. But no; most of the puzzles tried until now are solved in a few seconds.
Notes:
- the factor 3 is for the activation rule, the original pattern and the diagonally symmetric pattern
- the activation rule is lightweight
- the other two rules have complex conditions, about 3*<xxx> conditions if the pattern has <xxx> cells.


If you're interested in more examples with these patterns, see the puzzles I'll propose in the puzzles section when I find noteworthy ones.

[Edit, Feb 20, 2023]: I changed the order of components in the printed form of ORk-relations, so that the order is consistent with the generic one of ORk-chain rules: they will now be printed as:
EL<xxx>c<yyy>-OR<k>-relation
instead of the previous: OR<k>-EL<xxx>c<yyy> relation
My old posts in the Puzzles section will not be changed.
This is just a cosmetic change, with no bearing on understandability.
.

.
First results.
I've started a systematic study of the resolution power of eleven's 630-38 impossible patterns (Imposs630), in presence of the tridagon pattern, in the conditions described above.
One thing I've changed is the maximum number of guardians allowed. I have several examples where more than 6 guardians are useful.

My method was to compare the level Ln reached by resolution in the following two selections of rules:
1) Wn + OR5Wn + Trid
2) Wn + OR5Wn + Trid + Imposs630
In both cases, I have limited n (the max length allowed for chains of any type) to 8, in order to keep computation times in reasonable bounds.

On the first 4000 puzzles in mith's list of 158,276 T&E(3) min-expand puzzles, 203 (i.e. 5%) have a different level (of course smaller) in the second selection.
Among these 203 puzzles, 90 become solvable and 113 only get a smaller rating.

It also appears that only a few patterns lead to effective eliminations. Which patterns probably depends on the priorities chosen (described in my previous post).

I'll be posting examples in the Puzzles section and analyse later in this thread the corresponding patterns.
.

.
The most frequent impossible 3-digit patterns in two bands

Patterns are shown below with free cells marked with an "o". Free cells are important when looking for patterns. I give two isomorphic forms: eleven's original one, plus an isomorphic one that I manually tried to make look as close as possible to tridagon.

Reminder: The tridagon pattern (= EL12c38):

Code: Select all

+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . . ! . X . ! . X . !
! . . . ! X . . ! X . . !
+-------+-------+-------+
! . . . ! X . . ! . . X !
! . . . ! . X . ! . X . !
! . . . ! . . X ! X . . !
+-------+-------+-------+
! o o o ! . . . ! . . . !
! o o o ! . . . ! . . . !
! o o o ! . . . ! . . . !
+-------+-------+-------+

Not surprisingly, the two most frequent impossible 3-digit patterns among eleven-'s 630 list in two bands (or two stacks) look close to tridaagon, with 9 free cells in 3 mini-columns. When they appear in a puzzle, most of their X cells are shared with those of the tridagon.

EL13c290 :

Code: Select all

+-------+-------+-------+
! . . . ! . . . ! . . X !
! . . X ! . . X ! . X . !
! . . X ! . X . ! X . . !
+-------+-------+-------+
! . . . ! . . X ! X . . !
! . . . ! . X . ! . X . !
! . . X ! . . . ! . . X !
+-------+-------+-------+
! . . . ! . . . ! . . . !
! . . . ! . . . ! . . . !
! . . . ! . . . ! . . . !
+-------+-------+-------+
........X..X..X.X...X.X.X.......XX......X..X...X.....X...........................

isomorphic to:

Code: Select all

+-------+-------+-------+
! . . . ! . . . ! . . X !
! . . X ! . . X ! . X . !
! . . X ! . X . ! X . . !
+-------+-------+-------+
! . . X ! . . . ! . . X !
! . . . ! . X . ! . X . !
! . . . ! . . X ! X . . !
+-------+-------+-------+
! o o . ! o . . ! . . . !
! o o . ! o . . ! . . . !
! o o . ! o . . ! . . . !
+-------+-------+-------+

EL13c234 :

Code: Select all

+-------+-------+-------+
! . . . ! . . . ! . . X !
! . . . ! . . X ! . X . !
! . . X ! . . . ! X . . !
+-------+-------+-------+
! . . . ! . . X ! X . . !
! . . X ! . . X ! . . X !
! . . X ! . X . ! . X . !
+-------+-------+-------+
! o o . ! o . . ! . . . !
! o o . ! o . . ! . . . !
! o o . ! o . . ! . . . !
+-------+-------+-------+
........X.....X.X...X...X.......XX....X..X..X..X.X..X............................

isomorphic to:

Code: Select all

+-------+-------+-------+
! . . . ! . . . ! . . X !
! . . . ! . . X ! . X . !
! . . X ! . . . ! X . . !
+-------+-------+-------+
! . . X ! . . X ! . . X !
! . . X ! . X . ! . X . !
! . . . ! . . X ! X . . !
+-------+-------+-------+
! o o . ! o . . ! . . . !
! o o . ! o . . ! . . . !
! o o . ! o . . ! . . . !
+-------+-------+-------+

For an example where the two patterns (+ tridagon) are used in the solution, see: http://forum.enjoysudoku.com/116-in-63-137-or-158-276-t-e-3-min-expands-t40925.html.

.
Another impossible pattern that appears relatively frequently (less than the previous two) is EL10c4.
See http://forum.enjoysudoku.com/1000-in-63-137-or-158-276-t-e-3-min-expands-t40934.html for an example in a real puzzle.
Contrary to the previous two, this is quite far from tridagon.
It has only 6 cells free for having clues for the 3 digits in the pattern.

Code: Select all

     +-------+-------+-------+
     ! . . . ! . . . ! . . . !
     ! . . . ! . . . ! . . . !
     ! . . X ! . . X ! . . X !
     +-------+-------+-------+
     ! . . . ! . . . ! . . X !
     ! . . . ! . . X ! X X . !
     ! . . X ! X X . ! . . . !
     +-------+-------+-------+
     ! o o . ! . . . ! . . . !
     ! o o . ! . . . ! . . . !
     ! o o . ! . . . ! . . . !
     +-------+-------+-------+
....................X..X..X........X.....XXX...XXX...............................

isomorphic to:
     +-------+-------+-------+
     ! . . . ! . . . ! . . X !
     ! . . . ! . . X ! X X . !
     ! . . X ! X X . ! . . . !
      +-------+-------+-------+
     ! . . X ! . . X ! . . X !
     ! . . . ! . . . ! . . . !
     ! . . . ! . . . ! . . . !
     +-------+-------+-------+
     ! o o . ! . . . ! . . . !
     ! o o . ! . . . ! . . . !
     ! o o . ! . . . ! . . . !
     +-------+-------+-------+


.
Here are two more patterns, simultaneously illustrated here: http://forum.enjoysudoku.com/448-in-63-137-or-158-276-t-e-3-min-expands-t40945.html


EL15c97 (already seen in several puzzles, it was #37 in 15 cells, in eleven's previous shorter list of 380):

Code: Select all

.....X..X..X....X..X..X.X......X...X..X..XX...X.X...X............................
+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . X ! . . . ! . X . !
! . X . ! . X . ! X . . !
+-------+-------+-------+
! . . . ! . X . ! . . X !
! . . X ! . . X ! X . . !
! . X . ! X . . ! . X . !
+-------+-------+-------+
! o . . ! . . . ! . . . !
! o . . ! . . . ! . . . !
! o . . ! . . . ! . . . !
+-------+-------+-------+

 It can be morphed to a form much closer to the tridagon. Only one cell of the tridagon is missing (possibly solved); this cell is a member  of the unique rectangle made by the 12 tridagon cells; 4 cells are added. Note that there are very few free cells (3):
 +-------+-------+-------+
 ! . . . ! . . X ! . . X !
 ! . . X ! . . . ! . X . !
 ! . X . ! X . . ! X . . !
 +-------+-------+-------+
 ! . . . ! X . . ! . . X !
 ! . X . ! . X . ! . X . !
 ! . . X ! . . X ! X . . !
 +-------+-------+-------+
 ! o . . ! . . . ! . . . !
 ! o . . ! . . . ! . . . !
 ! o . . ! . . . ! . . . !
 +-------+-------+-------+

EL10c28:

Code: Select all

..............X..X..X..X.X...X........X.......X...X..X...........................
+-------+-------+-------+
! . . . ! . . . ! . . . !
! . . . ! . . X ! . . X !
! . . X ! . . X ! . X . !
+-------+-------+-------+
! . . X ! . . . ! . . . !
! . . X ! . . . ! . . . !
! . X . ! . . X ! . . X !
+-------+-------+-------+
! o . . ! o o . ! o . . !
! o . . ! o o . ! o . . !
! o . . ! o o . ! o . . !
+-------+-------+-------+

can be morphed to (which doesn't show much relation with the tridagon):
+-------+-------+-------+
! . . . ! . . . ! . X . !
! . . . ! . . . ! . X . !
! . . X ! X . . ! X . . !
+-------+-------+-------+
! . . X ! X . . ! . . . !
! . . . ! . . . ! . . . !
! . . X ! . . X ! . X . !
+-------+-------+-------+
! o o . ! . o . ! . . o !
! o o . ! . o . ! . . o !
! o o . ! . o . ! . . o !
+-------+-------+-------+

.
To continue with the topic of "how to deal...", here is how I select puzzles with potentially interesting impossible patterns in eleven's list.

I have almost finished classifying the 158,276 puzzles in mith's list of T&E(3) min-expands according to their Trid+W+OR5W rating, here noted Lx, restricted to chains of "reasonable" length, i.e. ≤ 8. Puzzles that might have a larger rating are classified as L99.

In parallel, I'm rating a small part of these puzzles according to their Trid+Imp630+W+OR5W rating, i.e. by adding to the previous rules all those that I derived from eleven's 630 patterns (rules that can only add ORk-relations).
When this is done, I check where the two ratings differ. I get something like:

Code: Select all

76   L99 --> L8
101   L99 --> L7
111   L99 --> L7
113   L99 --> L7
116   L99 --> L7
117   L99 --> L7
146   L99 --> L6
156   L99 --> L4
183   L99 --> L4
237   L99 --> L3
241   L99 --> L3
242   L99 --> L5
257   L99 --> L3
262   L7 --> L5
270   L8 --> L5
271   L8 --> L5
280   L99 --> L6

where the number on the left side is the position in the list and the Lx ---> Ly are the two ratings. Of course Lx is always larger than Ly.

The cases potentially most interesting are those where Lx = L99 and Ly is as small as possible. They are cases where the Imposs630 rules are the most effective.
It's interesting to note that, in the first 10,000 puzzles, only 625 (6.25%) have a different rating. It means that the 630 patterns are useful but not so much.

This is for the mechanised part. It reduces 10,000 puzzles to 625. It could reduce it even more if I kept only the L99 --> Ly

As for the rest, i.e. finding which patterns are effective in a puzzle, it's currently very time consuming; I have to do it all by hand.

What are my plans?
I'm still wondering whether I'll publish the (630-38)*3 rules generated from the patterns. In any case, because of how large this is, it would not be as a standard part of CSP-Rules but as an optional independent add-on. Alternatively (or complementarily), I could select a few of the most useful rules and add only them to SudoRules.
As for the current list of potentially interesting puzzles (wrt to these patterns), it's available to anyone who wants it: just send me a PM.

.
Pattern EL13c30, one more of the useful ones, with its closer to tridagon version

Code: Select all

..............X..X..X..X.X......X..X..X.X..X...XX..X.............................
+-------+-------+-------+
! . . . ! . . . ! . . . !
! . . . ! . . X ! . . X !
! . . X ! . . X ! . X . !
+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . X ! . X . ! . X . !
! . . X ! X . . ! X . . !
+-------+-------+-------+
! o o . ! . . . ! . . . !
! o o . ! . . . ! . . . !
! o o . ! . . . ! . . . !
+-------+-------+-------+

isomorphic to:

+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . X ! . X . ! . X . !
! . . X ! X . . ! X . . !
+-------+-------+-------+
! . . . ! . . X ! . . X !
! . . X ! . . X ! . X . !
! . . . ! . . . ! . . . !
+-------+-------+-------+
! o o . ! . . . ! . . . !
! o o . ! . . . ! . . . !
! o o . ! . . . ! . . . !
+-------+-------+-------+

[Edit:] used in this puzzle http://forum.enjoysudoku.com/156-in-63-137-or-158-276-t-e-3-min-expands-t40959.html

Concerning the classification of those patterns, there are some easy things to be said if we view them as graphs (subgraphs of the sudoku graph, induced by the restricted cells, to be precise):

First of all, there exist impossible patterns of k digits that are k-chromatic as graph. In these cases, either the sudoku grid can't be completed for the restricted digits (as is for example the case for the "sausage roll" pattern found in the "chromatic patterns" thread) or the restricted digits can be completely filled in, but the other digits can not (examples for higher k in the same thread). I don't have a good name for the first category ("pseudo-chromatic" might work?), but for the second one Marek came up with "co-chromatic", which is very appropriate.

The 680 puzzles in eleven's list are neither pseudo- nor co-chromatic, but 4-chromatic when viewed as graphs.
For completeness I also verified they are indeed 4-chromatic and minimal (any sub-pattern is 3-chromatic at most).

The first obvious thing to do is to check for graph-isomorphism; the following patterns are graph-isomorphic:

Numbers referring to eleven's lists. (note: There is a mistake in the 10c list. The pattern in line 11 has 4 cells in box 6, the removal of neither of which results in an impossible pattern. So I ignored this one, but kept the numbering for the following 10c patterns)

Two patterns that are graph-isomorphic can well behave slightly differently in a puzzle context. But they have identical proofs of k-chromaticity, so they should, in my opinion, belong to the same class in any pattern classification. (I'm not saying the isomorphy-classes should be the classes)

Going further than that, I did have the idea a while ago of searching for the critical subgraphs within those patterns (these are graphs such that any removal of an edge or vertex results in a smaller chromatic number).
The idea was to find a small set of critical subgraphs which cover all the patterns and can be used for classification. So if some pattern belongs in the class of some critical subgraph, then it is at most as hard to prove as this subgraph (which could be measured in something like T&E depth or its Hajós number).

The drawback is that the patterns can be a lot easier to prove (due to extra edges) than the critical subgraph they are classified by.
Also finding those critical subgraphs is rather expensive computationally. I have done it only for the smaller patterns in (a previous version of) eleven's list.

.
Hi ryokousha
Very interesting remarks.
I think our works are very complementary (and with mith's work also): you (and eleven) find and study impossible patterns, mith finds puzzles with them and I study rules that can make use of them. Sure, there's some overlap, but I think that's the main difference between us and this is useful to keep in mind to understand why my view of the patterns is slightly different.

ryokousha wrote:Concerning the classification of those patterns, there are some easy things to be said if we view them as graphs (subgraphs of the sudoku graph, induced by the restricted cells, to be precise):

To be still more precise, you're talking of the full subgraph of the sudoku graph for the candidates in the pattern (i.e. it inherits all the sudoku links between candidates in the pattern). Which of course keeps all this very sudoku-specific. This will be useful to remember when we come to your last point.

ryokousha wrote:First of all, there exist impossible patterns of k digits that are k-chromatic as graph. In these cases, either the sudoku grid can't be completed for the restricted digits (as is for example the case for the "sausage roll" pattern found in the "chromatic patterns" thread) or the restricted digits can be completely filled in, but the other digits can not (examples for higher k in the same thread). I don't have a good name for the first category ("pseudo-chromatic" might work?), but for the second one Marek came up with "co-chromatic", which is very appropriate.

In SudoRules (or any CSP-Rules application), this distinction is taken care of by the difference between restricted-T&E(n) and full T&E(n). See my results about this in a previous post.
Only 9 patterns fall in the second category when n=2. Tridagon = EL12c38 requires n=3 and falls in restricted T&E(3).
Also, all the patterns fall in restricted-T&E(3).

ryokousha wrote:The first obvious thing to do is to check for graph-isomorphism; the following patterns are graph-isomorphic:

It would be interesting to know which sudoku isomorphisms these graph isomorphisms break.
In the same order of ideas, it would be interesting to know which of these patterns enjoy row-column symmetry (more precisely diagonal or anti-diagonal symmetry modulo sudoku isomorphisms). I asked eleven but he didn't answer. I don't have the software to check this.

ryokousha wrote:(note: There is a mistake in the 10c list. The pattern in line 11 has 4 cells in box 6, the removal of neither of which results in an impossible pattern. So I ignored this one, but kept the numbering for the following 10c patterns)

Interesting. I hadn't noticed. As a result, my corresponding resolution rule couldn't be applied (there's an inner consistency test between the declared number of cells and the real one). I'll correct this.

ryokousha wrote:Two patterns that are graph-isomorphic can well behave slightly differently in a puzzle context. But they have identical proofs of k-chromaticity, so they should, in my opinion, belong to the same class in any pattern classification. (I'm not saying the isomorphy-classes should be the classes)

I agree with this in theory. However, when it comes to using these patterns for resolution, a slight difference can turn into a huge one in a real sudoku. The reason is, any deletion of a single candidate has unpredictable consequences.

ryokousha wrote:Going further than that, I did have the idea a while ago of searching for the critical subgraphs within those patterns (these are graphs such that any removal of an edge or vertex results in a smaller chromatic number).
The idea was to find a small set of critical subgraphs which cover all the patterns and can be used for classification. So if some pattern belongs in the class of some critical subgraph, then it is at most as hard to prove as this subgraph (which could be measured in something like T&E depth or its Hajós number).

I see two very different points here from the PoV of applicability in resolution rules:
1) Removing a vertex (i.e. a candidate) from the pattern; it wouldn't be a big problem for me. Dealing with kl-digit (or even klm-digit patterns) is not much harder than k-digit ones. Note that removing a known digit from the pattern is very different from allowing degenerate patterns that might have (unknown in advance) missing digits in any cell of the pattern (a computationally much harder problem).
2) Removing an edge, i.e. a link between candidates, is a very different story; this puts us out of the kingdom of Sudoku. Note that this wouldn't be a big problem for me either, in theory, because MapRules could be used as the solver instead of SudoRules (MapRules can indeed deal with any graph (i.e. not necessarily planar, as the name might suggest).

ryokousha wrote:The drawback is that the patterns can be a lot easier to prove (due to extra edges) than the critical subgraph they are classified by.
Also finding those critical subgraphs is rather expensive computationally. I have done it only for the smaller patterns in (a previous version of) eleven's list.

Sure, but maybe you could have an intermediary step, where you remove only candidates (but keep all the sudoku links between the remaining ones). That would be very interesting in itself for sudoku, as it would allow to deal with degenerate versions of the full patterns.
Could you give a few examples of such critical subgraphs ?

I broadly agree with all you say. There is an important misunderstanding we need to clear up, so we're talking about the same thing:

denis_berthier wrote:.

ryokousha wrote:Concerning the classification of those patterns, there are some easy things to be said if we view them as graphs (subgraphs of the sudoku graph, induced by the restricted cells, to be precise):

To be still more precise, you're talking of the full subgraph of the sudoku graph for the candidates in the pattern (i.e. it inherits all the sudoku links between candidates in the pattern). Which of course keeps all this very sudoku-specific. This will be useful to remember when we come to your last point.

No. I'm talking about (subgraphs of) the graph where the cells are the nodes and an edge exists when two cells see each other: https://en.wikipedia.org/wiki/Sudoku_graph
The full graph between candidates is of course also interesting, in particular isomorphic subgraphs. I'm not entirely sure in what context coloring/chromaticity on that full graph would be useful (maybe for broken wings / patterns which mix restricted candidate choices in cells and restricted locations for candidates in houses?). What does coloring of single candidates even mean?
Anyway, I'm not concerned with the full graph at the moment.

For the critical subgraphs mentioned, mith and I explored these a bit in this document: Chromatic Patterns in Sudoku.
The idea being to find a certain set of techniques required to prove (the 4-chromaticity of) those subgraphs and thereby the patterns. The proofs in the document were done manually, but I have since made a script to auto-generate them (it can't do x-wing or other fish logic yet nor parity arguments which would be required for the tridagon and such - it will revert to bifurcations instead).
A far goal would be to have a computer solver that not only can recognize such patterns in a puzzle by pulling them from a "library" and just stating that they are impossible, but is able to check any set of restricted cells in a puzzle for chromaticity and give a proof of the fact when appropriate.

Note: The pattern numbers in the correspondence diagrams of critical subgraphs to patterns refer to the earlier, not exhaustive version of eleven's list.

To make a concrete example, let's consider the Patto Patto pattern:

Code: Select all

+-------+-------+-------+
 ! . . . ! . . . ! . . . !
 ! . X . ! . X . ! X . . !
 ! . . . ! . . . ! . X . !
 +-------+-------+-------+
 ! . . . ! . . . ! . . . !
 ! . X . ! . X . ! . X . !
 ! . . . ! . . . ! . . . !
 +-------+-------+-------+
 ! . . . ! . . . ! . . . !
 ! . X . ! . X . ! . X . !
 ! . . . ! . . . ! . . . !
 +-------+-------+-------+


A common proof being that in any 3-coloring the cells r58c25 must have a repeated color due to the pigeonhole principle, which pushes this color twice into b3.

The (only) critical subgraph of this pattern is A3 in the document. It is missing an edge compared to the full graph of the pattern. This is saying we don't need r2c2 and r2c5 (alternatively r5c8 and r8c8) to see each other for the pattern to be impossible.
This graph A3 is not embeddable in classic 9x9 sudoku (I have ways to check that), but for example with additional anti-knight:

Code: Select all

+-------+-------+-------+
 ! . . . ! . X . ! . . . !
 ! . X . ! . . . ! X . . !
 ! . . . ! . . . ! . X . !
 +-------+-------+-------+
 ! . . . ! . . . ! . . . !
 ! . X . ! . X . ! . X . !
 ! . . . ! . . . ! . . . !
 +-------+-------+-------+
 ! . . . ! . . . ! . . . !
 ! . X . ! . X . ! . X . !
 ! . . . ! . . . ! . . . !
 +-------+-------+-------+


The proof of A3 applied to the pattern is then slightly more complicated than the above one:
The color of r2c7, say red, must appear twice in r58c25. If r1c5 and r2c2 are then both green, green would repeat in r58c5. If they are green and yellow, r58c8 become green and yellow, r3c8 becomes red, repeating red in b3.

To summarize, whether all those patterns can exist in a puzzle in sufficiently non-degenerate form, how such puzzles could be found, which useful guardian configurations are possible on which patterns etc. are all important questions.
But for the moment I'm solely concerned with finding such patterns and collecting a set of techniques required to prove them. The techniques do exhibit a certain "hierarchy of abstraction" if we search to avoid bifurcations. Some patterns can be proven by a simple contradictive coloring (specifically using "diamonds" - two cells that don't see each other but both see two more cells that also see each other), others require something like x-wings, bivalue oddagons (or more generally odd-length bivalue chains) up to TH / tridagon which - if we want to avoid any bifurcation - needs the "parity flow" argument considering permutation parities of 3 colors/digits.
Even larger patterns currently not in eleven's list need yet more abstract concepts. I gave an example of a 27c pattern in the chromatic pattern thread requiring the concept of "spin" to avoid bifurcating proofs.

The position of a pattern in that hierarchy might then lead to some sort of classification for the patterns reflecting their "hardness".