Zambon Sudoku Programming with C

1. ed
ISBN: 978-1-4842-0995-0
Verlag: Apress
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 285 Seiten

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!

Autoren/Hrsg.

Zambon, Giulio

Inhaltsverzeichnis

1;Contents at a Glance;3
2;Contents;279
3;About the Author;285
4;Introduction;5
5;Chapter 1: Modeling a Sudoku Puzzle in C;7
5.1;Solving a Puzzle;7
5.2;Generating a Puzzle;8
5.3;Modeling the Puzzle;8
5.4;Summary;14
6;Chapter 2: The Strategies;15
6.1;Level 0 Strategies;15
6.1.1;The Strategy Naked Single;15
6.1.2;The Strategy Unique;15
6.1.3;The Strategy Cleanup;15
6.1.4;Usage of Level 0 Strategies;16
6.2;Level 1 Strategies;17
6.2.1;The Strategy Naked Pair;17
6.2.2;The Strategy Hidden Pair;18
6.2.3;The Strategy Box-Line;18
6.2.4;The Strategy Pointing Line;18
6.3;Level 2 Strategies;19
6.3.1;The Strategies Naked Triple and Naked Quad;19
6.3.2;The Strategy Hidden Triple;19
6.3.3;The Strategy Lines-2;20
6.3.4;The Strategy Y-wing;21
6.4;Level 3 Strategies;22
6.4.1;The Strategy X Y-Chain;22
6.4.2;The Strategy Rectangle;25
6.4.3;The Strategies Lines-3 and Lines-4;29
6.5;Level 4 Strategies;31
6.5.1;What about Coloring ?;31
6.6;Strategy Selection;31
6.7;Summary;31
7;Chapter 3: The Solver Program;32
7.1;init(?);41
7.2;cleanup(?);43
7.3;solve(?);46
7.4;Counting;48
7.5;Checking Consistency;50
7.6;Input/Output;52
7.7;Summary;55
8;Chapter 4: Implementing “Unique”;56
8.1;unique_unit(?);56
8.2;unique(?);59
8.3;unique_loop(?);60
8.4;Summary;60
9;Chapter 5: Implementing “Naked” Strategies;61
9.1;naked_pair_unit(?);64
9.2;naked_triple_unit(?);69
9.3;naked_quad_unit(?);73
9.4;Summary;76
10;Chapter 6: Implementing “Hidden” Strategies;77
10.1;hidden_pair_unit(?);78
10.2;hidden_triple_unit(?);83
10.3;Summary;86
11;Chapter 7: Implementing “Box-Line”;87
11.1;box_line(?);87
11.2;box_line_unit(?);88
11.3;Summary;91
12;Chapter 8: Implementing “Pointing Line”;92
12.1;pointing_line(?);92
12.2;pointing_line_box(?);93
12.3;Summary;96
13;Chapter 9: Implementing “Lines” Strategies;97
13.1;lines_2(?);97
13.2;lines_3(?);98
13.3;lines_4(?);99
13.4;lines(?);100
13.5;An Example;103
13.6;Summary;105
14;Chapter 10: Implementing “Y-wing”;106
14.1;pairs_find(?);107
14.2;y_wing_digit(?);111
14.3;intersection(?);115
14.4;footprint(?);117
14.5;An Example;118
14.6;Summary;120
15;Chapter 11: Implementing “XY-chain”;121
15.1;xy_chain_digit(?);122
15.2;xy_chain_step();124
15.3;An Example;128
15.4;Summary;131
16;Chapter 12: Implementing “Rectangle”;132
16.1;rectangle();132
16.2;rectangle_pattern();133
16.3;rectangle_cell();136
16.4;rectangle_step();137
16.4.1;Case A: n == 0 and kBeq < 3;140
16.4.2;Case B: n > 0 and kBeq < 3;141
16.4.3;Case C: n == 0 and kBeq == 3;141
16.4.4;Case D: n > 0 and kBeq == 3;142
16.5;An Example;142
16.5.1;rectangle_step(): for 6, kBeq 0, chain: (1,5);142
16.5.2;rectangle_step(): for 6, kBeq 1, chain (1,5) (0,6);143
16.5.3;rectangle_step(): for 6, kBeq 2, chain (1,5) (0,6) (7,7);143
16.5.4;rectangle_step(): for 6, kBeq 3, chain (1,5) (0,6) (7,7) (6,5);143
16.5.5;rectangle_step(): for 6, kBeq 1, chain (1,5) (0,7);144
16.5.6;rectangle_step(): for 6, kBeq 2, chain (1,5) (0,7) (6,6);145
16.5.7;rectangle_step(): for 6, kBeq 3, chain (1,5) (0,7) (6,6) (7,4);145
16.5.8;rectangle_step(): for 9;146
16.5.9;Pointing-line within rectangle;146
16.6;Summary;147
17;Chapter 13: Implementing “Backtrack”;148
17.1;display_strats_in_clear(?);153
17.2;Optimization;153
17.3;An Example;156
17.4;Summary;162
18;Chapter 14: Solving Thousands of Puzzles;163
18.1;The Example of Minimum Sudokus;165
18.2;Summary;167
19;Chapter 15: Generating Sudokus;168
19.1;Generating a Solved Sudoku;168
19.1.1;init() for the Generator;172
19.1.2;fill();173
19.1.3;fill_digit();175
19.2;Removing Clues to Make a Puzzle;180
19.2.1;brute_comp();191
19.2.2;inconsistent_unit() for the Generator;196
19.3;Check for Uniqueness of the Solution;197
19.4;Completing the Generator;199
19.5;Utilities for the Generator;201
19.6;Summary;207
20;Chapter 16: Puzzle Statistics and More Puzzles;208
20.1;Statistic on Number of Clues;208
20.2;Statistic on Numbers;211
20.3;Statistic on Solutions;212
20.4;Timing;215
20.5;Generating More Puzzles;217
20.5.1;Number Shifting;217
20.5.2;Rotating, Flipping, and Mirroring;219
20.5.3;Swapping Lines and Triplets of Lines;221
20.5.4;Removing Different Numbers of Clues;222
20.6;Summary;223
21;Chapter 17: Special Sudokus;224
21.1;Designer Sudokus;224
21.2;Symbolic Sudokus;229
21.3;Summary;232
22;Chapter 18: Multi-Grid Sudokus;233
22.1;There Are Many Different Multi-Grid Sudokus;234
22.2;How You Join the Grids;236
22.3;How the Generator Does It;238
22.4;Displaying a Multi-Grid Sudoku;247
22.5;Designer Multi-Grid Sudokus;254
22.6;Summary;262
23;Chapter 19:Development Environment;263
23.1;Eclipse;263
23.1.1;Setting Up Eclipse on a PC;263
23.1.2;Coding Style;266
23.2;Setting Up the Solver and the Generator;268
24;Chapter 20:Abbreviations and Acronyms;272
25;Index;273