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

[denis_berthier]

.
In [HCCS2], I announced that I'd publish "soon" all the data I computed in order to build the numerous tables in the book. Thats' now done (not as soon as I wanted, because I did some cleaning, but finally done). I've created a new GitHub repository with all the collections analysed in the book, all the results and (almost) all the commands necessary to reproduce the results.
Each directory corresponds to one of the collections and contains all the calculations for it.
The presentation is uniform: same file names for all the collections, same basic statistical analyses, same "RESULTS.clp" for each collection.
I've also added to SudoRules global variables for the names of each collection, so that you can easily reproduce all the calculations.
See the README.md file in https://github.com/denis-berthier/Sudoku-classif for all the details.

Note 1: if I analyse more collections along similar lines, this is where the detailed results will now be published.
Note 2: if you have limited disk space, the whole repository requires 1.3 GB.
Note 3: the previous two repositories (https://github.com/denis-berthier/Classifications-of-TE3-Sudokus and https://github.com/denis-berthier/Classification-of-TE2-Sudokus) have been rejuvenated and have become parts of the new one; the old versions will soon be archived.

[Edit]: OOPS, I had forgotten to make the new repository public. It's now done.
.

[denis_berthier]

.
Erratum:
in HCCS2, section 4.3.2, there's a typo. You should read:
let us define a 1+BRT-expand(P) as any puzzle that is the BRT-expand of a 1-expand of P.
.

[denis_berthier]

.
In [HCCS2] and in a previous post, I defined the set P and its subset M, and I defined the BRT-topology on them.
Continuity wrt this typology means invariance under BRT-equivalence.
All the universal classifications in [HCCS] are continuous wrt the BRT topology.

However, there's another fundamental property expected of any rational classifcation system: monotonicity wrt to puzzle expansion. I'll show that it can also be expressed as a continuity property.
This will be one more occasion to show that BRT-equivalence and (1+BRT)-expansion must be taken seriously.


1) The sets PE and ME
Define
PE as the set of BRT-equivalence classes of consistent puzzles
ME as the set of BRT-equivalence classes of minimal puzzles

By choosing the BRT-expand common to all the puzzles in a class, one can also say that:
PE is the set of self-expand puzzles
ME is the set of min-expand puzzles


1) The BRT-inc topology on the PE and ME sets
For puzzles in PE or ME, define the partial order relation by
P < Q is P is a strict sub-puzzle of Q.
This turns PE and ME into posets (partially ordered sets).

Definition:
The BRTinc topology on PE (ME) is the topology associated to their poset structure.

(This is a classical concept in maths.)
(as before "BRT" stands for the universal "Basic Resolution Theory", "inc" stands for "inclusion", "BRTinc" stands for "inclusionn modulo BRT-equivalence"

To make it short, a basis of open sets is defined by all the P- for P in PE (resp. ME):
P- = the set of self-expand [resp. min-expand] puzzles Q with Q ≤ P.



2) Fundamental result:
Theorem: continuity wrt the BRTinc topology means monotonicity (decreasing, with this choice of the basic open sets)
Proof : this is classical for the topology associated to a poset.

All the universal classifications in [HCCS] are continuous wrt the BRTinc topology.



3) Intricacies of the poset structure and the BRTinc topology
It is quite obvious that one can have long strictly descending chains in PE (see any of the expansion path in the 1+BRT-expand thread).
But it is far from obvious in ME. The reason is, one needs to find minimal puzzles of which the puzzles in the chain are BRT-expands. One already knows chains of length 1 in the T&E(3) databse, but longer lengths are not obvious.
Note that a descending chain is also a sequence of striclty decreasing non-empty open sets.

I launched a chalenge here: http://forum.enjoysudoku.com/1-brt-expansion-paths-within-t-e-n-and-beyond-t45647-85.html
In the terms of this post, the challenge can be summarised as
find a sequence of strictly decreasing non-empty open sets (with some stricter conditions)
and the answer to it is, one can indeed find quite long chains.

This shows that the BRTinc toplogy is much more subtle than one might think and that the study of (1+BRT)-expansions has still a lot to deliver.


