The New Sudoku Players' Forum

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