Ossudo - ultimage open source sudoku

Saturday, August 26, 2006

Creating a new Sudoku

Creating a new Sudoku is a two step process:
  • First, create a complete 9x9 valid array
  • Then clear cells

Creating a complete valid array

Creating a correct full array is not that difficult. You start at upper left corner, set a value at random, move on to the next cell, see what values are still allowed, chose one at random and proceed.

Of course, as you move on, there are fewer and fewer possible values. Every time you set one cell, you must update possible values for rows, columns, blocs, and finally for individual cells.

So you move on this way, picking values at random, among those that remain available. At some points you get into a deadend, where there are no candidates left for a given cell. This usually occurs when you reach row 5 or 6.

At this point, you need to track back and start again. My algorithm makes a simple assumption, which I have not proved, but turns out to never fail: going back at the last complete bloc level row will allways get you out of deadends. This means if you encounter a deadend at row 6 for instance, you go back to row 4 (because row 4 is the beginning of the second bloc-row, row of 3x3 blocs), if you have reached row 7 and hit a deadend, then you start over at row 7 only (because row 7 is the beginning of the third bloc-row).

Well, this seems to work and is quite faster and also simpler then a real track-back trial-and-error algorithm.

Clearing cells towards a playable Sudoku

So once you have built a complete array, you start clearing cells.

A good Sudoku should have as many empty cells as possible. This means it is not possible to clear any one cell without getting a invalid Sudoku, one with more than a single solution.

It is definitely wrong to believe a difficult Sudoku is one with a lot of empty cells, and an easy Sudoku is one with not-too-many empty cells. It has nothing to do with empty cells. A Sudoku where more cells could be cleared is not a good Sudoku, although it's of course not as bad as one that would have two solutions.

0 Comments:

Post a Comment

Links to this post:

Create a Link

<< Home