Generating Sudokus with Dancing Links

GeniXPro

Its the same person in the previous thread, I got my sudoku program to work properly. I'm now investigating a fairly different way to generate sudokus. I'm wondering if anybody has tried this before (most likely someone has), and how its performance compares to other methods of generating sudoukus.

First, I use a modified version of Knuths DLX algorithm on an empty board to generate a random, completed sudoku. Then the algorithm removes numbers randomly, one at a time, while making sure that the sudoku keeps its one unique solution. If it attempts to remove a number and that causes the puzzle to have more than one solution, it replaces that number, and tries to remove another. If it makes three attempts (this number is changable) to remove a number and they all yield the soduku to have more than one solution, the algorithm quits, and there your final soduku lays.

As long as its given more than one attempt to remove a number, then it will generally make a fairly good sudoku with less than one third of givens. I know that the number of givens doesn't affect difficulty all that much, but in general, 30% givens is harder than 99% givens, and this algorithm has an obvious problem where it could remove only 4 or 5 numbers from the completed puzzle and quit. So the number of tries it is given to remove a number will change the number of givens in the resulting puzzle, however, it has only a small impact on the speed.

The method has an advantage of being fairly simple, I implemented it in under 1 1/2 hours.

Heres the speed statistics when the program is compiled with optmizations:

Given 3 tries:
Average 0.230 seconds to generate a sudoku

Given 10 tries
Average 0.310 seconds to generate a sudoku

Given 50 tries:
Average 0.580 seconds to generate a sudoku

Perhaps the algorithm would work better if it would backtrack more than one level if it couldn't make a certain maximum number of givens. However, it would slow the algorithm down considerably if had to solve each time even at a branching factor of 2 or 3.

Its probably already been done, tested, thrown away, but I still want to compare.

Ruud · Site Admin

GeniXPro: Please do not cross-post the same message in different forums.
Replies can be posted in the "programming sudoku" forum.