## Hierarchical Classifications in Constraint Satisfaction

### Hierarchical Classifications in Constraint Satisfaction

.
My new booklet Hierarchical Classifications in Constraint Satisfaction or [HCCS] is available on lulu.com https://www.lulu.com/shop/denis-berthier/hierarchical-classifications-in-constraint-satisfaction/paperback/product-654rp6d.html?q=denis+berthier&page=1&pageSize=4

It builds on my previous publications and it serves as a theoretical background for the Sudoku Hierarchical Classifier (SHC) developed by François Cordoliani:
(http://forum.enjoysudoku.com/the-sudoku-hierarchical-classifier-shc-t42075.html
https://github.com/denis-berthier/Sudoku_Hierarchical_Classifier).
It explains how to use the universal classifications in the search for the "hardest" puzzles.

Code: Select all
1. Universal hierarchical classifications      7
1.1 Introduction and the emblematic 9×9 Sudoku example      7
1.2 Pure logic classifications based on the hardest step      8
1.3 Universal classifications for Constraint Satisfaction Problems      9
1.4 Trial-and-Error: T&E      9
1.5 T&E(n) (iterated Trial-and-Error) and T&E-depth      11
1.6 Braids[p] and T&E(Bp, n)      13
2. Hierarchical classifications in 9×9 Sudoku      15
2.1 Illustrating the hierarchical classifications in 9×9 Sudoku      15
2.2 CSP-Rules and SudoRules      16
2.3 Known classification results in Sudoku      17
2.4 The quest for the “hardest” puzzles      20
3. The Sudoku Hierarchical Classifier      25
3.1 The Sudoku Hierarchical Classifier (SHC)      25
3.2 Comparison of SudoRules and SHC results      26
3.3 How to use the SHC in the search of the hardest puzzles      27
3.4 Checking the contents of your SHC directory      28
3.5 Typical examples of running the SHC      28
3.6 The SHC command line      29
4. Analysis of the hierachical classifications      33
4.1 The standard SHC examples      34
4.2 Analysis of B computations      34
4.3 Analysis of BpB computations and comparison with SER      35
4.4 Analysis of BpBB computations      37
4.5 Analysis of T&E-depth computations      38
5. References      39
5.1 Books      39
5.2 Software      39
5.3 Puzzle collections and their classifications      40

As for the search of the hardest puzzles, the idea of replacing the SER by T&E-depth has already led to hundreds of thousands of new puzzles in T&E(3), "many" of which happen to have high SER.
My idea is, replacing the SER by BpB could lead to "many" new puzzles in T&E(2), "many" of which might have high SER. The existence of the SHC makes the idea realistic.

Maximising BpB within T&E(2) and maximising T&E-depth are independent goals, both with an intrinsic, structural meaning.

As for all my publications, a free pdf version is available on ResearchGate:
https://www.researchgate.net/publication/374508822_Hierarchical_Classifications_in_Constraint_Satisfaction

.
denis_berthier
2010 Supporter

Posts: 4045
Joined: 19 June 2007
Location: Paris

### Re: Hierarchical Classifications in Constraint Satisfaction

.
The second edition of my book "Hierarchical Classifications in Constraint Satisfaction" has been published on Lulu.com:
https://www.lulu.com/shop/denis-berthier/hierarchical-classifications-in-constraint-satisfaction-second-edition/paperback/product-kv9j629.html?page=1&pageSize=4
After some time, it will also be available on all the main bookstores.

It's a completely revised version of the first edition (4x more pages). The 1st edition (which should be edition 0.25) answered an immediate need for the search of high BxB puzzles. This 2nd edition is back to its original broader track.
It includes extensions to the old statistical analyses in [PBCS].
The appendix gives detailed instructions on how to reproduce all the results and to go further, using the 3 software tools used in the book

Code: Select all

Foreword      7

1. Universal hierarchical classifications      9
1.1 Introduction and the emblematic 9×9 Sudoku example      9
1.2 Pure logic classifications based on the hardest step      10
1.3 Universal classifications for Constraint Satisfaction Problems      11
1.4 Trial-and-Error: T&E      12
1.5 T&E(n) (iterated Trial-and-Error) and T&E-depth      14
1.6 Braids[p] and T&E(Bp, n)      16

2. Hierarchical classifications in 9×9 Sudoku      19
2.1 The statistics of T&E-depth in 9×9 Sudoku      19
2.2 The unbiased B classification within T&E(0 or 1)      19
2.3 The BxB classification within T&E(2)      28
2.4 Hardest puzzles in the hierarchical classifications      32
2.5 The quest for the “hardest” puzzles      34

3. To correlate or not to correlate      37
3.1 Basic definitions      37
3.2 Elementary correlations in  Sudoku      40
3.3 Correlations (or lack thereof) with “difficulty”      47
3.4 Conclusions      48

4. Vicinity search and universal CSP topologies      49
4.1 The Hamming distance      50
4.2 Classical and extended vicinity search in Sudoku      55
4.3 Different ways of expanding puzzles      57
4.4 Two natural stratifications of the set of puzzles      60
4.5 Universal CSP topologies      61

5. The rise of the tridagon      67
5.1 The impossible trivalue oddagon pattern       67
5.2 The tridagon pattern      74
5.3 The degenerate-cyclic tridagon pattern      76
5.4 Ubiquity of the degenerate-cyclic tridagon pattern      83
5.5 How the tridagon discovery totally changed the T&E(2) landscape      90
5.6 Persistency of the tridagon in expansions of minimal T&E(3) puzzles      98
5.7 Conclusions      100

6.  Across and along the T&E(n) borders      103
6.1 Expansions of T&E(3) puzzles beyond the border of T&E(3)      103
6.2 BRT+1-expansions of T&E(2) minimal puzzles and their minimals      109
6.3 BRT(+1)-expansions of T&E(1) puzzles and their minimals      115

7. Appendix: software tools      121
7.1 CSP-Rules and SudoRules      121
7.2 SHC: the Sudoku Hierarchical Classifier      133
7.3 gsf’s solver and generator      147

8. References      151
8.1 Books and articles      151
8.2 Software      152
8.3 Sudoku puzzle collections (pre-tridagon)      153
8.4 Sudoku puzzle collections (post-tridagon)      153
8.5 Classifications of Sudoku puzzle collections      154

: I didn't have time yesterday, but that's now done. As usual, a free pdf copy is available on ResearchGate:
https://www.researchgate.net/publication/381884473_Hierarchical_Classifications_in_Constraint_Satisfaction_Second_Edition
.
denis_berthier
2010 Supporter

Posts: 4045
Joined: 19 June 2007
Location: Paris

### Re: Hierarchical Classifications in Constraint Satisfaction

.
Correlations
In Sudoku, one could say nothing correlates with anything, but...
I've found an unexpectedly strong correlation between the number of clues and the number of candidates, not at the start, but after applying the Basic Resolution Theory (BRT), i.e. "after Singles".

This result is valid for each collection among the following 8 large ones, covering all the spectrum of difficulty and of number of clues:
- the ~6M controlled-bias-collection,
- eleven T&E(2) "tamagochi" collection,
- ph2010,
- mith T&E(3) collection,
- and 4 collections, each with a fixed number of clues: 17, 18, 38, 39.

Detailed results make the content of chapter 2.

Note that the very strong correlation is valid within each collection, not if they are amalgamated (which would anyway be a statistical nonsense).
.
denis_berthier
2010 Supporter

Posts: 4045
Joined: 19 June 2007
Location: Paris

### Re: Hierarchical Classifications in Constraint Satisfaction

Sudoku topologies
This is related to the question raised here: http://forum.enjoysudoku.com/sudoku-space-t5347.html
but with a different starting point.

Let P (resp. M) be the set of one-solution* sudokus (resp. of minimal sudokus).
Define an expansion of a puzzle P as any puzzle with the same clues as P plus possibly some more clues (necessarily taken from its solution).
Define in particular the BRT-expansion of P as the expansion obtained by applying all the rules in the universal Basic Resolution Theory (BRT), i.e. Singles plus direct contradictions with decided values - also called expansion by Singles (an idea first introduced by mith, AFAIK).

Now, on P or M, one can define an equivalence relation between P1 and P2 by BRT-expand(P1) = BRT-expand(P2).
This relation is obviously compatible with isomorphisms of P or M.

Now, based on this equivalence relation, one can define a topology on P or M, in a straightforward way:
define the basic open neighbourhood of a puzzle P (in P, resp. M) as the set of all the puzzles (in P, resp. M) that have the same BRT-expansion as P.

It is easy to check that this defines a (non-metric) topology (the BRT topology) and that:
- every basic open neighbourhood is both open and closed ,
- a puzzle is isolated iff it is its own BRT-expand,
- puzzles with different solution grids are isolated from each other,
- the hierarchical classifications (T&E-depth, B, BxB, BxBB) are continuous functions for this topology.

In [HCCS2] (http://forum.enjoysudoku.com/hierarchical-classifications-in-constraint-satisfaction-t42076.html, https://www.researchgate.net/publication/381884473_Hierarchical_Classifications_in_Constraint_Satisfaction_Second_Edition),
I've introduced more topologies of the same kind, but the BRT-topolgy is the finest one.

(*) All this can be extended to multi-sol puzzles. Expansions are restricted to add clues common to all the solutions.
denis_berthier
2010 Supporter

Posts: 4045
Joined: 19 June 2007
Location: Paris