The New Sudoku Players' Forum

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

[denis_berthier]

.
In the CSP-Rules Examples (https://github.com/denis-berthier/CSP-Rules-Examples), I added the gB ratings for the cbg-000 collection.
.

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