Sudoku Generator Broken: Project Terminated
This multi-part tutorial is for anyone who wants to make a Sudoku generator without starting from scratch. Aside from programming considerations, the pros and cons boil down to puzzle quality. If you are a Sudoku purist, you probably want a program that can generate specific challenges. While this Sudoku generator derives its new puzzles from known grids, the starting patterns, also known as the clues or the givens, is limited to the number of patterns that you are willing to add to it. That’s a time-consuming prospect.
On the other hand, if you just want to have a steady supply of puzzles for the cost of printing supplies, you’ll love this Sudoku generator! Microsoft Access is used in this tutorial. You should be able to apply the techniques using your favorite development platform.
Sudoku Generator Overview
For now, let’s define some terms, identify some constraints and give you one last chance to run screaming in the other direction. The next post will begin the project in earnest.
The premise of this project is to reuse everything. From a programming perspective, looking up values is more efficient than calculating them. If this sounds like plagiarism, consider the following: we are not wholesale copying puzzles from sources and spitting them out. Furthermore, nobody has a copyright on Latin Squares! We’re simply using known quantities as a starting point.
Sudoku Generator Derivative Works
Sudoku grids are a subset of numerical arrays known as Latin Squares. Theoretically, the absolute simplest way to retrieve a Sudoku puzzle is to look it up in a list of Latin Squares. However, there are far too many distinct grids to make this feasible.
Despite that, the Sudoku generator can create our own list of Sudoku grids, which we will call solutions. Instead of retrieving all known solutions, our Sudoku generator will derive new solutions from a few starting grids. These initial grids will “seed” our list. As a bonus, newly generated solutions will become part of the seed list!
The key to deriving new solutions is to preserve the Sudoku symmetries:
According to the linked article, rotating and reordering alone yield 5,472,730,538 unique grids. When relabeling is factored in, the total is an unfathomable 6,670,903,752,021,072,936,960 grids! Needless to say, our Sudoku generator doesn’t even have to implement every symmetrical operation to be able to produce a nice collection of solutions.
Sudoku Generator Starting Points
Creating grids is one thing; generating a series of Sudoku puzzles – from easy to extreme – is another beast. This Sudoku generator relies on our willingness to manually add interesting starting patterns to our database. “Interesting” means pleasing to the eye as well as appropriately challenging. After having researched the concept of assigning difficulty levels to generated puzzles, I by-passed the complexities in favor of punching in existing starting points. Throughout this tutorial, this collection of manually supplied clues is called templates. You’ll discover that the variety of your puzzles is limited by the size of this collection.
Another starting point is the key used to relabel a grid. The digits 1 to 9 can be rearranged in more than 300,000 ways. Again, we don’t need to store every one, but we can create a seed list, which we’ll call the crypto collection. As new solutions are created, our Sudoku generator will derive new keys to add to this collection. This collection ensures that we won’t easily recognize repetitions due to our relative small collection of templates.
One thing that I do with my templates is rotate them and save the new template. This gives me two templates for each one that I enter. However, I’m pretty sure that this technique invalidates the difficulty rating, even though I arbitrarily assign the same level to the rotated template. If you don’t like that part, don’t add rotated templates to your collection.
Printing Sudoku Generator Grids
This is the one part of the tutorial that doesn’t rely on Sudoku logic. As a result, I will gloss over it. If you can manipulate strings, you should be able to create a decent grid. Microsoft Access gives me a lot of flexibility, at the expense of a very, very tedious setup of the grid elements. That was my choice, though. You may find an easier way to do things.
Printing choices include grid size and difficulty mix. Also, you’ll want an answer key to be at the back. Sudoku is one of those puzzles that really doesn’t need to have the answer key, except for when you give up. This means that you can just print out a bunch of puzzles to carry around with you.
That’s all for this time. If you subscribe to the Fieldnotes RSS feed, you’ll be notified when I post the next part of the Sudoku generator tutorial. Here is a mini-homework assignment. Make sure that your chosen environment has the ability to export your grids to PDF. If you are using Microsoft Access, check out one of these related articles: