Sudoku Players' Forum (clone)

.
Today's update on GitHub consists of:
- addition of a few functions for isomorphisms in SudoRules/Goodies
- addition of functions for the analysis of k and kl digit patterns in SudoRules/Advanced; they allow in particular to find which 3-digit patterns are in T&E(2) - both restricted form and full form.
- addition of the generic ORk-splitting rules, working on ORk-relations and allowing shorter ORk-chains
- corresponding update of the "Augmented User Manual"

.
I posted on GitHub new functions announced in my previous post but that I forgot to include in the previous update:
- addition of functions for the analysis of k and kl digit patterns in SudoRules/Advanced; they allow in particular to find which 3-digit patterns are in T&E(2) - both restricted form and full form [that's the new part].

.
Today's update on GitHub doesn't yet contain the 4*(630-38) rules for eleven's 630 impossible patterns. (They are coming soon.)
But they contain all the updates that will make them work smoothly, i.e. the following:
- update of all the ORk-chains and ORk-g-chains in order to allow them to track the ORk-relations they use; this was useless as long as the only ORk-relation was tridagon, but it's now required in order to find which impossible patterns are the most useful. This doesn't change in any way the ORk-chain rules; it only adds a variable to keep track of the ORk-relations used;
- similar update for the ultra-persitency rules;
- corresponding update of all the functions that solve files;

- additions of functions to normalise patterns *, to do some elementary analysis of them and to pretty-print them with additional information (free cells...).
- complete the SudoRules configuration file with many options for activating all or part of the impossible patterns (these options are mentioned as "forthcoming"; they will work only after the 4*(630-38) rules for eleven's 630 impossible patterns are added. I included this in order to give an idea of what's coming soon; details of which patterns are "selected" may change.


(*) examples of pattern functions:

Note that the "pretty-print" function can print an 81-character pattern-string, not only a puzzle-string.

Code: Select all

(normalise-k-digit-pattern-string "000000001001001010001010100000001100000010010001000001")

will give

Code: Select all

"........X..X..X.X...X.X.X.......XX......X..X...X.....X..........................."

Code: Select all

(browse-k-digit-pattern 3 "........X..X..X.X...X.X.X.......XX......X..X...X.....X..........................." TRUE)

wil give:

Code: Select all

   9 cells free for pattern digits: (r7c1 r7c2 r7c4 r8c1 r8c2 r8c4 r9c1 r9c2 r9c4)
   3 rows with no cell in the pattern: (r7 r8 r9)
   3 columns with no-cell in the pattern: (c1 c2 c4)
   3 blocks with no-cell in the pattern: (b7 b8 b9)
   1 bands with no-cell in the pattern: (B3)
   0 stacks with no-cell in the pattern: ()

     +-------+-------+-------+
     ! . . . ! . . . ! . . 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.X.X.......XX......X..X...X.....Xoo.o.....oo.o.....oo.o.....

FALSE instead of TRUE will skip the pretty-printing of the pattern.

Code: Select all

browse-k-digit-patterns-file ?k ?len ?pattern-file TRUE

will do the same for each pattern in the file.

.
Today's big update on GitHub includes:

- all the rules necessary to deal with eleven's 630 impossible 3-digit patterns in two bands or two-stacks. Note that these Sudoku-specific rules produce ORk-relations, intended to be exploited by CSP-Rules generic ORk chain rules;

- a new part of the SudoRules config file, allowing a large array of options for selecting relevant subsets of these rules;

- an update of the "Augmented User Manual" with, in particular, a full new chapter dedicated to these rules and how to use them. It develops what I've first introduced here: http://forum.enjoysudoku.com/how-to-deal-with-large-numbers-of-patterns-t40889.html. The most often found patterns are described in full detail, together with their proximity to tridagon.

.

a user that wants to remain anonymous wrote:In your presentation of CSP-Rules on GitHub, you write: "Instead of having zillions of application-specific rules (like e.g. most existing rule-based Sudoku solvers), the resolution backbone of CSP-Rules consists of only a few types of universal rules".
However, in your last update you added some 2400 very specific rules. Is this not a big contradiction?

Good question.
Note that the cited sentence is immediately followed by " - though it remains perfectly compatible with the addition of any number of application-specific rules (see the Slitherlink chapter)."
The newly added rules show again, if necessary, what I said in this non-cited part of my sentence.

But, to answer the core of the question:

1) The newly added ~2400 rules are about very rare "exotic" patterns. They don't belong to the CSP-Rules backbone. They are mainly intended for (extremely rare) puzzles in T&E(3) - though some of them might be more broadly useful (this remains to be assessed).

2) The part of the CSP-Rules backbone relevant for these new rules is made of:

- the generic ORk-chain and ORk-g-chain resolution rules,
- the generic ORk-rules for ensuring ultra-persistency of the ORk-relations.

All these rules for dealing with ORk-relations are a relatively recent extension to the CSP-Rules generic backbone. They are useful to deal with exotic patters, i.e. in rare cases.
These generic rules still belong to a very limited number of types of rules.

3) There's much more in the last update than ~2400 new rules. There's chapter 15 of the Augmented User Manual ([AUM]), where 4 small selections of the ~2400 rules are presented, based on hundreds of hours of computation. These selections appear in the configuration file.
Most of the selected patterns are close to "tridagon", probably the most perfect pattern in terms of symmetry and ease of finding.
Nobody is expected to learn 2400 rules.
My purpose was to find a small number of "useful" patterns which would take care of most of the cases. Read in particular section 15.8 to see the frequency of the selected useful patterns.
I think the situation for the 630 impossible 3-digit patterns will be similar to the one for non-uniqueness patterns ("deadly patterns": many are known, but few will ever be used in practice.

4) I've hesitated whether to publish the full set of rules or only a small selection. I've finally decided to publish everything, as a detailed example of how to use CSP-Rules for case studies.
I've always said CSP-Rules can't be compared to other solvers. It takes a strong stance on 100 % pattern-based solving, based on a few types of generic resolution rules and 0% ad hoc reasoning. The few useful patterns take care of the ad hoc reasoning parts that appear in other solutions of some puzzles.

For practical solving, my recommendations remain to use these exotic patterns with care: select them progressively only if you don't get a solution without them (read details about this in the [AUM]).
.

.
Today's update on GitHub is about the fine tuning of the four pre-selected subsets of impossible patterns.
The selections are now based on the first 50,000 T&E(3) puzzles in mith's list of 158,276 min-expands (instead of 20,000 before).
Two new patterns have been added to the lower part of the list.
Globally, the four subsets are quite stable when puzzles are added to the analysis. Here are the numbers of puzzles (among the 50,000) where each pattern is "useful" (i.e. allows at least one elimination - when all chains lengths are restricted to 8). The partition into 4 sets appears quite naturally.

Code: Select all

