September 04, 2006Sudoku GeneratorHere 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 commandline Sudoku solver... Update: For Google Chrome users, try installing this Chrome Sudoku Web App for hints and more. Preview the Sudoku Helper here. 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 19 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 nervewracking 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 9square 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 preK 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 3rowband, swapping bands, swapping columns within a 3columnstack, 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 17hint puzzles too, and Gordon's list of 17hint puzzles might be nearly complete. If this could be proved, it would also prove that there are no 16hint puzzles. So if you find a 17hint puzzle, you should check to see if Gordon already has it. And remember that there is no proof that fully determined 16hint puzzles don't exist. If you get a 16hint puzzle out of the automatic puzzle generator, don't throw it out. It would be publicationworthy. 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.
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 mostconstrained 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 fullysolved Sudoku board. To generate Sudoku puzzles, we start with a solved board, and we choose some minimal hints to reveal as follows.
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, neverseenbefore 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. Update: for help with solving sudokus  I have written a javascript Sudoku Puzzle Helper that gives you hints without giving everything away. Posted by David at September 4, 2006 03:36 AMComments
This isn't actually how you solve Sudokus when you're doing them by hand, is it? I have one Sudoku book where the instructions say that the "hard" puzzles require guessing and backtracking, and another one which says "you should never need to guess". The puzzles in the "no guessing" book are still very hard, but I find them much more fun to solve... I suppose the answer is to extend your simple solver to have some more sophisticated strategies before it starts to guess. (and then perhaps the rating could be based on some subjective ranking of the difficulties of the strategies the solver ends up needing to use?) Posted by: David Maymudes at September 4, 2006 01:12 PMYou are right. When you play Sudoku by hand, you basically never guess  instead you try to look ahead and then just write numbers when you are absolutely sure. Maybe it's like a breadthfirst versus a depthfirst search. Even though the computer's depthfirst strategy is plenty fast for solving puzzles, I'm not sure it's the best way to rate the difficulty of a puzzle. There are pretty simple Sudoku strategies that my algorithm does not know. But I am also running into the opposite problem: apparently the algorithm finds it easy to deduce squares (without guessing) that I find it very difficult to locate. I have been stuck on a particular "Level 0" board all morning, wondering where the heck the computer saw a simple deduction. I am not sure why it is so hard for me to see what I am missing. Any ideas on the right way to rate difficulty? Posted by: David at September 4, 2006 01:27 PMI also did a small development in Excel to solve the first part of a puzzle, which is the "guessing" of all possible figures in each cell, following the three basic rules: Nine different figures on each row, column and 3x3 matrix. After that, the real "guessing" process becomes very enjoying and takes much less of our relaxing time per puzzle (5 minutes for an easy puzzle is the average for an average IQ user). The next step is to get an automatic figures generator with difficulty choice inside the worksheet using script, to avoid typing every new puzzle. After reading you article I realized that possibly you have the right solution for my intent. If you accept doing me such please, I would like to send you my worksheet to enable a better understanding of my idea. (Some writings are in Portuguese but I think this will not be a concern). I believe that the worksheet engine (formulas) will be automatically translated to English inside your Excel. Thank you Valerio Posted by: Valerio Deo at September 10, 2006 09:17 PMYou should never need to guess. You can create a true solver in Excel, but as it is an iterative process (which is not Excel's strong suit) it becomes a very intensive application. Better is to set it up in MATLAB. As long as you watch out for the possiblity of an endless loop you can create a solver pretty quickly. Either way, the algorithm goes like this: Repeat these steps enough times and any solvable sudoku will be solved. That is to say, I have not yet found a published puzzle that could not be solved in this manner. Posted by: cosmicfish at November 7, 2006 01:32 PMi didn't see the steps algorithm of saving sudoku thank you Posted by: moon at March 23, 2007 06:41 PMValerio Deo's solution is not quite right. Whey you say "You don't have to guess" you really mean you should not write down guesses. Thinking about what number would fit is nothing but making a lot of guesses in your head and looking whether they will lead to a conflict... Posted by: sky at April 27, 2007 09:57 PMI know a better way to generator: 1. get a valid one like: 2. then randomly switch two lines(row) in a group or switch two big groups. 3. randomly switch all positions for two numbers, like switch all 1 and 2 Now you have a valid solution, you just need to get rid of number from it to create a sudoku. Posted by: Shawn at May 14, 2007 09:23 PMNice programming that you have here. Posted by: Ian Kree at July 2, 2007 10:34 AMThere is another strategy I have found, which I use for hard sudoku's on paper. Once you have worked out all the possibilities for each uncertain cell, look for a (row/column/block) that contains (2/3/4/5/6/7) different possibilities for the same number of cells in that row/column/block. Eliminate ALL of these options from all OTHER cells in that row/column/block. For example, if you have 3 cells in the same row, empty, which have the possibilities of: Hi, can somebody give me an efficient algorithm to develop a Sudoku Software where in a problem is generated automatically and asks player solve it.. Posted by: Ratnesh at November 29, 2007 03:22 AMHi, i need help coding a sudoku generator and solution checker, which also provides a gui that allows the user to input numbers into the puzzle, check their input, and generate a new puzzle at any time, using a neural network and random number generators. Posted by: Zuckerman at December 18, 2007 09:26 PMGood algorithm, David. I wrote a sudoku solver some time back that employs a few techniques: looking for cells with unique candidates, looking for the only position for a value along a row, column, or block. I also added another technique that looks at subcolumns within a block and comparing to other subcolumns. These techniques seemed to be able to solve all the puzzles from local newspapers, but that's only because thos puzzles were pretty simple. I found Stephen Ostermiller's source code (http://ostermiller.org) and realzed there are more techniques. In addition to the ones he implemented, there are others such as Xwing and sword fish, and probably many more. I believe it can probably be proven (or maybe it is already proven) that as long as the solution to a sudoku puzzle is guaranteed to be unique, there must be a logical series of steps that one can take to solve the puzzle. These steps which may include really complex technqiues  even ones that have not even been discovered. Using algorithms that make guesses is probably just a shortcut for not having to develop and implement complex techniques. But if you implement as many of the known techniques as possible, it would help make the generator more likely to generate a harder puzzle. Anyone here that has a Pascal or a C version of this generating algorithm? Cause I don't know Python and I don't understand the code. If you have one, please email me at emma_k89@yahoo.com. And, one more thing: I don't know Java either. I'm pretty young:) Posted by: Emma at May 16, 2008 10:46 AMwell,i think algo from shawn would b the best to generate new random sudoku's........wen u hav nothin.......and solver from david dated 28 dec,2007 is the best 1......but further isn't there any method 2 generate new sudoku's from a blank board.......i tried it this way.....first a generator which puts fixed no of random nos at random positions....follwoing possible conflicts.....then a solver which would solve this......if solver could solve it ...it's a valid sudoku.......else generator is called which generates a new sudoku from scratch.......but this gets quite typical for comp as it does guess work........can't there sum logical sol to this Posted by: sumit at July 13, 2008 04:21 AMGood stuff David, thanks. I wrote an solver in Excel VBA a few years back that employed a few different logical rules. It was pretty effective but could not solve the "brute force" type so recently I wrote a very simple smalltalk version that works very much the same way as your approach. I've been meaning to get around to writing a sudoku generator and this has now inspired me to get on with it! Posted by: Alan at December 15, 2008 07:21 PMDavid  I wrote a solver that uses brute force, not 'logic', based on the fact that there are only 46,656 (9x6x3x6x4x2x3x2) possible patterns of one number in a 9x9 puzzle. Just generate all of them, eliminate those for each number that are not consistent with the positions of that number, then successively merge nonconflicting patterns across numbers. Requires no lookahead/backtracking, just match/eliminate. Has 217 lines of Ruby code, and will solve 'hard' puzzles in about 30 seconds on my 5 year old PC. Posted by: Hal at January 2, 2009 09:07 PMInteresting stuff here. http://www.setbb.com/phpbb/viewtopic.php?t=314&mforum=sudoku Seems like a good thread on generating random sudoku puzzles Posted by: James at February 3, 2009 03:25 AMI have been reading on the subject and from what i have hear you can use the dancing links (DLX) algorithm I have used this to salve the N Queens problem but never sudoku. I think it will work though it uses linked lists. Posted by: Steve at May 7, 2009 05:01 PM"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." Because Sudoku Gridmaster doesn't use an algorithm  all of the puzzles in it are handmade. Having solved many Sudoku puzzles in my lifetime, I can assure you that 400 handmade ones are more fun and artistic than millions of computergenerated ones. :) Posted by: mathgrant at July 16, 2009 11:52 AMI tried out the Dancing Links solution a few years back in Java, and it just didn't scale, and was extremely slow. Dancing Links are useful for enumerating all possible solutions to a problem, not definitely not ideal for finding just one solution. The memory use, even just for a 9x9 puzzle, would balloon to over a gigabyte. Not good ;) Posted by: Shane at August 15, 2009 05:40 AMTo David Bau : Your solution works very nice. I'm a disabled person, former programmer, and I just love Sudoku. I had simply one question : can your code be compiled to a command line utility. Let's say it is called from the command line as SUDOKU.EXE 54453 Where 54453 represent a seed for rabdomizing. And the Sudoku.EXE then exports a textfile (even a textfile with the 81 char's is enough (0 represents a blank place) This way, this could be implemented very easy in no matter what type of application (also in Clipper as I use ...) Many thanks ! Greetings from Belgium Posted by: James Vandenberge at August 24, 2009 05:57 AMHello, I didn't know that there was so much fuss around creating a sudoku puzzle. I have developed SUHelper in www.charalampakis.info during my summer holidays. It is free... it creates random puzzles by rearranging a solved puzzle. I think it is rather fast, although I haven't tested it against other algorithms, nor was it my intention (to create the fastest algorithm). The program has full GUI. It can also try to solve a puzzle with logic (without guessing). Any feedback would be greatly appreciated. Regards Posted by: Aristotelis Charalampakis at September 17, 2009 11:23 AMInteresting... However, I don't believe the method above will generate a valid sudoku puzzle, because it uses best guess to determine if a sudoku is valid. Sudoku puzzles are supposed to be solved with logic, not trial and error. Perhaps forced chaining would be a better approach. I've implemented this in my own code, and it was surprisingly easy. Here's a breakdown of how it works: loop through all unsolved cells, first the ones with 2 possibilities, then 3, then 4, etc. for each possibility in the cell, create a copy of the original solution matrix, and populate that cell in each of the copies with each possibility. eg, if cell A1 can only contain 5, 7 or 9, then make 3 copies, populate A1 in the first copy with 5, 7 in the second copy, and 9 in the third copy. then pass each copy to the solver as if it were a puzzle in its own right. compare the copies, cell by cell. If any cell is set to the same value in all three copies, then that cell must contain that value. Posted by: Simon at September 21, 2009 01:48 PMSimon, The method of rearranging a solved puzzle always produces a valid puzzle. You just randomly swap rows and/or cols (with the necessary adjustments) for a number of times. That's it... Here's the initial puzzle i use: For those looking for an algorithm implemented in a language other than Python  here is the source for a Javascript sudoku engine that can actually also support hinting: http://davidbau.com/sudoku/sudokuengine.js It's part of the hinter at http://davidbau.com/sudoku/ I have written a program in Excel that generates Sudokus. It is very interactive. Posted by: Cavit Aydemir at October 28, 2009 02:39 PMIs there a proven optimum algorithm for generating a Sudoku puzzle? Posted by: elven at January 5, 2010 04:21 AMDear Jort Bloem, I am Akhilesh Godha. I came to know about you from my uncle Narendra Godha. Can you please contact me on my email id. It will be of great help to me. I am currently in Auckland and want to discuss with you. My email: agodha115@yahoo.co.nz Dear members, Sorry for posting this comment as I am seriously searching ways to contact Jort Bloem who has posted a comment in this webpage. Thanks, A simple solution: http://pastebin.com/1LfMVdu3 Posted by: Luis Tomas Wayar at February 26, 2010 11:45 AMJort Bloem described a nice algorithm for getting pretty far in computersolving sudoku without much work. I remember how pleased I was a few years ago when, in writing my solver, I realized that David Bau's two rules here were actually instances of the same rule that Jort Bloem describes. If you have a set of 1 cell with only 1 possible number that could go there, then put the number there. If you have a set of 8 cells which among them have only 8 possible numbers, then the remaining number must go in the remaining cell (this is David Bau's rule 2). Vary that parameter from 1 through 8 and you also get Jort Bloem's rules. These rules don't take into account the interaction between the boxes and the rows/columns that make a sudoku different from a latin square, though; you also need a "boxline" rule of some sort, along the lines of "if all possible locations for a given number in a given line are in the same box, then delete that number from the possibilities for all the remaining cells in that box", and the same thing interchanging line and box. I stumbled on a 2009 Canadian journal paper by Chungen Xu and Weng Xu that describes their work in purposely generating sudokus of a given difficulty. It basically follows the same idea suggested by David Maymudes in the comments above. Here is the link: http://www.ccsenet.org/journal/index.php/jmr/article/viewFile/3718/3313 The most curious thing I think is that their paper directly cites this webpage (the one you are reading now) as a reference. Hooray for the web. Posted by: David at April 14, 2010 09:00 AMthanks for posting, just what i was looking for. Posted by: Sudoku Strategies at May 3, 2010 02:42 AMAre the puzzles that are generated at the given links available for commercial use? Posted by: ClarK Burbidge at June 29, 2010 04:57 PMFor commercial use? No, not at this time. Enjoy them for free; please don't resell them, and thanks for asking. Posted by: David at July 2, 2010 06:07 PMminimum for 6x6?
...they were handwrittencan't use a generator on a ds : Posted by: Bradley W. at August 7, 2010 03:37 AM...they were handwrittencan't use a generator on a ds : Posted by: Bradley W. at August 7, 2010 03:37 AMI'd argue here with two posts: What you say is true: with such a changes your board remains valid. However during the game you can identify patterns which make solving relatively easy. Just take the first column starts with 1 4 7. If you follow the valid transformations (switching columns, rows) you will end up with having these triplets unmodified. (If you see somewhere 1 4 7 you can be sure that if you have a 7 and 4 in some column triplet, then the 3rd one is 1.) If you use the "switch two numbers in all occurrences" rule then you will have the same issue, but different numbers. What do you think? Posted by: LaszloLaszlo at September 4, 2010 02:42 AMFurther thinking on this topic: the problem which i mentioned above is a problem of the starting board. If this board doesn't have such patterns, the result won't have it either. Posted by: LaszloLaszlo at September 4, 2010 03:08 AMAlgorithms like some of the ones being proposed in the comments that require seeding with a valid Sudoku board before they will work ought to be considered cheating. If your algorithm cannot generate a valid Sudoku configuration without prior knowledge of one or more valid Sudoku configuration(s), then it is not a Sudoku generation algorithm. It's just a glorified array permutation algorithm. Posted by: aroth at September 27, 2011 10:27 PMI am using your sudoku generator, but I can't find the files sudokutemplate.pdf/.ps/.txt/.html that you refer to in the comments. Great blog and useful stuff on sudoku and jquery. thanks. poo Posted by: at December 26, 2011 04:36 PMI saw some incorrect statements in the comments stating that all Sudoku boards can be solved by using the row/col/square technique, and I wanted to correct this. In fact the difficulty of a Sudoku puzzle is based on the technique used to solve it, and the above technique provides a definite solution only for easier puzzles. For more about this I found an excellent site: http://www.sudokusolutions.com/background.php Posted by: bcorso at January 5, 2013 11:21 PMDancing links: This is tricky to implement efficiently, but Donald Knuth's own program for it, as well as his frontend for Sudoku puzzles, is available on his website: Only drawback: you need a TeX installation, since the code is (of course) in Knuth's own literate programming language CWeb. The `ctangle` tool supplied with TeX turns it into C. I've found it to be very fast. The output from the dancing links program includes the number of insertions/deletions, which is correlated to the difficulty of the puzzle. @Hal: The magic number is 6^6. There is a symmetric combinatorial interpretation, giving a onetoone mapping between sixdigit base 6 numbers and valid patterns. Think of the grid as three horizontal bands of three rows each and three vertical bands of three columns each, and associate a digit with each band. Choose any valid pattern to be #000000. Use the digits 0 to 5 to encode the permutations of (0,1,2), e.g. To convert a number to a pattern, permute the rows or columns of pattern #000000 within each band according to the permutation encoded by its digit. Post a comment

Copyright 2006 © David Bau. All Rights Reserved. 