The New Sudoku Players' Forum

[denis_berthier]

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

.

[denis_berthier]

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

[denis_berthier]

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

[denis_berthier]

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

[denis_berthier]

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

[denis_berthier]

.

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

[denis_berthier]

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

[denis_berthier]

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

[denis_berthier]

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

.

[denis_berthier]

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

[denis_berthier]

.
Today's update on GitHub revolves around function solve-knowing-solution.
It is now compatible with T&E at any level (it was previously designed to work only with resolution rules)

Companion functions have also been added to deal with files of puzzles in the standard line format, with-syntax:
(solve-n-grids-after-first-p-from-text-file-knowing-solutions ?puzzles-file ?solutions-file ?p ?n )
(solve-n-grids-after-first-p-from-text-file-knowing-solutions-excluding ?puzzles-file ?solutions-file ?p ?n ?excluded-list)
[?excluded list is useful if you know some puzzles in the list are e.g. in B4B and you want to check which are in B5B)

This allows to reduce computation times for the T&E-depth of any puzzle or for the BpB rating for puzzles in T&E(2).
Beware that reduction in time is quite varying, between 0 and 50%.
The best improvement I observed was on Hendrik's list of 384 (383 non redundant) hard puzzles, while showing that only 43 are in T&E(3), i.e. the other ones are solved in T&E(2): 50% reduction.
Note: the good point is, the gain seems to be larger for the hardest computations.

Note that, if you need to compute solutions (e.g. by DFS),
(record-solutions-n-grids-after-first-p-from-text-file ?puzzles-file ?p ?n ?solutions-file)
will record them in file ?solutions-file.
Note that only ?n lines will appear in ?solutions-file.
It is supposed that the set of selected rules is enough to solve all the puzzles; otherwise, some lines will be incomplete. Anyway, this function is mainly intended for use with DFS.

Update of the User Manual remains to be done.
.

[denis_berthier]

.

With the new SHC, how to know which of SudoRules or SHC to use?

It's not really a problem. They are based on the same theoretical background but their goals are very different:

1) SudoRules:
- SudoRules has been designed to implement resolution rules in the most straightforward way, based on the technique of pattern-matching (with the secondary benefit that I'm certain it can include no hidden ad hoc pieces of code in addition to the rules themselves: the rules are the code.
This approach has recently allowed me to code ORk-relations deducible from eleven's 630 impossible patterns in a few days only (which no other solver is still able to do after 1+ year).

- SudoRules can mix different types of rules, in almost unlimited combinations: any types of chain rules, Subsets, exotic patterns...

- SudoRules is only a small part of CSP-Rules, which can be applied to any finite CSP. The SHC is Sudoku-specific.


2) The SHC:
The SHC has been developed by François Cordoliani (alias Defise on this forum) with a very specific goal: computing four ratings/classifications and computing them fast:

the T&E-depth of any puzzle,
the B classification for puzzles in T&E(1),
the BpB classification for puzzles in T&E(2),
the BpBB classification for puzzles in T&E(3).

The fundamental classification by T&E-depth has already proven to be very useful in the search for the hardest puzzles, with millions of new ones in T&E(3) found by mith.
The BpB classification of puzzles in T&E(2) should be as useful for finding hard puzzles in T&E(2). But it appeared there was no tool fast enough to allow doing this in any practical way. So, this should become the major use of the BpB classification. This was the main motivation for developing the SHC.
The BpBB classification of puzzles in T&E(3) is mainly intended to check if all the puzzles found in T&E'(3) are in B2BB, as all those found until now.

Of course, SudoRules already allowed to do all these calculations and it has been used in the past to do them on a large scale (see [PBCS] and [UMNR]), but it's too slow for being used in the process of generating puzzles. The SHC is now the proper tool for all these calculations.


I could continue the listing of differences, but this should be enough to see the main ones and to help you choose which tool to use for which purpose.
.

[denis_berthier]

.
Today's update on GitHub includes:

GENERIC:
- allow focusing in ORk-chains;
- splitting-rules can now act on up to 16 guardians (instead of 12 before);
- add pretty-print-RS at the end of each h phase in T&E, at any level.

SUDOKU:
- add function solve knowing-solution-sukaku-grid;
- add the detection of degenerate cyclic anti-tridagons and the assertion of corresponding ORk-relations.
.

[denis_berthier]

.
Today's update on GitHub includes SudoRules function for extracting puzzles that have a given rating or that have a rating above a given value.

(extract-puzzles-with-value ?puzzles-file-in ?values-file ?file-len ?value ?puzzles-file-out)
(extract-puzzles-with-value-greater ?puzzles-file-in ?values-file ?file-len ?value ?puzzles-file-out)
As usual:
?puzzles-file-in is the full path to the file of puzzles;
?values-file is the full path to the file of their values for some rating/classification system (or nb of clues....);
?file-len is the length of ?puzzles-file-in;
?value is the target value or the (inclusive) lower bound for it;
?puzzles-file-out is the full path to the file of puzzles that satisfy the criterion.

This may be useful e.g. for:
- extracting T&E(1) puzzles with a high W or B rating, or a high SER (or FPGX), or a high number of clues, or a high number of candidates after BRT (or W1) (knowing all their W/B/... ratings);
- extracting T&E(2) or T&E(3) puzzles from a mixed list of hard puzzles (knowing all their T&E-depths);
- for extracting T&E(2) puzzles with a high value of their BpB rating (knowing all their BpB ratings).

I have used these functions to analyse Hendrik, Paquita, Coloin and JPF recent collections.
.

[denis_berthier]

.
Two updates on GitHub today:

1) CSP-Rules (https://github.com/denis-berthier/CSP-Rules-V2.1):
- a few cosmetic changes
- cleaning of the statistical and comparison functions
- addition of statistical and comparison functions (yet to be documented in the Manual, but examples of use are present in the "CB-stats.clp" file of the Controlled-bias collection)

2) Controlled-bias collection (https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection):
- addition of the gW ratings for the full collection
- detailed comparison with the W ratings
.