Random grids with DLX

brassbandit · Posted: Thu Oct 12, 2006 5:05 pm Post subject: Random grids with DLX

I use DLX to generate and solve Sudokus.

To generate them, I start off with a completely blank grid.

To select a column, the program collects all the columns with the smallest size and chooses one at random (so for the first pass, this could be any of the 324 columns, all with size 9).

My question is - am I restricting the randomness of the grid in anyway, as the first step will always choose the first row in any column? If I left it to run and run, would it (theoretically) generate every single Sudoku solution?

Perhaps, I would be better as a first step to pick a row at random and cover those columns before moving into the dance? What do you think?

Ruud · Site Admin

When you always select the first node in the selected column, your method will certainly be biased. But even when you pick a random node, your method will probably create clusters of given numbers around your first placement.

I use a similar method to create a solution grid (by assigning random numbers to the columns before DLX starts), and then clear random values from this grid until it is fully (or symmetrically) minimal.
_________________
Meet me at sudocue.net

brassbandit · Posted: Thu Oct 12, 2006 8:11 pm Post subject:

I like the idea of the random number with each column.

Presumably that means there are large variances in time taken to find a solution - you might select a column at random with six nodes still attached and may have to go through each of these until a solution is found? That's an extreme case, of course, it could be that a solution is found with no backtracking at all required.

Does your method start at a random row in the column and try them all in turn (until a solution is found)?

Sounds like your method is similar to mine for removing numbers - I randomize the numbers 0 to 80 (or 40 for symmetry) and remove each clue(s) in turn, replacing it if it fails to give a unique solution.

Ruud · Site Admin

brassbandit · Posted: Fri Oct 13, 2006 6:49 am Post subject:

Ah, I see what you're doing now. That's great, and guarantees complete randomness. Thanks.