Creating Sudoku puzzles

May 27, 2005 2:37 AM

I know the theory of solving Sudoku puzzles but I'd like to know how you would go about creating them.

I've found a lot of sites on the web that tell you how to solve Sudoku puzzles and even a site and an excel macro (link sadly lost) which will do just that automatically.

However I'm more interested in understanding the logic required for creating your own so that I can write something myself to generate them. Does anyone know where I can find such information?

I'm especially interested in how you go about generating the board and then which numbers you remove to get the puzzle to a pre-defined level of difficulty.

posted by ralawrence to sports, hobbies, & recreation (7 comments total)

This is an example of a little app which does what you wish to do, with three levels of difficulty.

Not sure if Dave Easton the writer gives any insight into its development anywhere on the web, will give a quick look....
posted by kenaman at 2:53 AM on May 27, 2005

Sudoku Programmers BB might help also..
posted by kenaman at 2:56 AM on May 27, 2005

Dave Easton's generator looks good but I'm having difficulty finding a contact email for him. There is nothing on his site and google doesn't seem to help.

The BB is also good but doesn't give too many details. For example, they advocate starting with a blank grid and then placing numbers and testing the solvability but that looks to be very hit and miss and intensive. The other way appears to be to start with a full grid and "roll back", which is one way, but I can't seem to find out how to generate the full grid in the first place!
posted by ralawrence at 5:23 AM on May 27, 2005

Here's a step-by-step guide. Interestingly enough, it doesn't start with a full grid. No real way to judge the difficulty of the puzzle (aside from how many cells you reveal), but this solver should help you get some idea of how hard it is (and whether it can be solved!).
posted by gleuschk at 6:33 AM on May 27, 2005

Oh, also, on how to generate a full grid. There's one obvious ("canonical") full grid:

123 456 789
456 789 123
789 123 456

234 567 891
567 891 234
891 234 567

345 678 912
678 912 345
912 345 678

and there are some obvious group actions: copies of Z/3Z can permute
(1) rows within each band
(2) columns within each band
(3) the horizontal bands, and
(4) the vertical bands

Furthermore, a copy of S_9 permutes the numbers, and Z/2Z acts by the transpose. I conjecture that the orbit of the canonical grid under these group actions is the entire set of full grids. My next step is to find a combinatorialist who'll count them all for me and see if there's any chance I'm right.
posted by gleuschk at 6:40 AM on May 27, 2005

Hm, more on the combinatorics, including an assertion that there are 6,670,903,752,021,072,936,960 valid full grids, a factor of about a trillion more than I thought. Oh well. Won't get tenure that way.
posted by gleuschk at 6:47 AM on May 27, 2005

and of course I meant S_3 instead of Z/3Z. I am so ashamed.
posted by gleuschk at 9:38 AM on May 27, 2005