Hierarchical Classifications in Constraint Satisfaction (Second Edition)

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,