Giulio Zambon's Website
Puzzles - Sudoku Classic

Writing a program to generate valid completed sudokus is not too hard. You can fill a Sudoku grid by 'sprinkling' one digit at a time in pseudorandom positions, while taking care that there are no repetitions in any row, column or box. If you reach a situation where this is not possible, to keep the algorithm simple, you restart from scratch.

To generate a Sudoku puzzle from a completed Sudoku is the tricky part. You have to remove clues, but when do you stop? If you remove too few clues, all your puzzles will be of the trivial type. On the other hand, if you remove too many clues, you will create Sudoku puzzles that admit more than one solution. The only way to solve this conundrum is to check that the solution remains unique after removing each clue. But that is easier said than done...

In any case, how difficult is the puzzle that you have generated? And, most importantly, is your new puzzle solvable with analytical/logical strategies or does it require guessing?

The only way I have found to determine the level of difficulty of a puzzle is to solve it and note down how complex were the strategies I needed to use. This is obviously not an exact science, because it will make me discard puzzles that, while they are analytically solvable, they require strategies that I don't know or I find too difficult to apply.

But with a program that implements all possible strategies, from the easiest to the most difficult, I will be able to grade the difficulty of all puzzles.

Now, writing a program to solve Sudokus is not too hard if all you want to achieve is finding a solution. You only need to implement a brute-force strategy, in which you try all possible candidates of each cell, keep going as long as the choice of each new candidate doesn't introduce conflicts, and backtrack when you run out of alternatives.

But to grade the difficulty of a puzzle you need to make the computer apply solving strategies based on logic, and that is far from trivial. Moreover, you need to classify the complexity of each strategy and keep applying the easier ones to solve as many cells as possible, before resorting to more complex strategies. Otherwise, if you used complex strategies at once, you would overestimate the difficulty of the puzzles.

The bottom line of all these considerations is that, in order to generate valid Sudoku puzzles that admit single solutions and of known difficulty, a program needs to do quite a bit of work.

That's why, once I managed to write programs to solve and generate Sudoku puzzles to my satisfaction, I decided to write a book about them (see Sudoku Programming).

Here are some examples of the puzzles I generated

Diamond Sudoku   Heart Sudoku   Cross Sudoku   Smiley Sudoku

Cute, aren't they? Obviously, I can also generate traditional puzzles.

Concerning the difficulty of the puzzles, I can generate puzzles from easy to diabolical. The most difficult puzzle I have so far generated required the repeated application of eight different strategies, including three very complex ones. In total, the Solver had to apply a sequence of seventeen strategies.

If you need custom-made Sudoku puzzles for any occasion, don't hesitate to contact me at the email address that you find on the home page.

Valid XHTML 1.0!   Valid CSS!