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.
Author(s): Giulio Zambon
Publisher: Apress
Year: 2015
Language: English
Pages: 300
Contents at a Glance
Contents
About the Author
Introduction
Chapter 1: Modeling a Sudoku Puzzle in C
Solving a Puzzle
Generating a Puzzle
Modeling the Puzzle
Summary
Chapter 2: The Strategies
Level 0 Strategies
The Strategy Naked Single
The Strategy Unique
The Strategy Cleanup
Usage of Level 0 Strategies
Level 1 Strategies
The Strategy Naked Pair
The Strategy Hidden Pair
The Strategy Box-Line
The Strategy Pointing Line
Level 2 Strategies
The Strategies Naked Triple and Naked Quad
The Strategy Hidden Triple
The Strategy Lines-2
The Strategy Y-wing
Level 3 Strategies
The Strategy X Y-Chain
The Strategy Rectangle
The Strategies Lines-3 and Lines-4
Level 4 Strategies
What about Coloring ?
Strategy Selection
Summary
Chapter 3: The Solver Program
init( )
cleanup( )
solve( )
Counting
Checking Consistency
Input/Output
Summary
Chapter 4: Implementing “Unique”
unique_unit( )
unique( )
unique_loop( )
Summary
Chapter 5: Implementing “Naked” Strategies
naked_pair_unit( )
naked_triple_unit( )
naked_quad_unit( )
Summary
Chapter 6: Implementing “Hidden” Strategies
hidden_pair_unit( )
hidden_triple_unit( )
Summary
Chapter 7: Implementing “Box-Line”
box_line( )
box_line_unit( )
Summary
Chapter 8: Implementing “Pointing Line”
pointing_line( )
pointing_line_box( )
Summary
Chapter 9: Implementing “Lines” Strategies
lines_2( )
lines_3( )
lines_4( )
lines( )
An Example
Summary
Chapter 10: Implementing “Y-wing”
pairs_find( )
y_wing_digit( )
intersection( )
footprint( )
An Example
Summary
Chapter 11: Implementing “XY-chain”
xy_chain_digit( )
xy_chain_step()
An Example
Summary
Chapter 12: Implementing “Rectangle”
rectangle()
rectangle_pattern()
rectangle_cell()
rectangle_step()
Case A: n == 0 and kBeq < 3
Case B: n > 0 and kBeq < 3
Case C: n == 0 and kBeq == 3
Case D: n > 0 and kBeq == 3
An Example
rectangle_step(): for 6, kBeq 0, chain: (1,5)
rectangle_step(): for 6, kBeq 1, chain (1,5) (0,6)
rectangle_step(): for 6, kBeq 2, chain (1,5) (0,6) (7,7)
rectangle_step(): for 6, kBeq 3, chain (1,5) (0,6) (7,7) (6,5)
rectangle_step(): for 6, kBeq 1, chain (1,5) (0,7)
rectangle_step(): for 6, kBeq 2, chain (1,5) (0,7) (6,6)
rectangle_step(): for 6, kBeq 3, chain (1,5) (0,7) (6,6) (7,4)
rectangle_step(): for 9
Pointing-line within rectangle
Summary
Chapter 13: Implementing “Backtrack”
display_strats_in_clear( )
Optimization
An Example
Summary
Chapter 14: Solving Thousands of Puzzles
The Example of Minimum Sudokus
Summary
Chapter 15: Generating Sudokus
Generating a Solved Sudoku
init() for the Generator
fill()
fill_digit()
Removing Clues to Make a Puzzle
brute_comp()
inconsistent_unit() for the Generator
Check for Uniqueness of the Solution
Completing the Generator
Utilities for the Generator
Summary
Chapter 16: Puzzle Statistics and More Puzzles
Statistic on Number of Clues
Statistic on Numbers
Statistic on Solutions
Timing
Generating More Puzzles
Number Shifting
Rotating, Flipping, and Mirroring
Swapping Lines and Triplets of Lines
Removing Different Numbers of Clues
Summary
Chapter 17: Special Sudokus
Designer Sudokus
Symbolic Sudokus
Summary
Chapter 18: Multi-Grid Sudokus
There Are Many Different Multi-Grid Sudokus
How You Join the Grids
How the Generator Does It
Displaying a Multi-Grid Sudoku
Designer Multi-Grid Sudokus
Summary
Chapter 19:
Development Environment
Eclipse
Setting Up Eclipse on a PC
Coding Style
Setting Up the Solver and the Generator
Chapter 20:
Abbreviations and Acronyms
Index