Trid = 49089 (it's not 50000 because even if the pattern is present, it many not be useable by ORk-chains).

- In Imp630-Select1:
EL13c290 = 10863
EL14c30 = 6746
EL14c159 = 4241
EL14c13 = 3243
EL14c1 = 2737

- In Imp630-Select2:
EL13c30 = 1409
EL10c28 = 1375
EL13c179 = 1295
EL13c176 = 1159
EL13c234 = 925
EL13c171 = 742
EL10c6 = 738

- In Imp630-Select3:
EL13c259 = 577
EL10c8 = 509
EL13c172 = 413
EL13c187 = 378
EL10c4 = 378
EL13c175 = 371
EL14c19 = 360

- In Imp630-Select4:
EL14c93 = 273
EL15c97 = 234
EL14c154 = 160
EL10c10 = 157
EL13c170 = 155
EL13c168 = 153
EL13c19 = 150

This seems to support my idea that only a few of the 630 impossible patterns in two bands (or two stacks) are really useful (those in Select1 or Select2) - although quantifying this claim requires more investigations.

Note: a friend and user of SudoRules (and expert in finding whips) remarked that the recent updates are only for the few people interested in very rare puzzles. This is absolutely true (except for the generic ORk-chain and ORk-ultra-persistency rules). But notice that finding Trid-ORk-whips is not more difficult than finding ordinary whips; which should allow this expert friend to solve most of the puzzles in mith's list.

Notice also that these recent updates also illustrate the original nature of CSP-Rules as a research tool.

.

.
Today's small update on GitHub corrects very rare problems of unwanted interactions between (generic) splitting rules for different (application-specific) impossible patterns.
.

another user of CSP-Rules wrote:When you use impossible patterns in ORk-chains, instead of having what you call "ultra-persistency rules", why don't you identify the patterns only at the time when they are used in an ORk-chain? This would make your resolution paths much shorter.

When I publish a solution, I could easily discard manually all the ultra-persistency rules and move all the impossible pattern identification rules to the first place where the patterns are used in an ORk-chain (after deleting the candidates eliminated in the mean time). The resolution paths would indeed look much shorter.
But there are two reasons why I don't do this:
- it would be cheating with what CSP-Rules really does;
- it would suggest that degenerate forms of the pattern are identified when they are needed by an ORk-chain.

Identifying degenerate patterns is much harder than identifying the non-degenerate form. This first requires to decide how much degenerate patterns may be (e.g. how many missing candidates, in how many cells...) To make it simple, each missing candidate roughly multiplies by two the complexity of finding the pattern.

Notice that, from a purely technical PoV, as I have automatically generated (930-38)*4 rules for eleven's impossible patterns, I could almost as easily generate variants of such rules with missing candidates, thus multiplying the number of rules by a factor as large as needed to allow n missing candidates.
But no. If there is one thing that will not change in CSP-Rules in relation to impossible patterns, this is it: there will never be degenerate forms of them.
Generic ultra-persitency rules are a much smarter way of dealing with degeneracy.
.

.
Today's minor update on GitHub is about the introduction of an IMP630-ORk-W set of preferences for puzzles in T&E(3).
Like all the other sets of preferences, it is intended to be used with function "solve-w-prefs", allowing to give a preference to ORk-whips over any other regular rules.
The set of rules effectively included in IMP630-ORk-W is defined as those selected in the configuration file for Imp630 patterns and for ORk-whips max-length. (It always includes Subsets+Tridagons.)
Notice that, like all the sets of preferences built on ORk-chains, it is rarely useful in practice, because ORk-chains naturally want to intermingle with regular chains in the solution of most T&E(3) puzzles. (This is similar to trying to solve a puzzle using only Subsets; most of the time, they are not enough; the corresponding set of preferences allows to get the most of Subsets before trying anything else.)

In anticipation of more users questions/objections about my continued focusing on T&E(3) puzzles, let me recall that the discovery of the tridagon pattern and of the Loki puzzle by mith, the recognition of Loki as a T&E(3) puzzle (the first known one) - with all the work that followed - is the only breakthrough that happened in the Sudoku world in the past few years. As such, it seems to me that T&E(3) puzzles, impossible patterns related to them and generic ORk-chain rules allowing to deal with them deserve some special attention.
And again, no, my work on the 630 impossible patterns is not in contradiction with my insistence on having only a small number of rule types: the 630 patterns are not intended for being used as such; they are only a step to the identification of a very small number of really useful ones (say those in Select1 or Select2), most of which appear as follow-ups of Tridagon.

Notice that, for CSP-Rules users not interested in this advanced topic, my recent additions don't change anything to the more elementary ways they can use CSP-Rules for easier puzzles. The Augmented User Manual and the config file are precisely designed to isolate such advanced topics from the basic ones.
.

.
In order to complete the SudoRules examples (now in a separate project), I've added a few examples of puzzles using eleven's 630 impossible patterns: https://github.com/denis-berthier/CSP-Rules-Examples.
For followers of this forum, they will not be new, as I have proposed most of them here.
.

.

anonymous user of CSP-Rules wrote:Why do you say that ORk-whips are "exotic".

I think I never said this. (Otherwise, let me know where I said this, so that I can correct it.)
Nor did I write anything like this in the User Manual.

The only reason I can see for you to have this impression is, in the generic part of CSP-Rules, all the ORk-chains and ORk-g-chains are in a folder named "CHAIN-RULES-EXOTIC". Don't attach too much importance to this. It could as well be named CHAIN-RULES-ORk".

What I said is, generic ORk-chains (which depend on application-specific ORk-relations for their effective use) are intended to be used only with ORk-relations derived from exotic patterns. Exotic-ness is the only reason why the ORk part is counted as only 1 in the total length of the ORk-chain resolution rules.
This is to be understood in the general framework developed in [PBCS]; I'm not mainly interested in solving puzzles, but in solving them in principled ways, using generic rules as much as possible - rules that have a natural complexity measure assigned to them, allowing to assess their resolution power.
Exotic patterns always disrupt any natural generic rating system; generic ORk-chains are a way of drawing the maximum of exotic patterns, while managing this disruption in a consistent way.

Conversely, ORk-chains are not intended to be used with ORk-relations deduced from frequently occurring patterns such as e.g. almost-Subsets. Of course, nothing prevents one from doing it in practice, but that would introduce an unjustified disruption of the natural lengths.
For a simpler example of the problem, take AICs with inner Subsets. I've always counted the length of such a chain by adding the lengths of the inner Subsets instead of only 1 for each of them. This is the only consistent way of defining the length of such an AIC.
Similarly, one would have to define the lengths of ORk-chains differently if non-exotic ORk-relations were used in them.
.

.
Minor update today on GitHub:
- the ORk-whips[1] now have a blocked version and it is selected by the same variable ?*blocked-Whips[1]* as the ordinary whips[1] (and therefore selected by default).
Remember that blocked versions of rules (which have now been the default in CSP-Rules for quite some time) allow a rule R to make all its possible eliminations before it is interrupted by a simpler one made available by the first elimination due to R.
Note that, while whips[1] appear in almost any puzzle not solvable by Singles, ORk-whips[1] are much more rare (even if considered only for T&E(3) puzzles). The change is therefore mainly for abstract consistency with the ordinary whips.
.

.
I've pushed to GitHub a small update of the subsets of impossible patterns, now taking into account the full set of 158276 min-expand puzzles for their definitions. (This implies it's the final update for these sets.)
Details have been announced here: http://forum.enjoysudoku.com/the-tridagon-rule-t39859-115.html
.