[Edit]: note Notice that it would also make sense on P or M to define a strict partial order relation between two puzzles P and Q by: P < Q if and only if BRT-expand(P) is a strict sub-puzzle of BRT-expand(Q). But beware that this definition of P < Q wouldn’t make any difference between puzzles with identical BRT-expands and that, in the associated non-strict order, P ≤ Q wouldn’t mean that P is a sub-puzzle of Q; indeed, Q could well be a strict sub-puzzle of P, as long as they have the same BRT-expand. I shall therefore avoid to write this order relation on P or M. This is a clear example of the necessity of taking BRT-equivalence seriously.

.

[denis_berthier]

.
One more point of interest wrt to the above-defined topology is about its isolated points.
Theorem: a puzzle is isolated in the BRTinc topology on PE or ME iff it is a min-expand (a member of ME) and it is the common BRT-expand of all its minimal puzzles.
The proof is quite easy, knowing that the isolated puzzles in the topology associated to a poset as above are its minimal elements (in the sense of the order).

This is interesting, because it gives a topological meaning to a class of puzzles encountered by mith in his search of T&E(3) puzzles.

[Edit]: one more interesting point about isolated puzzles in T&E(3).
In the whole collection of 4,634,101 known T&E(3) minimals, there are 667,767 min-expands and 449,209 (i.e. 67.27 %) non isolated min-expands.
.

[denis_berthier]

.

The third edition of my book "Hierarchical Classifications in Constraint Satisfaction" has been published:
https://www.lulu.com/shop/denis-berthier/hierarchical-classifications-in-constraint-satisfaction-third-edition/paperback/product-4587d42.html
After a few weeks, it should also be available from the main book sellers.

Code: Select all

Table of contents

Foreword      7

PART ONE: General definitions and results      11

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

2. Hierarchical classifications in 9×9 Sudoku      23
2.1 The statistics of T&E-depth in 9×9 Sudoku      23
2.2 The unbiased B classification within T&E(0 or 1)      23
2.3 The BxB classification within T&E(2)      32
2.4 Hardest puzzles in the hierarchical classifications      36

3. To correlate or not to correlate      41
3.1 Basic definitions      41
3.2 Elementary correlations in  Sudoku      44
3.3 Correlations (or lack thereof) with “difficulty”      51
3.4 Conclusions      52

4. Vicinity search and universal CSP topologies      53
4.1 Hamming distance versus topology      54
4.2 Classical and extended vicinity search in Sudoku      59
4.3 Different ways of expanding puzzles      61
4.4 Two natural stratifications of the set of puzzles      64
4.5 The universal BRT topology      65
4.6 The universal BRTinc topology      68
4.7 Final remarks      72
4.8 More topologies      72

5. The rise of the tridagon      77
5.1 The impossible trivalue oddagon pattern       77
5.2 The tridagon pattern      84
5.3 The degenerate-cyclic tridagon pattern      86
5.4 Ubiquity of the degenerate-cyclic tridagon pattern      94
5.5 How the tridagon discovery totally changed the T&E(2) landscape      101
5.6 Persistency of the tridagon in expansions of minimal T&E(3) puzzles      108
5.7 Conclusions      111

PART TWO: Expansion paths within T&E(n) and across the borders      113

6. Expansion paths within T&E(3)      115
6.1 Expansion phases      116
6.2 Expansion paths within T&E(3)      124
6.3 Terminal puzzles and T&E(3)-expands      128
6.4 Expansion paths to the T&E(3) inner border      129

7. Expansion of minimals within T&E(2)      133
7.1 Expansions of minimals within T&E(2)      133
7.2 Expansion paths within T&E(2)      139
7.3 Terminal puzzles and T&E(2)-expands      141
7.4 Expansion paths to the T&E(2) inner border      142

8. Expansion of minimals within T&E(1)      145
8.1 Expansions of minimals within T&E(1)      145
8.2 Expansion paths within T&E(1)      150
8.3 Terminal puzzles and T&E(1)-expands      156
8.4 Expansion paths to the T&E(1) inner border      157
8.5 Comparisons of expansions within T&E(3), T&E(2) and T&E(1)      158

