Giulio Zambon's Website
Non-fiction - Books and manuals - Sudoku Programming
Sudoku Programming
by Giulio Zambon

ISBN: 978-0-9808159-1-7
Publisher: Harry Maxwell Publications through Lulu.
Publication date: 2011-04-04. Pages: 365.

List price: USD 30.00
Available from (on 2011-04-23):
    Lulu for USD 30.00 in print and for USD 9.99 in PDF format with ISBN 978-1-4717-9794-1

Here are some PDFs that will tell you more about the book: table of contents, table of figures, and table of listings.

After reading this book, you will be able to generate all sorts of Sudokus, including pattern-Sudokus like the following one:

heart Sudoku

What follows is the Introduction section from the book.

Introduction

Welcome to Sudoku Programming. The purpose of this book is to teach you how to write computer programs to solve and generate Sudoku puzzles.

This is a practical book. My intention is not to teach you how to become a software developer, but rather how to use computer programs to deal with Sudoku puzzles. Therefore, you will not find here theoretical analyses of algorithms, solvability problems, or complexity theory.

All the code I present and comment in this book conforms to the ANSI-C standard as described in The C Programming Language, by Brian W. Kernighan & Dennis M. Ritchie, Second Edition, Prentice Hall Software Series, ISBN 978-0131103627. It is a testament to the validity of the "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 Sudoku 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.

Chapter 1 describes the notation I use throughout the book and how I represent Sudoku grids in C.
Chapter 2 lists and explains the strategies I implement in the Solver program.
Chapter 3 describes the structure of the Solver and its general utilities.
Chapter 4 to 13 explain how I implement in C the solving strategies described in Chapter 2.
Chapter 14 describes how the Solver can accept input from file and solve many puzzles one after the other.
Chapter 15 describes in detail the Generator program.
Chapter 16 analyses the puzzles that the Generator creates.
Chapter 17 presents some of the classic Sudoku puzzles.
Chapter 18 shows how to build Samurai puzzles.
Appendix A provides a summary of the C programming language focussed on what is needed to understand the code presented in the book.
Appendix B explains how to install the software on a Windows PC and on a Macintosh.
Appendix C provides the solution of the puzzles presented in Chapter 17.
Appendix D lists the abbreviations and acronyms I use in the book.

With the exception of trivial include files, I have listed and explained every module. I hope you will enjoy reading and using the book as much as I enjoyed writing it.

Back-cover blurb

The purpose of this book is to teach you how to write computer programs to solve and generate Sudoku puzzles. If you love Sudoku and have some knowledge of computer programming, you will have no problem in understanding the code of my Sudoku Solver and Sudoku Generator.

I have included in the book the full listings of both programs and an explanation of each C module, with walk-throughs and examples. To make your life easier, I have also included a description in detail of the sixteen solving strategies implemented in the Solver and a summary of the C language.

By following the instructions contained in this book, you will be able to create a practically unlimited number of original Sudokus.

To stimulate your creativity, I have also added a chapter about Samurai Sudokus, and a program to help you generate them.

This is a practical book that will provide you with everything you need to write your own books of Sudoku Classic and Samurai puzzles.

History

Sudokus are so popular that they systematically increase newspaper circulation. This has resulted in the publication of many books about how to solve Sudokus. But how to generate Sudokus is a highly-guarded secret. Even on The WorldWide Web the information about Sudoku-generating strategies is limited and fragmentary. The obvious explanation (although not necessarily true!) is that those who possess the programming and problem-solving skills necessary to write software capable of solving and generating Sudokus choose to sell their puzzles rather than divulge their tricks.

That's why I decided to write a book explaining in detail how to develop a Sudoku-generating program. I then immediately realised that I also had to include a program capable of solving Sudokus with as many strategies as possible. Otherwise, it would have not been possible to estimate the difficulty of the generated Sudokus, which is necessary for two main reasons:

  1. Ungraded Sudokus are unsellable, because the publishers of puzzles are only interested in Sudokus of known difficulty
  2. I wanted to be able to weed out Sudokus that could only be solved by guessing.

I started working on the software at the beginning of December 2010 and completed the book around mid February 2011.