.
All my classification results of mith's 158,276 mi-expand T&E(3) puzzles are now available in a new repository on GitHub: https://github.com/denis-berthier/Classifications-of-TE3-Sudokus.

This consists mainly of several files of 158,276 lines each (with Unix endings):

- "Trid-OR5W-levels.txt" contains the classifications wrt SFin + W + Trid-OR5W,
- "Select1-OR5W-levels.txt" contains the classifications wrt SFin + W + (Trid+Select1)-OR5W,
- "Select2-OR5W-levels.txt" contains the classifications wrt SFin + W + Trid+Select2)-OR5W,
- "Imp630-OR5W-levels.txt" contains the classifications wrt SFin + W + (Trid+Imp630)-OR5W.

An additional file "Trid-OR5gW-levels.txt" contains the classifications of only the first 10,000 puzzles wrt SFin + gW + Trid-OR5gW.

Comparison of ratings in the above files can be done within SudoRules, using function "compare-level-files".
Details about the meaning of all this can be found in the last two chapters of [UMRN]https://www.researchgate.net/publication/372364607_User_Manual_and_Research_Notebooks_for_CSP-Rules).

There are many ways you can use the above results to find interesting examples of puzzles in T&E(3) and/or of impossible patterns. The following are just examples (in which you can use SudoRules function "compare-level-files" to find the differences):

- select puzzles solvable using only the most basic T&E(3) pattern, i.e. Tridagons, according to their SFin + W + Trid-OR5W level,
- select puzzles solvable using only Tridagons, but for which ORk-gchains are useful, by choosing those that have a Trid-OR5gW-level lower than their Trid-OR5W-level,
- select puzzles solvable in one of the Select subsets of impossible patterns, but not in the the next smaller one, by comparing their different levels,
- select puzzles requiring very rare impossible patterns by choosing those with their Imp630-OR5W-level lower than their Select2-OR5W-level...

This is indeed how I've selected most of the T&E(3) puzzles I''ve proposed in the Puzzles section.
Now, you can do the same by yourself.

[Edit]: the link to ResearchGate was broken. It should work now.

.

.
Added a small update of "User Manual and Research Notebooks for CSP-Rules" ([UMRN]).