- Only the main updates to the original publication (in reverse time order) are listed below.
- Cosmetic changes (such as minor changes in the way things are printed) are not mentioned.
- Trivial additions to the globals, saliences or print functions (which may be necessary when new resolution rules are added) are not mentioned.
- All the changes from the first publication are indeed additions to the original functionalities; in particular:
-- no basic data structure has been changed ;
-- no fundamental generic resolution rule (i.e. bivalue-chains, z-chains, t-whips, whips, g-bivalue-chains, g-whips, braids, g-braids), as defined in [CRT] or [PBCS], has been changed (though the files that contain them may have been split into partial-chain extension rules and chain elimination rules);
-- no application-specific resolution rule, as defined in [CRT] or [PBCS] - such as Subsets in Sudoku or any application that has them, ascending-chains in Futoshiki, loops in Slitherlink... - has been changed (though their "blocked" and "unblocked" versions may may have been fused);
-- no bug has been found since the first publication (note that this software had been largely tested (on millions of instances) before the first publication). - Because they reflect changes to the software (almost) as soon as such changes are published, updates of the User Manual are not mentioned per se, except in case of a major update.
- add functions for filtering puzzles that have some fixed rating or have their rating above some fixed raing. This may be useful e.g. for extracting T&E(2) or T&E(3) puzzles from a mixed list of hard puzzles, or for extracting T&E(2) puzzles with a high value of their BpB rating.
- Extend ORk splitting rules upto length 16 (instead of 12).
- Allow focusing in ORk-whips.
- Add pretty-print RS after each phase.
- Add ORk-degenerate-cyclic-anti-tridagon.
- Add function solve-knowing-solution-sukaku-grid.
- Update of the generic T&E(n) procedures, addition of extra conditions in whips[1] and partial-whips[1] so as to allow compatibility with function solve-knowing-solution. Computation times are decreased in various porportions for BpB and T&E(2).
Addition of corresponding functions for solving files of puzzles knowing solutions.
- Update of the four subsets of selected impossible patterns, taking into account the latest classification of all the known T&E(3) puzzles.
- ORk-whips[1] now have a blocked version. It is selected by the same global variable ?*blocked-Whips[1]* as ordinary whips[1].
- Add the IMP630-ORk-W module for the impossible patterns in two bands or two stacks. Note that impossible patterns and ORk-whips effectively loaded in this module are those defined in the configuration file. This module also contains Tridagons and the reversible patterns: Subsets, bivalue-chains and z-chains. It allows to try a solution with mainly impossible patterns before allowing more advanced "regular" chains (t-whips, whips, g-whips, braids...).
- Add ORk-persistency rules to all the ORk-modules.
- Fine tune the four pre-selections of impossible patterns, based on their “usefulness” (see details in release 5 of the Augmented User Manual), a major step in finding the really useful patterns.
- Update the Augmented User Manual with a full new chapter about the impossible patterns and the general question of how to deal with large numbers of patterns.
- Add the 2488 automatically generated rules that can detect all the patterns in eleven's list of 630-38 impossible patterns in two bands (or two stacks). The output of these rules (ORk relations) can be used by all the generic ORk-chain rules.
- Complete the SudoRules configuration file with many options for activating all or part of the impossible patterns.
- Allow ORk chains and g-chains to track which ORk-relations they have effectively used (introduce global variables ORk-relations-used and all-ORk-relations-used-in-list for respectively a puzzle and a file of puzzles). This was not useful when there was only one ORk relation (tridagon) but it will allow to make statistics about which ORk relations are the most frequently used.
- Add functions to normalise patterns, to do some elementary analysis of them and to pretty-print them with additional information (free cells...).
- Note that the Sudoku-specific part of the "candidate" template in SudoRules has been extended with two slots (band and stack) for easier writing of the rules detecting the 630 impossible patterns. This has strictly no impact on anything existing before this change (especially on generic chain rules, which never use any application-specific slot, or on rules such as Subsets that do use Sudoku-specific slots, but continue not to use the two new ones).
- Add 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 (already published before) and full form (that's the new part).
*In functions that solve lists of puzzles, add global variables to check in how many puzzles any specified ORk relation has effectively been used and to estimate the resolution power of each impossible pattern.
- Add the ORk-splitting rules, for k ≤ 12, allowing to reduce the number of guardians in an ORk-relation and, possibly, to solve with shorter ORk-chains.
- Add the ORk-contrad-g-whips, for k = 6
- Add the full ORk-g-Whips for k ≤ 6.
- Add the ORk-forcing-g-whips, for k ≤ 6.
This completes the set of ORk chain and g-chain rules, now all defined for 2 ≤ k ≤ 6.
- Add the ORk-contrad-g-whips, for k ≤ 5 (and corresponding global variables allowing to use them in the SudoRules config file).
- Split the G-Whip files into G-Whip and Partial-G-Whip files (for easier use with ORk-Contrad-Whips). This implies no change for the ordinary G-Whips.
- All the ORk-relations of size ≤ 20 are now ultra-persistent. (Previously, size for applying persistency was limited to 12, but there are rare anti-tridagons with 20 guardians).
- Add Forcing2-T&E and Forcing3-T&E. They have been mentioned in the User Manual for a long time, but I had forgotten to post the code.
- Faster ORk-Whips for k>3 (irrelevant for k=2 or 3). They are about 30% to 50% faster (depending on many contextual factors) and they also use less memory.
For technical reasons, these improvements work only when ORk-forcing-whips are not active. Which version is used is automatic: the new, faster one if ORk-forcing-whips are not active, the original one otherwise.
- New, extended and largely restructured version of the user manual: "Augmented User Manual".
- addition of the TRIDAGON-ORk-W and TRIDAGON-ORk-CHAINS sets of preferences;
- addition of control variables related to Tridagons in the configuration file, in particular to choose the priority of Tridagon elimination and anti-tridagon detection rules.
- addition of ORk-whips, k≤6.
- addition of this UPDATES.md file.
- addition of the TRIDAGON-ORk-FW and TRIDAGON-ORk-CW sets of preferences.
- addition of ORk-Contrad-Whips, k=2,...6;
- addition of OR6-Forcing-Whips (ORk-Forcing-Whips, k=1,...5, were already available).
- functions "solve-k-digit-pattern-string", "solve-n-grids-after-first-p-from-k-digit-pattern-string-file" and "solve-n-grids-after-first-p-from-k-digit-pattern-string-file-excluding" now also work in combination with DFS.
- focusing now also works with DFS.
- addition of Forcing2-Whips (equivalent to Forcing-Whips) and Forcing3-Whips, based on the general ORk-Forcing-Whips and with (3D) bivalue or trivalue cells as starting points;
- addition of rules for automatically applying eleven's replacement method in the context of an anti-tridagon pattern.
- addition of ORk-forcing-whips (k≤5).
- addition of functions related to k-digit patterns: "solve-k-digit-pattern-string", "solve-n-grids-after-first-p-from-k-digit-pattern-string-file" and "solve-n-grids-after-first-p-from-k-digit-pattern-string-file-excluding".
Given a k-digit pattern (in string format) or a file containing a sequence of such patterns, these functions allow to solve them (e.g. to prove that they are contradictory).
When T&E is involved, they restrict the candidates that may be tried at each level to those in the pattern, thus taking advantage of the new generic feature of T&E. By avoiding to try unproductive candidates, this makes these procedures thousands to millions of times faster than standard T&E (depending on T&E-depth).
- all the generic T&E procedures (at depths 1, 2 and 3) are now sensitive to restrictions on the candidates they may try (at each level). They are totally unchanged in the default case. In and of itself, this only allows new possibilities, but doesn't offer them readily.
- addition of two separate sets of preferences: TRIDAGONS and TRIDAGON-FW;
- addition of functions for solving with preferences whole files of puzzles;
- addition of functions for applying manually the eleven replacement technique;
- in the SudoRules configuration file, addition of global variables related to the above additions;
- addition of rules for automatically applying eleven replacement techniques in cases "not too far" from to the trivalue oddagon impossible pattern.
- replacement of the CSP-Rules EXAMPLES folder by an independent "CSP-Rules-Examples" repository: https://github.com/denis-berthier/CSP-Rules-Examples.
- addition of the tridagon-forcing-whips and of the TRIDAGONS set of preferences.
- addition of the Tridagon elimination rule.
- addition of my book "Pattern-Based Constraint Satisfaction and Logic Puzzles (Third Edition)" in the Publications folder.
- addition of the "Basic User Manual for CSP-Rules-V2.1 (Second Edition)".
- introduction of sets of preferences and of function "solve-with-preferences" (also "solve-w-prefs"). Original sets of preferences are:
-- generic: BIVALUE-CHAINS, REVERSIBLE-CHAINS, REVERSIBLE-PATTERNS
-- Sudoku-specific: S4Fin.
- addition of "blocked" versions for z-chains (typed or not) and oddagons.
- update of the fewer-steps solving function, allowing to find shorter resolution paths; it can now take into account all the generic chain rules (except t-whips) and all the Subsets and Finned Fish.
- "blocked" and "non-blocked" versions of Subsets are merged,
- Subset rules become compatible with focusing (i.e. with function "try-to-eliminate"). (This is a major boost for focused eliminations and for reducing the number of steps).
- add functions for reducing the number of steps in a resolution path.
- add the Pandiagonal variant.
- add functions "find-1-steppers" and "find-2-steppers" for the fully automated search for 1- or 2- step solutions.
- add all the rules and functions necessary for looking for 1- or 2- step solutions.
- add functions: "pretty-print-sudoku-string" (also "pretty-print"), "pretty-print-sukaku-list" and "random-shuffle-9x9-puzzle" .
- add functions for printing the rc, rn, cn and bn views first introduced in [HLS 2007]:
-- "print-current-resolution-state" (also "print-RS"),
-- "print-current-resolution-state-rn-view" (also "print-RS-rn"),
-- "print-current-resolution-state-cn-view" (also "print-RS-cn"),
-- "print-current-resolution-state-bn-view" (also "print-RS-bn"),
-- "print-current-resolution-state-all-views" (also "print-RS-all").
- add function "find-sudoku-anti-backdoor-pairs" and first application to find a 2-step solution in Sudoku.
- add function "find-anti-backdoor-pairs".
- add function "find-sudoku-anti-backdoors" and first application of focused eliminations to find a 1-step solution in Sudoku.
- add functions "find-backdoors" and "find-anti-backdoors".
- focused eliminations now also work for z-chains (typed or not).
- focused eliminations now also work for bivalue-chains (typed or not).
- addition of the full set of functions:
-- "init-sudoku-string" (also "init"),
-- "init-sudoku-list",
-- "init-sudoku-grid",
-- "solve-sudoku-string" (also "solve"),
-- "solve-sudoku-list",
-- "solve-sudoku-grid"
-- and similar functions for sukakus.
- the resolution state is now printed at the end of the resolution path when a full solution is not found; combined with "solve-sukaku-list" or "solve-sukaku-grid", this allows resolution in stages.
- add function "try-to-eliminate-candidates" (focused eliminations); works for:
-- oddagons, whips (untyped), braids (untyped), g-whips (untyped) and g-braids (untyped),
-- forcing-whips, forcing-braids, forcing-g-whips and forcing-g-braids (where the focus is not applied to eliminated or asserted candidates but to the bivalue starting points).
- add functions "solve-sukaku-list" and "solve-sukaku-grid".
- add pre-computed backgrounds (making reoslution much faster for pre-computed square grids).
- add isolated chains and extended-loops.
- first public release of CSP-Rules-V2.1, including all the currently existing applications and the first edition of the "Basic User Manual for CSP-Rules-V2.1".
Notice that, apart from minor details, this core of CSP-Rules has remained unchanged in all the updates (indeed additions of functionalities) described in this file. This is why the version number (V2.1) has not changed.