Skip to main content
main-content

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Modeling a Sudoku Puzzle in C

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

Chapter 2. The Strategies

Not all strategies are created equal. When solving a Sudoku puzzle manually it makes sense to use simpler strategies as long as they result in candidate removals and cell solutions, and only then move to more complex strategies. Obviously, there is no reason for making the same distinction when writing a computer program to solve Sudokus. And yet, that is precisely how I structured my Sudoku-solving program. The reason is that I want to use the Sudoku Solver to estimate the difficulty of Sudoku puzzles. If the program applied more complex strategies before achieving what is possible with simple ones, it would be impossible to know whether the complex strategies were needed at all.
Giulio Zambon

Chapter 3. The Solver Program

The main program, sudoku_solver.c, accepts the Sudoku to be solved, performs some checks, solves the Sudoku, and presents the final result. It is the module that binds together all the various functions of the program.
Giulio Zambon

Chapter 4. Implementing “Unique”

The “unique” strategy looks for candidates that are unique within a unit. This happens when all other candidates for the same number are removed from the unit (see Figure 4-1).
Giulio Zambon

Chapter 5. Implementing “Naked” Strategies

The three naked strategies, naked pair, naked triple, and naked quad, work on the same general principle: unit by unit, first make a list of all the cells containing naked multiples (i.e., pairs, triples, or quads), and then process the multiples that appear the correct number of times within the unit. If it sounds confusing, read on and it will become clear.
Giulio Zambon

Chapter 6. Implementing “Hidden” Strategies

The two “hidden” strategies, hidden pair and hidden triple, have the same general design: first, they build lists of the cells containing each candidate number; then, they analyze the lists to see whether pairs or triples are hidden inside the lists.
Giulio Zambon

Chapter 7. Implementing “Box-Line”

As with most strategies, you implement “box-line” with two functions: one general that conforms to the type f_ptr_t as defined in def.h and one to handle an individual unit. The general function, box_line() (see Listing 7-1), executes box_line_unit() (see Listings 7-2 and 7-3) for each possible row and column of the Sudoku.
Giulio Zambon

Chapter 8. Implementing “Pointing Line”

As I explained in Chapter 2, pointing-line is similar to box-line in that they both look at the intersection of a line with a box. Therefore, it is not surprising that the implementations of the two strategies are quite similar.
Giulio Zambon

Chapter 9. Implementing “Lines” Strategies

As I already said in Chapter 2, the lines strategies rely on parallel rows and columns. You can implement all lines strategies with three small functions named lines_2(), lines_3(), and lines_4() (see the respective Listings 9-1, 9-2, and 9-3) that set up the arguments for and then execute a generalized function named lines() (see Listing 9-4).
Giulio Zambon

Chapter 10. Implementing “Y-wing”

The Y-wing strategy is quite complex, which is reflected in the complexity of its implementation.
Giulio Zambon

Chapter 11. Implementing “XY-chain”

This strategy is an extension of Y-wing. Therefore, it is not surprising that the two strategies share a significant amount of code.
Giulio Zambon

Chapter 12. Implementing “Rectangle”

The rectangle strategy is the first level 3 strategy that is not an extension of easier ones. As I explained in Chapter 2, this strategy relies on sets of cells that form rectangular patterns. You implement it with the functions rectangle(), rectangle_pattern(), rectangle_cell(), and rectangle_step() (see Listings 12-1, 12-2, 12-3, and 12-4, respectively).
Giulio Zambon

Chapter 13. Implementing “Backtrack”

As I have already explained in Chapter 2, backtracking is a nice way of saying “guessing.” When you exhaust all strategies you know, you can only pick a cell that you haven’t yet solved and try out one of its candidates. If you reach a contradiction, you need to revert the Sudoku grid back to what it was before your arbitrary choice and try another candidate—hence the “back” of backtracking.
Giulio Zambon

Chapter 14. Solving Thousands of Puzzles

The Solver program accepts a Sudoku string as an argument. This is OK when you want to solve a few Sudokus, but it is completely inadequate when you want to obtain statistical data on solving puzzles. For that, you need to be able to solve thousands of puzzles one after the other. The obvious solution is to store Sudoku strings in a file and let the Solver load them one at a time. You do it by adding the following define to the beginning of sudoku_solver.c (see Listing 3-2, Listing 3-3, Listing 3-4, and Listing 3-5): #define USE_FILES. Then insert the code shown in Listing 14-1 immediately after checking the consistency of the strategy arrays (you can find the code for this book in the Source Code/Download area of the Apress web site ( www.apress.com )).
Giulio Zambon

Chapter 15. Generating Sudokus

To generate a valid Sudoku puzzle you have to go through the following two steps: generate a completed Sudoku and remove numbers from it in such a way that only one solution is possible with the clues that are left.
Giulio Zambon

Chapter 16. Puzzle Statistics and More Puzzles

According to Wikipedia, the total number of possible solved Sudokus is a staggering 6,670,903,752,021,072,936,960 ( http://en.wikipedia.org/wiki/Sudoku , accessed on February 6, 2015). Moreover, it is possible to create many different puzzles resulting in each one of the 6.67 sextillions of solved Sudokus. Therefore, you might be disappointed that the Generator as described in the previous chapter can only produce up to 2,147,483,648 different puzzles because that is the number of different pseudorandom seeds you can choose from.
Giulio Zambon

Chapter 17. Special Sudokus

Now that you know how to generate standard Sudoku puzzles, it is time to learn how to make some special ones.
Giulio Zambon

Chapter 18. Multi-Grid Sudokus

You obtain a multi-grid Sudoku when you combine two or more classic puzzles by partially overlapping them. For example, Figure 18-1 shows a double Sudoku.
Giulio Zambon

Appendix A. Development Environment

I developed the Solver and the Generator on a Macintosh, but from the very start I wanted to be certain that they were portable to Windows-based PCs. That is why I chose Eclipse as an Integrated Development Environment rather than Apple’s Xcode. This appendix will show you how to set up and run the Solver and Generator.
Giulio Zambon

Appendix B. Abbreviations and Acronyms

ANSI
Giulio Zambon

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise