Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Sudoku programming with C
Zambon G., Apress, Berkeley, CA, 2015. 300 pp. Type: Book (978-1-484209-96-7)
Date Reviewed: Jul 20 2015

This book is for readers whose primary interest is Sudoku puzzles. A knowledge of programming and C is assumed, as the book is not intended to teach these, nor how to become a software developer. It simply explains the author’s programs to solve and generate Sudoku puzzles.

Two C programs, Solver and Generator, are described in the book. The first chapter introduces the two programs and the representation of a Sudoku puzzle used in the programs (not surprisingly, a multi-dimensional array). The second chapter describes and shows examples of the 15 strategies used by the Solver program to solve Sudoku puzzles. The strategies are grouped into five levels of increasing sophistication (or difficulty). As a last resort, a 16th strategy, brute force with backtracking, is used. The explanations and examples are very helpful when discussing the actual implementation of each of the strategies.

Most of the rest of the book (chapters 3 through 14) is devoted to the Solver program. Chapter 3 describes the main module that accepts the puzzle to be solved, invokes the various strategies until the puzzle is solved, and outputs the result. The following ten chapters then describe the implementation of the various strategies, in order of complexity.

The chapters and discussions include complete C listings for the modules. The sources are available on the companion website, though strangely this is not mentioned, nor the location given, until chapter 14. By that time, the interested reader will have likely already searched for and found the sources.

The discussion and explanation of the C modules is relatively straightforward and generally clear. The modules are in a consistent format, and the style of the C programs is reasonable and conforms to ANSI standard C. Arrays are used extensively with little use of pointers. The emphasis is on clarity rather than efficiency, so there are no hard-to-figure-out optimizations or coding tricks. There is, however, a dearth of comments in the code, though the explanation in the book largely makes up for that. One thing lacking in the program listings in the text is line numbers. These would have made it much easier to refer to code in the discussion, as well as made it much easier for the reader to know exactly which part of the program was being referred to. Instead, references are to things like the for loop, the second if statement, and so on, which the reader has to search for. I cannot guarantee that the programs are bug free; however, as a practicing software developer who writes and reviews C code on a daily basis, I found no errors in the code.

The Generator program for generating Sudoku puzzles is described in a single chapter (15). The algorithm used is neither subtle nor very efficient, but it does work and it is simple to understand. The program generates a completely filled in (or solved) Sudoku grid at random by brute force, trying all possible combinations and backtracking when necessary. A configured number of cells in symmetrical positions are then cleared, again choosing the cells at random.

If the resulting puzzle has a unique solution, the removal continues until a unique solution cannot be found. In checking for a solution, brute force is used rather than applying the Solver program. Different puzzles are generated using different seeds in the standard C random number generator.

Chapter 16 does some analysis of puzzles generated by the Generator, showing statistics like how many clues (solved cells) are in each puzzle and how many and which strategies are needed to solve the puzzles. Chapter 17 shows how to generate puzzles with the clues in specific patterns, such as a smiley face or a heart. Chapter 18 shows how to generate multi-grid Sudokus--puzzles where some of the cells of one Sudoku overlap the cells of one or more other Sudokus.

An appendix describes how to set up and run the Solver and Generator programs using Eclipse in a Windows or Mac operating system (OS) environment. Strangely, given the programs are written in C, no makefile is supplied with the sources, though for Linux users compiling the programs is straightforward. A short list of acronyms and a short index conclude the book.

Though its purpose is limited, the book fulfills that purpose very well. Any programmer interested in Sudoku puzzles will find it interesting. The programs could be used as a starting point for other similar puzzles (Kakuro, anyone?). It can also be useful to anyone looking for an example of a nontrivial program to review or analyze, or how certain techniques such as backtracking can be used in practice.

Reviewer:  Andrew R. Huber Review #: CR143630 (1510-0882)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Games (K.8.0 ... )
 
 
Backtracking (I.2.8 ... )
 
 
C (D.3.2 ... )
 
 
General (D.1.0 )
 
 
Problem Solving, Control Methods, And Search (I.2.8 )
 
Would you recommend this review?
yes
no
Other reviews under "Games": Date
How to beat your chess computer
Keene R., Levy D. (ed), Henry Holt, New York, NY, 1992. Type: Book (9780805023169)
Jun 1 1994
Relationships between fun and the computer business
Bushnell N. Communications of the ACM 39(9): 31-37, 1996. Type: Article
Apr 1 1997
NetWarriors online
Gradecki J., John Wiley & Sons, Inc., New York, NY, 1996. Type: Book (9780471135555)
Jul 1 1997
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy