[Update 10-14-2012: the spreadsheet is no longer available. I turned the process into PDFs]

Does the world need yet another printable Sudoku puzzle software? Of course it does. I wanted to make one using my creaky spreadsheet programming skills. Along the way, I made a startling discovery…

…Sudoku puzzles are nothing more than collections of cryptograms!
This does not mean you can solve a Sudoku puzzle like a Cold War spy. Maybe.
But if you want to quickly create an absurdly large number of puzzles, you no longer have to create a tentative puzzle and exhaustively check it for accuracy. Just grab your code key and translate one Sudoku puzzle into another! I’ll demonstrate the technique with pictures.

Consider the first grid to be the solution to a particular Sudoku puzzle. Consider a substitution key where 1 becomes 4, 2 becomes 9, 3 stays 3, 4 becomes 5, 5 becomes 8, 6 stays 6, 7 becomes 1, 8 becomes 2 and 9 becomes 7. After translating the first grid, we arrive at the second grid!
Now that you know the “secret”, you can use your favorite program to generate new Sudoku Puzzles!

Here are some tricks I used for Printable Spreadsheet Sudoku:

1. I randomly select one of 99 different solutions
2. For the substitution key I use one of the rows in the solution!!
3. I randomly shift and rotate the grid, ensuring that the puzzle remains intact
4. Blank squares are randomly displayed – more blanks mean a tougher challenge

I limited the total number of possible combinations because I figured 48,000 puzzles is enough. By the time you finish them, you won’t even remember the first batch and you can play all over again!

Who’s Out There?

I wanted to see if anyone else had created Sudoku Puzzles based on substituting values. I discovered an interesting site:

This site has a Sudoku variation called Twin Corresponding Sudoku. Henry Kwok is the author.
This variation requires you to use cryptography in order to help solve both puzzles simultaneously.

Sudoku Generator Broken: Project Terminated

One of my most enjoyable pastimes is generating puzzles. Because of my programming background, I often try to reproduce puzzles on my computer. If the program becomes too difficult, I abandon the project and think about why I couldn’t solve it. This happened with my desire to write a Sudoku generator. In fact, I didn’t know where to begin.

I had done some research on Sudoku solvers, which are programs that fill in the Sudoku grid. My reasoning was that a solver would have to have some foreknowledge of the creation of the puzzles. By the time I had read enough to know that such programs were non-trivial, I had already given up ever designing my own Sudoku generator.

I couldn’t stop thinking about the complexity of this type of project. Part of the obsession had to do with my inability to solve Sudokus in a reasonable amount of time. I was convinced that a simple solution was “out there”. Without being dramatic, let me just state that one day, I realized that a single completed puzzle could be used to generate a new puzzle, just by swapping one digit for another.

Precursor to my Sudoku Generator
At the time, I was unaware that I was thinking about what is known as “relabeling”. I called the idea “cryptogram-like substitution” and added a few rotations and column swapping that preserved the integrity of the Sudoku grid, while creating a completely different puzzle. I shared this process in an article called Printable Spreadsheet Sudoku.

That was three years ago. This past weekend, I decided to automate those concepts. Meanwhile, I delved back into the web to see if anyone else was doing this. What I found, instead, was a validation of these ideas from a mathematical perspective. In other words, I didn’t really come up with anything new; I simply stumbled on to some insights about the nature of Sudoku puzzles and applied them to creating new puzzles!

As I read the different articles, I noticed that programmers are still trying to write Sudoku generators from scratch. As an exercise, there is nothing wrong with that approach. But, what if you just want an unlimited number of Sudokus to print out whenever the mood strikes? In that case, my method will serve just fine. Here’s a silly joke I made up to point out this philosophy: A freshman chemistry student asks the professor, “What’s the best way to produce carbon dioxide in the laboratory?” The professor says, “Breathe.”

So, by deconstructing existing puzzles, I avoided the complexities inherent in designing the puzzles from scratch. Two of the most arduous complexities are guaranteeing the uniqueness of the solution and determining the difficulty level of the puzzle. My automated generator simply maps these attributes onto new puzzles! Of course, there exists the possibility that the source puzzle is not unique. That would suck, but I am not about to test each puzzle for that. I basically stick to published solutions from reliable sources. In essence, I’m deriving new puzzles based on existing patterns. I’m simply breathing.

As for the difficulty level, different sources subjectively rate their puzzles. I’ve read comments from people who’ve solved a five-star puzzle but have gotten stuck on a two-star puzzle from the same source. So, how do I map the difficulty level onto new puzzles? I use an existing puzzle’s starting pattern! Sudoku puzzles usually have a nice symmetry to them. I can rotate a pattern or reuse it. Either way, the pattern is independent of the “relabeling” and transposing. This greatly increases the number of puzzles that can be generated from the same initial solution.

Difficulty Made Easy!
In my 2009 post, I stated that I only used 48,000 possible combinations (before relabeling.) While I still maintain that that is more than enough variety, my new Sudoku generator uses a few more transformations and an ever-growing list of source puzzles. Combine those factors with relabeling and the difficulty levels and my program can crank out millions of Sudoku puzzles. Yay.

I’m actually going to step through this process, one piece at a time. You’ll be able to make your own Sudoku generator, using the programming language of your choice.

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:

• Relabeling
• Rotation
• Reordering

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.

Getting Started

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:

• PDFCreator
• Access 2007

Well folks, it turns out that my generator does not create unique puzzles. The techniques for preserving Sudoku symmetry also preserve the non-uniqueness attribute of a pre-existing puzzle. Garbage in, garbage out. I wonder which of my source puzzles did me in? Oh well!

Rather than waste time trying to solve something that plagues Sudoku programmers, I’m terminating this tutorial and pulling the book.

Guess I’ll visit this project again, someday.

Thanks to eagle-eyed Mitch Mitchell of ImJustSharing.com, who play-tested a copy of the puzzles:

Broken Sudoku has multiple solutions