Sudoku Programming with C

Sudoku Programming with C

by Giulio Zambon
Released March 2015
Publisher(s): Apress
ISBN: 9781484209950

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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.

Table of contents

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

Product information

  • Title: Sudoku Programming with C
  • Author(s): Giulio Zambon
  • Release date: March 2015
  • Publisher(s): Apress
  • ISBN: 9781484209950