Introduction
All the code I present and comment on in this book conforms to the ANSI-C standard as described in The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie (2nd ed., Prentice Hall Software Series, 1989). It is a testament to the validity of “K&R” that the book is still in print unmodified since its first publication in 1988. If you don’t have it, you should definitely buy it. No C programmer should be without it.
All the code I present and comment on in this book conforms to the ANSI-C standard as described in The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie (2nd ed., Prentice Hall Software Series, 1989). It is a testament to the validity of “K&R” that the book is still in print unmodified since its first publication in 1988. If you don’t have it, you should definitely buy it. No C programmer should be without it.
For longer than a decade before writing this book, I developed software exclusively in Java and its derivatives (e.g., JavaScript and JSP). But for this project, I decided to go back to “plain old” C. The main reason was that I didn’t want to use object-oriented (OO) technology. In general, I do prefer OO programming, but this book is mainly for people whose primary interest is Sudoku, rather than software development. For such a reader, programming is a means to an end, and writing C statements is easier than defining classes and dealing with things like class inheritance.
Most of this book concentrates on solving the puzzles, but I felt that it would be incomplete if I didn’t provide a program to generate them. There is very little information on the World Wide Web about how to generate puzzles. Perhaps it is so because once you have a program to create them, you can also sell them to magazines and newspapers (but good luck with that!).
The two main programs described in this book are the Solver and the Generator. In their development, I gave priority to clarity rather than efficiency. The two qualities are often in conflict, and many programmers make the mistake of trying to be efficient and develop the cleverest algorithms. This is often a bad strategy. First of all, modern compilers, when generating executable code from your sources, take care of any redundancy and make intelligent use of registers. Second, it is always better to write a program that runs like a dog but behaves as needed instead of one that runs very fast but is full of bugs and difficult to fix (I wish that all companies that develop commercial software adopted my priorities).
Once you have a program that works correctly, you can see where it spends most of its execution time and optimize those sections of the code to improve efficiency. But I haven’t done anything in that direction concerning my Sudoku software. The main reason is that its purpose is to show you how to solve and generate puzzles with C. Any optimization would have made it more difficult to understand.
Some of the algorithms I implemented are far from trivial. In fact, some of them are among the most difficult code I have developed. In those cases, besides explaining the code in the book, I have added some comments in the code on key points.
Chapter 1 tells you how to model a Sudoku puzzle in C and introduces you to the Solver and the Generator.
Chapter 2 lists and explains the strategies implemented in the Solver program. Although the intent is to get you to understand the the structure of the program, it also is a great little introduction to solving Sudoku puzzles in a systematic manner.
Chapter 3 describes the structure of the Solver and its general utilities.
Chapters 4 to 13 explain the implementation in C of the solving strategies described in Chapter 2.
Chapter 14 describes how the Solver accepts input from a file to solve many puzzles one after the other.
Chapter 15 describes the Generator program in detail.
Chapter 16 analyzes the puzzles that the Generator creates and explains how and explains how to create more puzzles.
Chapter 17 shows how to can create special puzzles.
Chapter 18 shows how to build multi-grid Sudokus.
Appendix A explains how to use the code provided with the book within Eclipse.
Appendix B lists abbreviations and acronyms.