The New Sudoku Players' Forum

[denis_berthier]

.
In order to allow the easy calculation of expansions of puzzles, I added to SudoRules (https://github.com/denis-berthier/CSP-Rules-V2.1) a function "record-expansions-n-grids-after-first-p-from-text-file", with syntax:

Code: Select all

(record-expansions-n-grids-after-first-p-from-text-file ?puzzles-file ?p ?n ?expansions-file)

As usual:

Code: Select all

?puzzles-file and ?expansions-file are file names
?p is the number of puzzles to be skipped (it will generally be 0)
?n is the number of puzzles to be expanded
?p + ?n is supposed to be ≤ the length of ?puzzles-file
the length of ?expansions-file will be ?n

Note that this function can be used for multiple purposes, depending on which rules are selected in the configuration file. The two most typical ones are:
- select only the rules in BRT (i.e. nothing in the configuration file) and you will get the file of expansions by Singles;
- select only DFS and you will get the file of solutions.

Warning: any other set of rules with the confluence property can be selected to make expansions with this function, but only the asserted values are taken into account in the results (eliminated candidates are not: i.e. the result is a Sudoku not a Sukaku). Whether such expansions may have any usefulness is up to the user to decide. IMO, they don't, because what they keep of the expansion process is arbitrary.
.

[denis_berthier]

.
I updated the Controlled Bias Collection (https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection) by adding more gB-ratings.
The purpose is not to change the stats (they are already quite precise, but to find cases of largest differences between the 4 ratings (W, gW, B, gB). See http://forum.enjoysudoku.com/pattern-based-constraint-satisfaction-2nd-3rd-eds-t32567.html for comments about the reults.
The collection with computed gB ratings now has over 3M puzzles (more than half of the total collection).

[Edit 2024 Feb. 03: the gB ratings are now computed for the whole collection of ~6M puzzles.]
.

[denis_berthier]

.
Addition of global variable ?*Imp630-list* for the easier tracking of impossible patterns in functions of type "solve-file".
A the end of the function, ?*Imp630-list* contains the IDs of the puzzles that have an impossible pattern (among those selected in the configuration file).

This comes in addition to the already existing: ?*tridagon-list* and ?*degenerate-cyclic-tridagon-list*.
.

[denis_berthier]

.
In order to make it easier to track (non-degenerate) tridagons and degenerate-cyclic tridagons when solving files of puzzles, at the end of calculations, the two global variables:
?*tridagon-list* and ?*degenerate-cyclic-tridagon-list* now contain the lists of puzzles numbers having respectively:
- a (non-degenerate) tridagon,
- either a non-degenerate or a degenerate-cyclic tridagon.

(The difference with before is, when both rules were activated together with other rules, ?*degenerate-cyclic-tridagon-list* might not have included all the non-degenerate cases (in case a puzzle was solved before the degenerate form was found) and some union of the two lists was necessary. This doesn't change my previously reported results, as I did this union). But it will avoid possible errors.
.

[denis_berthier]

What has changed is not clear....

First, if you are using SudoRules to solve puzzles one by one, nothing has changed.

There are 3 resolution rules for tridagons:
- one for the simplest 1 guardian case of the non-degenerate tridagon: it concludes on the deletion of the 3 tridagon candidates in the target cell (the resulting Single is dealt with by the basic Singles rule), and it sets global variable ?*has-tridagon* to TRUE;
- one for the multi-guardian case of the non-degenerate tridagon: it asserts a tridagon-ORk-relation, k≥2, and it sets global variable ?*has-tridagon* to TRUE;
- one for the degenerate-cyclic tridagon: it asserts a tridagon-ORk-relation, k≥1 (when k=1, the resulting Single is dealt with by an OR1 rule that does the same job as Singles), and it sets global variable ?*has-degenerate-cyclic-tridagon* to TRUE.
(The two non-degenerate cases could have been dealt with the same way, but the difference is the result of historical development and is irrelevant here.)
Note: the variables are set to TRUE in a way totally independent of the usefulness of the tridagon. They just mean that the pattern has been detected.

Note: the three rules can be activated almost independently by setting the corresponding global variable (?*Tridagons*, ?*Anti-Tridagons* or ?*Degen-Cyclic-Anti-Tridagons*) to TRUE in the configuration file. (?*Anti-Tridagons* automatically implies *Tridagons*)

For efficiency reasons, the degenerate-cyclic tridagon rule doesn't have explicit conditions for degeneracy, so that it also covers the non-degenerate case. Also, it has lower priority than the non-degenerate rules.

In case you solve files of puzzles, variables ?*has-tridagon* and ?*has-degenerate-cyclic-tridagon* are used by the solve-files functions to add the puzzle number to the corresponding global variable list ?*tridagon-list* or ?*degenerate-cyclic-tridagon-list* at the end of resolution of each puzzle.
There are puzzles that can be solved by the simplest tridagon rule and Triplets. In such a case, the degenerate-cyclic tridagon doesn't get a chance to be identified before the solution is reached: ?*has-tridagon* is set to TRUE but ?*has-degenerate-cyclic-tridagon* is not.
Before the last modification, this implied that the puzzle appeared in ?*tridagon-list* but not in ?*degenerate-cyclic-tridagon-list*. This wasn't a problem for me because I knew how it works and I did a union of the two lists, but it may have been confusing for other users.
(Why activate Triplets when checking the presence of tridagons? It is indeed very useful to eliminate trivial cases in which Triplets destroy the pattern before it can be identified.)

So, after the last changes, in every possible case, at the end of computations:
- ?*tridagon-list* is the list of all the puzzles that have a non-degenerate tridagon,
- ?*degenerate-cyclic-tridagon-list* is the list of all the puzzles that have either a non-degenerate or a degenerate-cyclic tridagon.

Note: I originally introduced these lists for my own research purposes. I hadn't planned to document them. But that's done.
.

[denis_berthier]

.
Today's update on GitHub is mainly about adding functions that have been useful while writing the second edition of [HCCS] (to be published soon):
- functions for recording some types of calculations in appropriate files;
- function for filtering the contents of resulting files acccording to various criteria;
- cleaning and expansion of statistical functions.
There''s currently no update to the User Manual: these functions will be described in [HCCS2].
.

[denis_berthier]

.
Today's update on GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1) has two new functions that may be useful in the search for new puzzles, in order to eliminate redundancies.

(puzzle-string-in-puzzle-file ?puzzle-string ?file ?file-length) : check if ?puzzle-string is already present in ?file; returns TRUE or FALSE

(puzzles-in-file1-not-in-file2 ?puzzle-file1 ?file-length1 ?puzzle-file2 ?file-length2): checks which puzzles in puzzle-file1 are already present in puzzle-file2; returns their list of line numbers

In order to get the list of line-number for puzzles that are new, you can combine this function with generic function "not-in-list$":
(not-in-list$ (puzzles-in-file1-not-in-file2 ?puzzle-file1 ?file-length1 ?puzzle-file2 ?file-length2) ?file-length1)

In turn, this list can be used within function "extract-lines-in-list" in order to get a file of the puzzles corresponding to it. Syntax:
(extract-lines-in-list ?puzzle-file1 ?file-len1 ?list ?file-out)
.

[denis_berthier]

.
I added the templates resolution method to GitHub. Templates are available up to template-depth 4.
(For definitions, see here: http://forum.enjoysudoku.com/templates-as-patterns-t44896.html)

Templates are perfectly compatible with any other rules.
But if you want a pure templates solution, don't forget to disable other rules in the config file.

Settings for templates in the config file are in section 4.1.

Note that there are several ways to control what's printed:
?*print-actions* controls the printing of "normal" rules, in the present case of the Singles rules.
?*print-templates* controls the printing of template rules that eliminate templates. (This implies many lines of printing.)

If you want to see still more details, you can activate the Clips function (watch facts) before launching any "solve" function. Any fact added or deleted will appear with a leading sign ==> or a <==.
Once the template rules start applying, the <== lines will correspond to automatic updating of the resolution state (i.e. truth maintenance).
.

[denis_berthier]

.
Today's update fixes a problem with eliminations of templates[3] that were not done automatically after a template[2] is retracted.
.

[denis_berthier]

.
Until now, there were functions to permute the rows, columns, bands (floors) and stacks (towers).
I've added functions to permute the digits (relabelling). Their output is a puzzle (in standard string format).

(relabel-9x9-puzzle-with-permutation(?puzzle-string ?perm)
;;; number ?i in the given puzzle becomes perm(?i) in the new puzzle

(random-relabel-9x9-puzzle ?puzzle-string)
;;; same, but with a random permutation

(random-isomorphic-9x9-puzzle ?puzzle-string)
;;; rows, columns, bands, stacks and digits randomly permuted (according to allowed isomorphisms).

.

[denis_berthier]

.
In SudoRules, I've added the possibility to arbitrarily select any set of impossible patterns in eleven's list of 630 ones.

This is controlled by two new global variables in new sub-section 2.3.2c of the config file:
;;; First declare you want to make your own selection (compulsory)
;;; this will cancel all previous selections of Imp630 (but not the tridagons):
; (bind ?*Select-Imp630-list* TRUE)
;;; Then select impossbile patterns by their names, e.g.:
; (bind ?*Selected-Imp630-list* (create$ EL14c30 EL13c259))


You don't have to know in advance the names I've given to these patterns:
usually, you'll want to do this after running a larger selection and checking the patterns effectively used in the solution.
This will clean the resolution path of all the useless patterns.
.

[denis_berthier]

.
Today's small update eon GitHub generalises the automatic application of eleven's replacement technique.
Until now, it was based on a block having a tridagon-like pattern of cells and candidates (i.e. 3 and only 3 candidates in the 3 cells).
Now, there may be a cyclic pattern of candidates in the 3 cells (as in the degenerate-cyclic-tridagon pattern).

Note that a replacement candidate may be chosen in one of the 3 cells even if it is no longer a candidate in it. This is irrelevant, because anyway, a relabelling (restricted to the 3 digits) must be made in the end in order to recover the original puzzle.
.

[denis_berthier]

.
Following my publication of a new GitHub repositoriy for the data supporting my results in [HCCS2] (see http://forum.enjoysudoku.com/hierarchical-classifications-in-constraint-satisfaction-t42076-7.html), I've added to SudoRules global variables that give direct access to the collections described there and that allow you to re-run the calculations just by copying into SudoRules all the commands that appear in the RESULTS.clp files of each folder. They are defined as:

Code: Select all

?*CSP-EX* = (str-cat ?*CSP-Rules* "CSP-Rules-Examples/”)
?*CBGC* = (str-cat ?*CSP-Rules* "CBGC/”)
?*SUDCL* = (str-cat ?*CSP-Rules* "SUDCL")

?*TE3-Mi* = (str-cat ?*SUDCL* "mith-158276-TE3/")
?*TE2-EL* = (str-cat ?*SUDCL* "eleven-26370-TE2/”)
?*TE2-PH* = (str-cat ?*SUDCL* "ph2010-3103972-TE2/”)
?*TE2-Paq* = (str-cat ?*SUDCL* "Paquita-2023-sept-dec-TE2/")
?*TE23-Mon* = (str-cat ?*SUDCL* "Monhard-until-2023-08-15-TE23/")
?*TE2-Col* = (str-cat ?*SUDCL* "Coloin-2024-09-03-B7B+/")
?*17c* = (str-cat ?*SUDCL* "Royle-49158-17c/")
?*18c* = (str-cat ?*SUDCL* "JPF-2000000-18c/")
?*38c* = (str-cat ?*SUDCL* "dob-2014078-38c/")
?*39c* = (str-cat ?*SUDCL* "dob-2650-39c/")

Using them as such supposes you have installed all the repositories in the CSP-Rules directory, that should look like:

Code: Select all

CSP-Rules    | CSP-Rules-V2.1
             | SHC (the Sudoku Hierarchical Classifier)
             | CSP-Rules-Examples
             | CBGC (the Controlled-Bias Generator and Collection)
             | SUDCL (the classification results of various Sudoku collections)
             | TE3-classif (deprecated, now included in SUDCL )
             | TE2-classif (deprecated, now included in SUDCL )

However, you can decide to install them at any other place. You'll only have to redefine the 3 top level directories, e.g.:

Code: Select all

(bind ?*CSP-EX* “/usr/me/CSP-Rules-Examples/”)
(bind ?*CBGC* “/usr/me/CBGC/”)
(bind ?*SUDCL* “/usr/me/SUDCL/")

and then type:

Code: Select all

(relocate-companion-folders)

in order to redefine the other variables.
.

[denis_berthier]

How many rules are there in SudoRules ?

I hadn't counted before the question. But it's easy to do it. After activating all the rules in the config file (with no limit on chain lengths), type (rules). You'll get a list of the rule names (one per line) plus a last line giving the number of rules: +11,500.

However, this number doesn't mean much (except that all the rules can be loaded together without creating any incompatibilities):
- this is the number of CLIPS rules, not the number of logical/conceptual rules; each of the last ones may use several CLIPS rules for its implementation (e.g. an activation rule, a tracking rule, a detection rule, an elimination rule);
- for most of the types of chains, there are rules up to length 36 (which has never been useful - the largest known whip length is 31);
- it includes the 4*(630-38) rules for 3-digit impossible patterns;
- it includes the 4*(408) rules for deadly patterns on 12 or fewer cells;
- it includes rules that no one would want to use together (e.g. rules simulating the T&E(3) procedure plus rules for g-braids[36]).

Finally, in anticipation of the next questions:
- no, I haven't written manually 11,500 rules; for most of them, I've first written a rule generator (which makes their testing drastically simpler);
- some rules occupy a few lines, some one or two pages (e.g. rules for impossible or deadly patterns).
- if the question was related to the "hesitation", the number of rules is irrelevant; rules are not "activated" and don't interfere with the resolution process before their "level" is needed (they don't slow the solution);
what may be relevant for you is whether or not you're interested in the approach; SudoRules allows you to select exactly the rules you want to use. Unless you're trying exceptional puzzles, you won't meet any problem. Whenever potential problems may arise with some rules (generally, memory overflow, such as with deadly patterns on many cells), this is signalled in the config file.
.

[denis_berthier]

.
I've just added to GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1) the 4*408 rules allowing to detect the 408 Deadly patterns in Blue's list. (http://forum.enjoysudoku.com/unavoidable-sets-vs-deadly-patterns-t45376-9.html).

DPs work in the same way as Impossible Patterns: they produce ORk-relations that are taken care of by generic ORk-chains. SudoRules has similar control variables for them.
Like most of the simpler rules for uniqueness, Deadly Patterns are not very useful in practice, but I've given in the Puzzles section a few of the rare examples where they more or less simplify the solution.

Soon, I'll publish an updated version of the User Manual, with all the details.
.