davidbau.com

Sudoku Generator

Here is a free Sudoku generator that can generate puzzles of varying difficulty in PDF, Postscript, plaintext, and HTML.

It is a nice example of the website fun you can have with 250 lines of Python over a Labor day weekend; it also makes a handy command-line Sudoku solver...

What is Sudoku?

Have you ever played Sudoku? A few months ago my dad raved about a new game in the newspaper that he liked solving better than the daily crossword, and so I picked up one of the five hundred or so Sudoku books at the bookstore. I was quickly hooked.

The rules of Sudoku are simple: finish filling in the squares of a 9x9 grid so that the digits 1-9 appear exactly once in each of the nine rows, columns, and 3x3 blocks. Puzzles are designed so that there is only one correct way to fill in the 81 squares, and they tend to be just hard enough to be satisfying: not too easy, not impossible.

Ways to Play

Sudoku is a good solo game; if you are having trouble getting into it, you can read about various solution strategies on the web.

But, like crosswords, it can be even more fun to work Sudoku puzzles together with somebody else. Heidi and I sometimes race each other on adjacent puzzles in a Sudoku book - it can be nerve-wracking to try to catch up when you're behind, while the other person is rapidly filling in squares. Either player always has a chance to win a race, because backtracking in Sudoku is hard. You can be dealt a blow at the finish line when you encounter a contradiction and then realize you made a mistake long ago. (The best strategy in Sudoku is not to guess, yet it's still good to play with an erasable pencil.) It can also be fun to cooperate on a Sudoku puzzle - the entertainment there is to be stymied together, and then question the other person's clever move to get out of a logjam.

There are many Sudoku variants, for example versions of the game where the 9-square blocks come in different shapes, or smaller versions of the game that are designed for children.

I realized Sudoku was a major phenomenon when I saw the Dora Sudoku books for preschoolers. Since they are for the preliterate set, you fill in simplified 4x4 puzzles using stickers instead of letters or numbers. The amazing thing is that my pre-K daughter Piper was completely enthralled by the books. We brought a Dora Sudoku book on our trip to Taiwan, and solving Sudokus became the most reliably fun activity for Piper whenever she was waiting around, remarkably beating out her Nintendo DS.

I guess it's no wonder that they recently came out with Sudoku for the Nintendo DS too.

Counting Sudoku Boards

But if you read the advertisements for Sudoku Gridmaster for DS, you will notice that it is said to come with "over 400" Sudoku puzzles. With crosswords, I can understand why your software might have only a few hundred puzzles, since each hint needs to be done by a human editor. But with Sudokus, I wonder why they don't just let the software generate millions of puzzles? Imagine how many millions of puzzles "included" they could claim.

Solved Sudokus are a special kind of Latin square, which were studied by Euler. Euler discovered that there did not seem to be very many Latin squares of a certain type, and in 1782 he proposed that the 36 Officers Problem had no solution for 6x6, 10x10, 14x14 squares, and so on. His conjecture stood until the 20th century. But in 1959, a set of 10x10 "Euler's Spoiler" squares were discovered by Parker, Bose, and Shrikhande (in work popularized by Martin Gardner) disproving Euler's famous conjecture. Mathematicians continue to play with and theorize about Latin squares today.

How many different ways are there to completely fill in the 81 squares of a Sudoku board? In May 2005, Felgenhauer and Jarvis counted the Sudoku boards carefully and concluded that there are exactly 6,670,903,752,021,072,936,960 solved boards. These thousands of billions of billions are so large that there would really be no hope of using a supercomputer to enumerate all the boards: the only way to count them all is to understand the symmetries of the game.

If you have one solved board, you can get another equivalent one by relabeling digits, swapping rows within a 3-row-band, swapping bands, swapping columns within a 3-column-stack, swapping stacks, or by rotating the whole board. How many "really different" boards are there which cannot be created from each other by just swapping things around this way? Jarvis and Russell concluded that the kernel of really distinct boards is still pretty large, numbering 5,472,730,538. Yet this number is small enough for a computer, and it is possible (although tricky) to write a program to enumerate all these boards quickly.

Counting Sudoku Hints

