Sudoku Programming with C (eBook)

Giulio Zambon (Autor)

eBook Download: PDF

2015 | 1st ed.
XIV, 300 Seiten
Apress (Verlag)
978-1-4842-0995-0 (ISBN)

Infos

Sudoku Programming with C teaches you how to write computer programs to solve and generate Sudoku puzzles. This is a practical book that will provide you with everything you need to write your own books of Sudoku Classic and Samurai puzzles. But be warned: after reading it, you'll discover that the puzzles in your local paper are not so challenging after all!

We like Sudokus because they test our capacity to recognize and interpret patterns. But how are the clues generated? Where do those quasi-symmetrical configurations come from? When the author explored the Web to find out, he discovered that there were many sites that explained how to solve Sudokus, but none that told him how create them. He also saw many sites and apps to play Sudoku, but, perhaps not surprising, no indication of how they worked.

So, he had to develop his own applications in order to find out. And, from the very start, he decided that he would publish the code for anyone else to use and perhaps tinker with, but the author wrote it in such a way that also lets readers with limited knowledge of programming techniques understand it. In fact, you could decide to start generating thousands of puzzles almost immediately, and go through the explanations of algorithms and techniques later, a bit at a time. The author chose to write the application in ‘plain old C’ because he wanted to make the code accessible to as many people as possible.

In this book, you will find an explanation of all solving strategies, and the code to implement them. Writing the Solver application was more difficult than writing the Generator, because it required designing and implementing each strategy separately. However, the author wanted to include a solving program capable of listing the strategies necessary to solve any particular puzzle. He also wanted to check whether a puzzle was solvable analytically, without any guessing.

This book includes the full listings of both the Generator and the Solver, and explanations of all C modules, with walk-throughs and examples.

Giulio Zambon s first love was physics, but he decided to dedicate himself to software development more than 30 years ago: back when computers were still made of transistors and core memories, programs were punched on cards, and Fortran only had arithmetic IFs. Over the years, he learned a dozen computer languages and worked with all sorts of operating systems. His specific interests were in telecom and real-time systems, and he managed several projects to their successful completion. In 2001 Giulio founded his own company offering computer telephony integration (CTI) services, and he used JSP and Tomcat exclusively to develop the web side of the service platform. Back in Australia after many years in Europe, he now dedicates himself to writing software to generate and solve numeric puzzles. His web site, http://zambon.com.au/, is written in JSP on his dedicated server, which, unsurprisingly, runs Tomcat!

Inhalt

Contents at a Glance 3
Contents 279
About the Author 285
Introduction 5
Chapter 1: Modeling a Sudoku Puzzle in C 7
Solving a Puzzle 7
Generating a Puzzle 8
Modeling the Puzzle 8
Summary 14
Chapter 2: The Strategies 15
Level 0 Strategies 15
The Strategy Naked Single 15
The Strategy Unique 15
The Strategy Cleanup 15
Usage of Level 0 Strategies 16
Level 1 Strategies 17
The Strategy Naked Pair 17
The Strategy Hidden Pair 18
The Strategy Box-Line 18
The Strategy Pointing Line 18
Level 2 Strategies 19
The Strategies Naked Triple and Naked Quad 19
The Strategy Hidden Triple 19
The Strategy Lines-2 20
The Strategy Y-wing 21
Level 3 Strategies 22
The Strategy X Y-Chain 22
The Strategy Rectangle 25
The Strategies Lines-3 and Lines-4 29
Level 4 Strategies 31
What about Coloring ? 31
Strategy Selection 31
Summary 31
Chapter 3: The Solver Program 32
init(?) 41
cleanup(?) 43
solve(?) 46
Counting 48
Checking Consistency 50
Input/Output 52
Summary 55
Chapter 4: Implementing “Unique” 56
unique_unit(?) 56
unique(?) 59
unique_loop(?) 60
Summary 60
Chapter 5: Implementing “Naked” Strategies 61
naked_pair_unit(?) 64
naked_triple_unit(?) 69
naked_quad_unit(?) 73
Summary 76
Chapter 6: Implementing “Hidden” Strategies 77
hidden_pair_unit(?) 78
hidden_triple_unit(?) 83
Summary 86
Chapter 7: Implementing “Box-Line” 87
box_line(?) 87
box_line_unit(?) 88
Summary 91
Chapter 8: Implementing “Pointing Line” 92
pointing_line(?) 92
pointing_line_box(?) 93
Summary 96
Chapter 9: Implementing “Lines” Strategies 97
lines_2(?) 97
lines_3(?) 98
lines_4(?) 99
lines(?) 100
An Example 103
Summary 105
Chapter 10: Implementing “Y-wing” 106
pairs_find(?) 107
y_wing_digit(?) 111
intersection(?) 115
footprint(?) 117
An Example 118
Summary 120
Chapter 11: Implementing “XY-chain” 121
xy_chain_digit(?) 122
xy_chain_step() 124
An Example 128
Summary 131
Chapter 12: Implementing “Rectangle” 132
rectangle() 132
rectangle_pattern() 133
rectangle_cell() 136
rectangle_step() 137
Case A: n == 0 and kBeq < 3
Case B: n > 0 and kBeq <
Case C: n == 0 and kBeq == 3 141
Case D: n > 0 and kBeq == 3
An Example 142
rectangle_step(): for 6, kBeq 0, chain: (1,5) 142
rectangle_step(): for 6, kBeq 1, chain (1,5) (0,6) 143
rectangle_step(): for 6, kBeq 2, chain (1,5) (0,6) (7,7) 143
rectangle_step(): for 6, kBeq 3, chain (1,5) (0,6) (7,7) (6,5) 143
rectangle_step(): for 6, kBeq 1, chain (1,5) (0,7) 144
rectangle_step(): for 6, kBeq 2, chain (1,5) (0,7) (6,6) 145
rectangle_step(): for 6, kBeq 3, chain (1,5) (0,7) (6,6) (7,4) 145
rectangle_step(): for 9 146
Pointing-line within rectangle 146
Summary 147
Chapter 13: Implementing “Backtrack” 148
display_strats_in_clear(?) 153
Optimization 153
An Example 156
Summary 162
Chapter 14: Solving Thousands of Puzzles 163
The Example of Minimum Sudokus 165
Summary 167
Chapter 15: Generating Sudokus 168
Generating a Solved Sudoku 168
init() for the Generator 172
fill() 173
fill_digit() 175
Removing Clues to Make a Puzzle 180
brute_comp() 191
inconsistent_unit() for the Generator 196
Check for Uniqueness of the Solution 197
Completing the Generator 199
Utilities for the Generator 201
Summary 207
Chapter 16: Puzzle Statistics and More Puzzles 208
Statistic on Number of Clues 208
Statistic on Numbers 211
Statistic on Solutions 212
Timing 215
Generating More Puzzles 217
Number Shifting 217
Rotating, Flipping, and Mirroring 219
Swapping Lines and Triplets of Lines 221
Removing Different Numbers of Clues 222
Summary 223
Chapter 17: Special Sudokus 224
Designer Sudokus 224
Symbolic Sudokus 229
Summary 232
Chapter 18: Multi-Grid Sudokus 233
There Are Many Different Multi-Grid Sudokus 234
How You Join the Grids 236
How the Generator Does It 238
Displaying a Multi-Grid Sudoku 247
Designer Multi-Grid Sudokus 254
Summary 262
Chapter 19:Development Environment 263
Eclipse 263
Setting Up Eclipse on a PC 263
Coding Style 266
Setting Up the Solver and the Generator 268
Chapter 20:Abbreviations and Acronyms 272
Index 273

Produkt-Details

• Erscheint lt. Verlag: 25.3.2015
• Zusatzinfo: XIV, 300 p. 90 illus.
• Verlagsort: Berkeley
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Informatik ► Software Entwicklung ► Spieleprogrammierung
• ISBN-10: 1-4842-0995-8 / 1484209958
• ISBN-13: 978-1-4842-0995-0 / 9781484209950