When I had almost completed it, at the beginning of January 2011, I proposed it to Apress, which had already published my book Beginning JSP, JSF, and Tomcat Web Development. They had already published in 2006 a book titled Programming Sudoku by Wei-Meng Lee, but its generator program was very simple and its solver program only used comparatively easy strategies. Moreover, the software had been written in Visual Basic.

Unfortunately, after publishing Wei-Meng's book, Apress had decided that the subject was not in line with what the readers expect from them. As a result, they rejected my proposal.

The problem with this book is that it is a serious programming book written about a puzzle. It falls outside the scope of both publishers of puzzle books and of computer manuals. Even my editor at Apress, who has been in the publishing industry for a long time, couldn't come up with any suggestion.

I contacted Pearson Australia, the local subsidiary of "the global leader in educational publishing", and they suggested that I contact their head office. I contacted Simon Lake, a Product Development Director, but he didn't bother to reply.

I had in fact expected that small publishers wouldn't take the risk and large publishers would probably ignore me. On advice from a fellow Mensan, I contacted Sid Harta Publishers. They are an Australian company that does both straight publishing and vanity publishing. They replied to my book proposal by saying: "with the current demise of A & R/Borders your SP book might be best served as an eBook initially." I pointed out that computer code cannot flow and that most current e-readers have too small a screen to accomodate the many figures and the listings. Do you know what their reply was? You guessed it: none.

That's when I decided to self-publish it.

Errata

Since publishing the book, I have discovered that several typos and other mistakes have slipped through review and copy-edit. I will correct them in the next edition but, for the time being, this page seems the best place to make the corrections available.
To suggest further changes, send me an email to the address shown on the homepage of this site. Thanks.

For your convenience, I have highlighted the errors that can compromise the understanding of the text.

# Ch Page[s] Section Paragraph Description
1 1 5   2 Replace (7,4) with (6,4)
2 2 18 The strategy 'XY-chain' 2 Remove the repetition of the word arrays
3 3 37 cleanup() 2 replace Remove_unit() with cleanup_unit()
4 4 56 unique_unit() 3 Insert a comma after skips (4,1)
5 7 88-91 unique_unit() several In the descriptive text, replace all occurrences of the variable s with the variable b
6 7 89 box_line_unit() Fig 7-1 Replace the 1 in cell (8,2) with an 8
7 7 90 box_line_unit() 2 Insert the between corresponding to and three digits
8 7 90 box_line_unit() 2 Replace (3,5) with (3,4)
9 7 90 box_line_unit() 3 Replace The same happens again when (3,7) is processed, while (3,8) is ignored because it is with (3,7) and (3,8) are ignored because they are
10 7 91 box_line_unit() 2 Replace excution with execution
11 8 93   1 Replace the the in a line with the box to an a
12 8 97 pointing_line_box() 6 Replace two vectors contain with array contain
13 8 97 pointing_line_box() 7 Replace cc[*][ROW] with rc[*][COL]
14 10 119 y_wing_digit() 3 Insert at between are looking and a chain
15 11 138 'XY-chain' Example last Change start to starts
16 12 143 rectangle() 3 Indent the second paragraph of rectangle()
17 12 144 rectangle_pattern() 3 Change ractangle_pattern to rectangle_pattern
18 12 149 rectangle_step() 4 In First off, rectangle_cell(), change rectangle_cell to rectangle_step
19 13 172 An Example 1 Indent the paragraph
20 13 174 An Example Fig 13-4 Move the caption to the bottom of the previous page
21 13 174 An Example 1 Change only get to only gets
22 15 186 fill() 1 Change -2 to 2
23 13 174 An Example 2 Change backtrack() to monospace font
24 15 190 fill_digit() 4 Change 9 to 8, It second to Its second, IDs of the box to IDs of the boxes, row of box 2 to columns of box 2, and no further row to no further boxes whose columns have to be considered
25 15 191 fill_digit() 3 Change save its coordinates to saves its coordinates
26 15 213 brute_comp() 4 Change go back to goes back
27 B 286-298   headers Change from Installation to Development Environment

Chapters 7 and 15 seem to have been somewhat neglected. Sorry about that...

Valid XHTML 1.0!   Valid CSS!