The New Sudoku Players' Forum

[denis_berthier]

.
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

Table of contents
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]

.
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

Table of contents

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


[Edit]: 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]

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

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]

.
Because the hierarchical classifications are monotonic and invariant under BRT-expansions, they allow to ask new questions, involving non-minimal puzzles.
(From a player's POV, there's strictly no reason to consider only minimal puzzles.)

1) Starting from a minimal puzzle in T&E(n), how many expansion steps* can one do in the mean before reaching T&E(n-1);
2) Starting from a minimal puzzle in T&E(n), how many expansion steps* can one do in the mean before reaching T&E(n-2) ....;
3) Starting from a minimal puzzle in T&E(n), what is the maximum number of expansion steps* before reaching T&E(n-1);
4) Within each T&E(n), same questions for the secondary classification (B, BxB...).

(*) Here, an expansion step can be defined in two different ways, which doubles the number of the above questions:
a) add a clue from the solution,
b) starting from BRT-expansions of minimals, add a clue from the solution and apply BRT expansion.

Section 5.6 and chapter 6 deal with similar questions, but many of the above questions remain open. To me, they now seem more interesting than the quest for more "hard" puzzles.
.

[denis_berthier]

.
In [HCCS2], I've studied the correlation coefficient after BRT (i.e. "after Singles") between the numbers of clues and of candidates for various large collections of puzzles and I've shown that it is very high. (It's the only meaningful correlation ever found in Sudoku.)

A recent compilation by coloin of 3362 T&E(2) puzzles in BxB, x>7, found by Hendrik Monhard, Paquita and coloin in the past months (http://forum.enjoysudoku.com/post348093.html#p348089) allows to extend the above results (in particular those of section 5.5.4.2).
It also extends the result that, for puzzles with a tridagon, the correlation at the start is also very high (contrary to collections with no tridagon).

correlation-coefficient(nb-clues, nb-cands) = -0.92
correlation-coefficient(nb-clues-after-BRT, nb-cands-after-BRT) = -0.94
(For obvious reasons, the coefficients are negative.)
.

[denis_berthier]

.
Following the speed improvements brought by François to the SHC 6.1 release, some of the Tables of section 7.2.4 in [HCCS2] need to be updated.
The computation times for T&E-depth and BxBB are not significantly changed.
Here's the updated Table 7.2 for the BxB classification, currently the most used one in the search for the hardest puzzles in T&E(2).
The puzzle collection for the BxB standard examples has been extended by adding 10 puzzles for each of the B8B, B9B, B10B, B13B values and 3 puzzles for B14B (the only 3 known ones). The puzzles are the first ones in the corresponding BxB sub-list of 3362 minimals published by Coloin here: http://forum.enjoysudoku.com/the-bxb-classification-of-t-e-2-puzzles-t41922-105.html

Code: Select all

BxB            2       3       4       5       6       7       8       9       10      11      12      13      14
mean time (s)  0.35    0.90    2.10    3.60    4.75    6.1     7.7     30.4    15.8    N/A     N/A     10.0    9.33

Note that no puzzles with BxB = 11 or 12 is known.
Note the "anomaly" for B9B; note that this "anomaly" also appears in the buffer sizes (see the BxB messages in the examples folder). Larger buffers means more partial chains used, which implies longer time.

Note that the main speed improvements are for large values of BxB and don't appear here if you compare with the original Table 6.2 in [HCCS2], as its BxB values were restricted to 7. But you can use the same set of BxB examples and run it with previous versions of the SHC and you will see they are drastic.
.