The New Sudoku Players' Forum

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

[denis_berthier]

.

A few of Blue's deadly patterns are auto-symmetric (wrt to row-col symmetry). I've deleted the redundant cases (which doesn't change the resolution power or the resolution paths).
I've also put the symmetric forms of the rules in minlex form (which only changes the names of variables in the rules).

In order to facilitate the mapping of "abstract deadly patterns" to their instances in a real resolution state, I've added functions:
where ?c = number of cells and ?n = number in the list with ?c cells

Code: Select all

(pretty-print-deadly-pattern 10 12) gives:
(. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 12 . . . . . 13 . . 13 . . 34 . . . . 24 23 . . 34 . . 13 . 14 .)
+----------+----------+----------+
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  .  ! .  .  .  !
+----------+----------+----------+
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  .  ! .  12 12 !
+----------+----------+----------+
! .  .  .  ! .  .  13 ! .  .  13 !
! .  .  34 ! .  .  .  ! .  24 23 !
! .  .  34 ! .  .  13 ! .  14 .  !
+----------+----------+----------+

Code: Select all

(pretty-print-diag-sym-deadly-pattern 10 12) gives:
(. . . . . . . . . . . . . . . . . . . . . . . . . 34 34 . . . . . . . . . . . . . . . . . . . . . . . . 13 . 13 . . . . . . . . . . . . . . 12 . 24 14 . . . . . 12 13 23 .)
   +----------+----------+----------+
   ! .  .  .  ! .  .  .  ! .  .  .  !
   ! .  .  .  ! .  .  .  ! .  .  .  !
   ! .  .  .  ! .  .  .  ! .  34 34 !
   +----------+----------+----------+
   ! .  .  .  ! .  .  .  ! .  .  .  !
   ! .  .  .  ! .  .  .  ! .  .  .  !
   ! .  .  .  ! .  .  .  ! 13 .  13 !
   +----------+----------+----------+
   ! .  .  .  ! .  .  .  ! .  .  .  !
   ! .  .  .  ! .  .  12 ! .  24 14 !
   ! .  .  .  ! .  .  12 ! 13 23 .  !
   +----------+----------+----------+

The 3rd function is the same as the 2nd, but it restaures the minlex form:

Code: Select all

(pretty-print-digit-minlex-diag-sym-of-deadly-pattern 10 12) gives:
(. . . . . . . . . . . . . . . . . . . . . . . . . 12 12 . . . . . . . . . . . . . . . . . . . . . . . . 31 . 31 . . . . . . . . . . . . . . 34 . 42 32 . . . . . 34 31 41 .)
+----------+----------+----------+
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  .  ! .  12 12 !
+----------+----------+----------+
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  .  ! 31 .  31 !
+----------+----------+----------+
! .  .  .  ! .  .  .  ! .  .  .  !
! .  .  .  ! .  .  34 ! .  42 32 !
! .  .  .  ! .  .  34 ! 31 41 .  !
+----------+----------+----------+

When, in a resolution path, you see some ORk-relation being asserted, such as:

Code: Select all

DP10-4-12-OR5-relation for digits: 2679
   in cells (marked #): (r7c3 r7c2 r1c7 r1c2 r2c6 r2c3 r2c2 r3c6 r3c7 r3c3)
   with 5 guardians (in cells marked @) : n2r2c6 n2r2c3 n5r2c2 n2r3c6 n5r3c7
   +-------------------+-------------------+-------------------+
   ! 1     27#   3     ! 4     5     6     ! 27#   8     9     !
   ! 4     567#@ 269#@ ! 27    8     279#@ ! 1     3     25    !
   ! 57    8     29#   ! 1     3     279#@ ! 257#@ 6     4     !
   +-------------------+-------------------+-------------------+
   ! 2     4     1     ! 8     9     5     ! 6     7     3     !
   ! 59    3     7     ! 6     24    1     ! 49    25    8     !
   ! 6     59    8     ! 3     247   27    ! 49    25    1     !
   +-------------------+-------------------+-------------------+
   ! 3     26#   26#   ! 5     1     4     ! 8     9     7     !
   ! 8     79    4     ! 79    6     3     ! 25    1     25    !
   ! 79    1     5     ! 279   27    8     ! 3     4     6     !
   +-------------------+-------------------+-------------------+

The correspondence between this ORk-relation and the abstract DP is as follows:
- the name DP10-4-12 gives ?c = 10 and ?n = 12.
- the cells of the relation (marked #), i.e. (r7c3 r7c2 r1c7 r1c2 r2c6 r2c3 r2c2 r3c6 r3c7 r3c3), follow the same order as the cells in the abstract pattern (read from top to bottom and left to right).
- the digits in the relation "OR5-relation for digits: 2679" correspond to the abstract digits 1234 of the abstract pattern.

In the "s" case of the patterns, the right digit correspondence is obtained with function pretty-print-digit-minlex-diag-sym-of-deadly-pattern.
.

[denis_berthier]

.
I've published the Second Edition of the "User Manual and Research Notebooks for CSP-Rules" ([UMNR2]): https://www.lulu.com/shop/denis-berthier/user-manual-and-research-notebooks-for-csp-rules-second-edition/paperback/product-yv8dk82.html?page=1&pageSize=4

As usual a free pdf version is available on ResearcGate: https://www.researchgate.net/publication/388568383_User_Manual_and_Research_Notebooks_for_CSP-Rules_Second_Edition.

Code: Select all

Foreword      11
1. Introduction      15
1.1 What CSP-Rules is      15
1.2 The contents of CSP-Rules      17
1.3 Scope of this Manual       17
1.4 Motivations for the [PBCS] approach (adapted from [PBCS])      19
1.5 Simplest-first search and the rating of instances (adapted from [PBCS])      20
1.6 What can one do with CSP-Rules?      21
1.7 A quick graphical introduction to the most basic chain rules      23
1.8 General warnings      29
1.9 Selected generalities about CLIPS      30

PART ONE: GENERALITIES      33
2. Installing and launching CSP-Rules       35
2.1 Installing CSP-Rules (machine independent)      35
2.2 Launching a CSP-Rules application      37

3. The generic resolution rules and functions present in CSP-Rules       39
3.1 Basic generic resolution rules      39
3.2 Ordinary generic resolution rules      39
3.3 A word on typed-chains      41
3.4 Oddagons      42
3.5 ORk-forcing-whips, ORk-contrad-whips and ORk-whips (advanced)      42
3.6 Rules for simulating T&E (Trial and Error)      47
3.7 Rules for simulating DFS (depth-first-search)      48
3.8 Rules for finding backdoors, anti-backdoors and anti-backdoor pairs      48
3.9 Rules for simulating Forcing-T&E and Forcing{3}-T&E      49
3.10 Hooks for introducing new resolution rules      50
3.11 Generic global variables      50
3.12 Generic utility functions      51
3.13 Elementary statistical functions      56
3.14 Appendix 3A: The T&E-depth of a resolution rule      58

4. Simplest-first strategy, saliences, ratings      63
4.1 The simplest-first strategy      63
PART TWO: RUNNING SPECIFIC APPLICATIONS      67

5. General structure of the configuration files      69
5.1 The first part of the configuration file is for installation      69
5.2 The second part of the configuration file must not be changed      70
5.3 The third part of the configuration file is application specific      71
5.4 The fourth part of the configuration file defines the configuration      71
5.5 The final part of the configuration file must not be changed      83

6. SudoRules      85
6.1 Solving a puzzle given in the standard “line” (or “string”) format      86
6.2 Solving puzzles given in other formats      88
6.3 Solving collections of puzzles      92
6.4 For the readers of [HLS]      94
6.5 How different selections of rules change the resolution path      94
6.6 Goodies      101
*** The next sections of this chapter are for more advanced users ***      104
6.7 Bases for more elaborated functions and techniques      104
6.8 Solving a puzzle in stages; sets of preferences      108
6.9 Focusing on some candidates for eliminations      114
6.10 Eleven’s replacement technique      115
6.11 Global variables and utility functions for large scale studies   121
6.12 Elementary statistical functions      125
6.13 Functions for computing unbiased statistics from controlled-bias data      125

7. LatinRules      127
7.1 Latin Squares      127
7.2 Pandiagonal Latin Squares      128

8. FutoRules      135
8.1 The configuration file      135
8.2 The user functions      136
8.3 Some specific notations in the resolution path      140

9. KakuRules      141
9.1 The configuration file      142
9.2 The user functions      142
9.3 Typed-Chains in KakuRules      147

10. SlitherRules      151
10.1 The configuration file      152
10.2 The user functions      154
10.3 A lot of application-specific rules      155
10.4 An experience in assisted theorem proving      156
10.5 Isolated-HV-chains and Extended-Loops      156

11. HidatoRules (Numbrix and Hidato)      159
11.1 The configuration file      159
11.2 The user functions      159

12. MapRules      161
12.1 The configuration file      161
12.2 The user functions      161

PART THREE: ADVANCED TOPICS in SUDORULES      165
13. Requirements on the number of steps      167
13.1 Considering some rules as “no-step”      168
13.2 Finding backdoors, anti-backdoors or anti-backdoor-pairs      169
13.3 Looking for one-step solutions      171
13.4 Disabling and re-enabling rules in CSP-Rules      176
13.5 Two technical details      178
13.6 Looking for two-step solutions – 1st part (first example)      180
13.7 Looking for two-step solutions – 2nd part (second example)      182
13.8 Looking for two-step solutions – 3rd part (the method)      184
13.9 Looking for two-step solutions – 4th part (fully automated search)      187
13.10 Reducing the number of steps      189
13.11 Forcing T&E      197
13.12 Additional remarks about one- or  two- step/elim solutions      199

14. Puzzles in T&E(3) and the Tridagon family of rules      201
14.1 The trivalue oddagon and the tridagon patterns      201
14.2 The Tridagon elimination rule      203
14.3 The complexity of the impossible trivalue-oddagon pattern      208
14.4 Tridagon links      211
14.5 Tridagon-forcing-whips      212
14.6 General k-digit patterns      219
14.7 Two different views of ORk chain rules based on an exotic pattern      223
14.8 The anti-tridagon pattern and mith’s puzzles in T&E(3)      224
14.9 Tridagon-ORk-forcing-whips      226
14.10 Tridagon-ORk-contrad-whips      235
14.11 Tridagon-ORk-whips      238
14.12 Resolution power of ORk-chains      244
14.13 General remarks on ORk-chains      249
14.14 Sets of preferences for ORk-chains      250
14.15 ORk-forcing-g-whips      251
14.16 ORk-g-whips      255
14.17 Using ORk maintenance rules with large numbers of guardians      259
14.18 The part of the configuration file for ORk-chains      265
14.19 Ultra-persistency of the ORk-relations vs degeneracy   273
14.20 Updated classifications for a larger collection of T&E(3) puzzles   280
14.21 Automating eleven’s method in the context of trivalue oddagons      281
14.22 A word on T&E(3) puzzles and T&E(2) puzzles with BxB ≥ 7      286

15. Dealing with large numbers of patterns      287
15.1 Motivations      287
15.2 Eliminating useless patterns      288
15.3 Elementary tools for analysing the patterns      289
15.4 Transforming all the patterns into rules asserting ORk-relations      291
15.5 A rare example involving three impossible patterns (+ tridagon)   294
15.6 How to select the most useful patterns      299
15.7 Four levels of “usefulness” and how meaningful they are      301
15.8 A very rare example      302
15.9 A rare example with the five patterns of Imp630-Select1      306
15.10 Compared resolution power of the Select1 and Select2 sets of rules      312
15.11 Updated four levels of “usefulness” and how meaningful they are      315
15.12 The most useful patterns      316
15.13 How to use the associated ORk-chain rules in SudoRules      327
15.14 Using CSP-Rules as a research tool      329
15.15 Exceptional cases of non-confluence in ORk-whips      331

16. Miscellanea      339
16.1 Deadly patterns and ORk-chains in Sudoku      339
16.2 Sudoku templates as patterns   365
16.3 CSP-Rules companion repositories on GitHub (1): examples      372
16.4 SudoRules companion repositories on GitHub (2): large scale studies      374
16.5 Questions and answers   375
16.6 Reporting bugs and improving CSP-Rules      377
16.7 CSP-Rules-V2.1 main updates      377

References      387
Books and articles      387
Websites      389
Software and companion repositories      389
Sudoku puzzle collections (pre-tridagon)      390
Sudoku puzzle collections (post-tridagon)      390

Anticipating questions about what's new wrt to the previous edition:
– “addition” of generic global variables (section 3.11) and utility functions (section 3.12);
– “addition” of elementary generic statistical functions (section 3.13);
– “addition” of sudoku-specific statistical functions (section 6.12) and of functions for computing unbiased distributions from controlled-bias collections (section 6.13);
– extended revision of chapter 14; the First Edition reported the progressive development of the topic; in this second Edition, the path of development has been deliberately kept visible, in particular its main two concurrent lines: modification of the default saliences for Tridagons and ORk-chain rules, and introduction of ORk-ultra-persistency and ORk-splitting rules; but most of the T&E(3) examples have been updated to reflect the new settings instead of the old ones, resulting as expected is shorter resolution paths; some examples have even been changed;
– in chapter 14, update of all the classification results for T&E(3) collections;
– addition of remarks on T&E(3) and T&E(2) puzzles with BxB ≥ 7 (section 14.22);
– addition of Sudoku-specific deadly patterns (section 16.1); they depend on the assumption of uniqueness and they are not very useful patterns in general, but here they are, mainly to demonstrate another use of ORk-chains and another case of a large set of patterns;
– addition of Sudoku-specific templates (section 16.2) (and addition to [SUDCL] of some detailed results of their study); they are neither friendly nor very useful in practice, but here they are;
– addition to SudoRules of links to [SUDCL], the new GitHub repository for large Sudoku collections (other than [CBGC]), containing the details of all the results either already published in [HCCS2] or forthcoming; the links appear in the form of global variables making it easier to refer to the collections when the repositories are installed at the right place in the CSP-Rules root directory (section 16.4); the function calls appearing in many “RESULTS.clp” files of [SUDCL] rely on these global variables and can be used to reproduce the results by merely pasting them into SudoRules (with the relevant sets of rules loaded).

(Additions in double quotes consist partly in documenting previously existing but as yet undocmented functions.)

.