For puzzlers, a solved board is not as interesting as an unsolved one! And among unsolved puzzles, the interesting ones are the minimal ones: the puzzles which uniquely determine a single solution, and for which you cannot erase any hint without permitting extra solutions. How many minimal Sudoku puzzles are there? Certainly the number must be far more than the number of solved Sudoku boards, but the total count is unknown. In fact, it is not even known for sure how small a minimal puzzle can be!

My simple program for generating minimal puzzles typically generates Sudoku puzzles with 24 or more hints. I have never seen it generate a puzzle with fewer than 22 hints. But there are some puzzles that are much smaller. Gordon Royle mainains a list of (currently) 36628 nontrivially distinct and fully constrained Sudoku puzzles with 17 hints.

Some mathematicians suspect that the smallest number of hints you can give in a Sudoku puzzle that uniquely determines a fully solved board is 17, because concerted searches for a fully constrained puzzle with only 16 hints have come up dry. In fact, it is hard to find 17-hint puzzles too, and Gordon's list of 17-hint puzzles might be nearly complete. If this could be proved, it would also prove that there are no 16-hint puzzles.

So if you find a 17-hint puzzle, you should check to see if Gordon already has it. And remember that there is no proof that fully determined 16-hint puzzles don't exist. If you get a 16-hint puzzle out of the automatic puzzle generator, don't throw it out. It would be publication-worthy.

Sudoku Generation Algorithm

How can you generate Sudoku puzzles? I do not know what the 'best' algorithm is, but here is what I have done in my simple little python program.

First, we need a Sudoku solver. My solver uses three simple strategies to solve a board; they are simple to implement and seem fast enough.

1. If only one number fits in a square without row, column, and box conflicts, we fill it in.
2. If a number needed by a row, column, or box can only go in one square in that row, column, or box, we fill it in.
3. If we can't fill in anything using rules 1 or 2, then we find a most-constrained place or number where we can guess (for example, two choices is better than three), and we try all the guesses.

The last bit about trying all the guesses will require some backtracking. When we are selecting a place to guess, we choose one randomly among the most-constrained places, and we shuffle the choices to try them in a random order.

The result is if we tell the solver to solve an empty board, we get a nice random fully-solved Sudoku board.

To generate Sudoku puzzles, we start with a solved board, and we choose some minimal hints to reveal as follows.

1. Going through the squares in shuffled order, reveal each square only if it is not deduced by the other revealed squares (using the solver without guessing). This produces a list of about 30 to 40 hints which together dermine the 81 squares of the board.
2. Going through the chosen hints in shuffled order, attempt dropping each one, and fully solve the board far enough to find two solutions if there are two. Replace the hint unless the solution is still unique with the hint removed.

Notice that generating a minimal puzzle this way requires us to do the work of solving a Sudoku board about twenty times, so it takes a lot more work to generate a minimal Sudoku puzzle than it does to solve one. If there are ways of generating Sudoku puzzles more quickly, I'd love to know.

Rating Puzzles

Any Sudoku fan will tell you that there are hard puzzles and easy puzzles. The newspapers like to save the really diabolical ones for the Friday edition, so you can stew over them all weekend. The hardest puzzles require you to look several moves ahead, or make lots of good guesses to find a solution.

Unfortunately, the algorithm here does not always create hard puzzles - I don't know how to create a more difficult puzzle on purpose. So in the links below, you may get a hard or an easy puzzle, randomly. The best we can do is tell you what kind of puzzle you've got.

The ratings that go along with the puzzles estimate the amount of guessing (or thinking ahead more than one move) that you might need to do to solve a puzzle. This is done by counting the depth of the search stack when the computer finds a solution. Since, depending on order of the guesses, the search might be deeper or shallower, we try a few different paths and average the search depth to get the rating.

A rating of zero means that you can completely solve the puzzle without any looking ahead or guessing. Ratings of three or more tend to be pretty hard.

Here's the Source Luke

Python code for the Sudoku solver and generator is here. The python script works as both a commandline tool and as a cgi script.

Every time you visit the links below, you should get a fresh, new, never-seen-before Sudoku puzzle. We also print the difficulty of each puzzle so you know what you're getting into before you send it to the printer. Enjoy.

Get a generated Sudoku PDF here.

Get a generated Sudoku in HTML here.

Get a generated Sudoku in plaintext here.

Get a generated Sudoku in Postscript here.

Update: for more printable puzzle fun - I've also put together a 3d printable maze generator here.

Posted by David at September 4, 2006 03:36 AM