How to create a valid sudoku puzzle

xiaolu

It's easy to fill in the 9x9 with say 25 numbers randomly (randomly choose 25 cells out of the 81 cells, and each of the 25 chosen cells filled with one random number between 1 and 9), subject to the condition that the chosen 25 numbers do not break the rule that no number is duplicated on the same row or column on in one of the 9 sub-regions.

Now the questions with what is created so far:

1. Do I guarantee to have a solution (able to fill the remaining empty cells to solve the puzzle), and

2. If yes to the above quesiton, is the solution unique, OR

2. If no to Question #1 above, what else shall I do to make such a partially filled 9x9 a valid puzzle?

Thanks in advance.
James

Moritz · Posted: Sat Oct 28, 2006 3:43 pm Post subject:

Hi,

you have to write a solver and check if
a) a solution exists
and
b) if it is uniq.

If you implement one or two simple solving techniques + backtracking it's fairly efficient.

The easiest way to do it is:
a) if it has no solution, discard this one, and try again
b) if it has multiple solutions, add another hint.

If' implemented that, and it works great. Take a look at
http://moritz.faui2k3.org/en/yasss#generate
There is a discussion about choosing the number of initial hints and some speed considerations.

Cheers,
Moritz
--
http://moritz.faui2k3.org/sudoku

atkman · Posted: Fri Jan 04, 2008 6:36 pm Post subject:

It can take a very long time to generate a sudoku that only has one solution by discarding it if it doesn't have a unique solution (after randomly filling it with numbers). Also adding more hints until there is one unique solution may be the way to go, but doesn't mean it will have a difficulty rating of very hard.

ka1n · Posted: Sat Jan 05, 2008 6:41 am Post subject:

I was just writing a program that generates a pre-solved totally random sudoku board. I decided to take a break and google'd my way here. Here's the algorithm I've come up with so far:

1) Use recursion to create a data structure representing an empty board (e.g. a graph of Node objects)
2) Use recursion that, starting with the root Node... (see 2.x)

2.1) puts incomplete child Node objects into a list
2.2) randomly generates an index into that list (e.g. 0 through list.size)
2.3) uses the random index to select a random available child Node
2.4) inevitably the current Node in the recursion will be a leaf in the graph... (see 2.4.x)

2.4.1) create an array of all available numbers (e.g. 0 through (size * size))
2.4.2) remove those that have already been used by scanning all siblings, and all relatives on north/east/south/west axis
2.4.3) if several available numbers remain, use the random-index'ing technique (same as before) to select one at random

2.5) assign the value discovered in 2.4 to the leaf node
2.6) if the leaf node is complete, mark it as such

Inevitably, the whole sudoku board will be filled -- and every single number will have been chosen at random.

Is there a mathematical proof that determines whether or not a valid sudoku board is generated 100% of the time if built up completely at random?

If so, does this proof hold up if we get rid of the assumption that the number of dimensions goes beyond 3 (e.g. sudoku's 3 dimensions being a cell, its parent (an inner region), and its grandparent (an outer region))?

daj95376 · Posted: Sat Jan 05, 2008 5:40 pm Post subject:

As far as I know, every technique to generate a properly filled grid -- what you're describing -- needs to incorporate backtracking because there aren't any guarantees that an assignment at one point won't force a contradiction to occur later. I'm far from an expert, but this matches my own experiences and it matches what I recall reading in this forum.

However, you've only scratched the surface of creating a valid puzzle. Before long, you'll have to address how to create a puzzle from a filled grid, and how to gauge the difficulty in solving a puzzle once it's generated.

ka1n · Posted: Sat Jan 05, 2008 7:27 pm Post subject:

daj95376 · Posted: Sat Jan 05, 2008 9:05 pm Post subject:

It's possible that your recursion logic will perform the backtracking.

What I didn't see was what happens if steps (2.4.x) fail to find a number to use. Your outline left the impression that step (2.5) would always be passed a number.

coloin · Posted: Thu Jan 17, 2008 1:23 am Post subject:

Icebone1000 · Posted: Fri Jan 18, 2008 5:35 am Post subject:

its possible to create a valid sudoku puzzle by just taking random numbers and random positions, and so check if those are correct, if they are not correct, change it and check all again ?

m_b_metcalf · Posted: Fri Jan 18, 2008 12:42 pm Post subject:

Icebone1000 · Posted: Fri Jan 18, 2008 6:32 pm Post subject:

Icebone1000 · Posted: Fri Jan 18, 2008 7:08 pm Post subject:

you know, its very interestning think about that, if whit 20 numbers it fill the grid in about a half second, whit 81 numbers it dont finish, its like..also the computer will take years to finish the grid?...what a weird thing..

m_b_metcalf · Posted: Fri Jan 18, 2008 7:24 pm Post subject:

rkral · Posted: Fri Jan 18, 2008 7:43 pm Post subject:

Ruud · Site Admin

Mike, 2 questions:

isn't it possible for this deadlock to occur at row 9 as well?

when you generate puzzles for the Patterns Game, are you just generating solutions and overlaying the pattern, or do you use methods to adjust the puzzle when it is unsolvable or not minimal? Having tried the game a few times myself, my generator has a very low yield of usable puzzles using only the random solution + pattern.

Ruud