9.  Across the T&E(n) borders      161
9.1 Expansions of T&E(3) puzzles beyond the T&E(3) border      162
9.2 Expansions of T&E(2) puzzles beyond the T&E(2) border      168
9.3 A systematic T&E(3)-minimal-to-high-B procedure      169
9.4 A systematic T&E(2)-minimal-to-high-B procedure      172
9.5 A putative systematic T&E(3)-minimal-to-insol-high-BxB procedure      175
9.6 A putative systematic T&E(3)-minimal-to-outsol-high-BxB procedure      179

10. Software tools      183
10.1 CSP-Rules and SudoRules (general)      183
10.2 SHC: the Sudoku Hierarchical Classifier      195
10.3 gsf’s solver and generator      211
10.4 The SudoRules Expansion kit   214

11. References      233
11.1 Books and articles      233
11.2 Software      234
11.3 Sudoku puzzle collections (pre-tridagon)      235
11.4 Sudoku puzzle collections (post-tridagon)      235
11.5 Classifications of Sudoku puzzle collections      236


.

[denis_berthier]

.
Anticipating on the usual question ("what's new..."), here's an extract of the Foreword:

The main change in this Third Edition is the drastically increased role granted to BRT-equivalence, to (1+BRT)-expansion and to associated universal concepts. As a result and for the first time (as far as we know), a systematic exploration of non-minimal puzzles becomes possible. It is split into two parts: exploration of the insides of each of the T&E(n) territories and analysis of the modes of reaching or crossing their borders. Thus, chapters 6 to 8 are completely new; they are based on the successive phases of (1+BRT)-expansion of puzzles within T&E(n). The “border crossing” or “out of T&E(n)” part is now in chapter 9 (ex chapter 6, completely re-written, except section 9.1). Chapter 9 also analyses how easily high B puzzles in T&E(1) can be obtained by expansion of T&E(3 or 2) minimals but high BxB ones in T&E(2) cannot.

Topological considerations have been extended as a theoretical background for the above mentioned concepts. Section 4.4 about the universal BRT topology has been slightly expanded, with lemma 4.1 being added before Theorem 4.3 (now 4.4) about isolated puzzles.
Section 4.5 is new; it introduces the universal BRTinc topology (a classical “dual Alexandrov” topology) on the set of BRT-equivalence classes of puzzles [resp. of minimals] – equivalently on the set of self-expand [resp. of min-expand] puzzles. It is based on the poset structure defined by the idea of “expansion of a puzzle modulo BRT-equivalence”. On a practical side, any isolated puzzle P in this topology has a very interesting “closure” property: all its minimals have the same BRT-expand, namely P itself; by any rational measure of difficulty, minimization of an isolated puzzle cannot produce harder puzzles. This is a clear indication that any useful notion of an isolated puzzle comes with the BRTinc instead of the BRT topology. The BRTinc topology now appears as the right one for taking BRT-equivalence even more seriously.
We had already argued in the Second Edition that universality, invariance under CSP-isomorphims, invariance under BRT-equivalence and monotonicity are a priori fundamental properties for any rational classification system. We can now say that the first two are (trivially) satisfied by both topologies and that:
– the BRT topology allowed to consider the invariance of our main classifications with respect to BRT-equivalence as a topological property;
– the BRTinc topology now allows to consider the monotonic (decreasing) behaviour of these classifications with respect to the expansion of puzzles (modulo BRT-equivalence) also as a topological property. It will also appear as essential in practice for allowing a deep understanding of the expansion techniques discussed in chapter 6 and after.
Technically, none of the above topological considerations is a big deal; but they give the feeling that, at the most elementary levels, pieces fit together – in particular that BRT-equivalence and (1+BRT)-expansion are essential tools in any systematic analysis.

On the practical side, one point that now appears to be essential in our approach (and apparently new in the Sudoku world) is the systematic splitting of puzzle collections into the sub-collections associated to different solution grids. This allows a much simpler approach to expansion.

Section 10.4 “The SudoRules EXPANSION toolkit” is new and the corresponding software has been (or will soon be) added to the CSP-Rules repository on GitHub. The normal place of section 10.4 might be in the SudoRules part of the CSP-Rules User Manual, but having it here is intended to show the strict relation between our general approach and its software implementation.