View previous topic :: View next topic 
Author 
Message 
 xiaolu
 Joined: 17 Oct 2006  Posts: 1  :   Items 

Posted: Tue Oct 17, 2006 7:59 pm Post subject: How to create a valid sudoku puzzle 


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 subregions.
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 

Back to top 


 Moritz
 Joined: 07 Oct 2006  Posts: 23  :  Location: Edinburgh, Scotland  Items 

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 

Back to top 


 atkman
 Joined: 04 Jan 2008  Posts: 4  :   Items 

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. 

Back to top 


 ka1n
 Joined: 05 Jan 2008  Posts: 3  :   Items 

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


I was just writing a program that generates a presolved 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 randomindex'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))? 

Back to top 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

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. 

Back to top 


 ka1n
 Joined: 05 Jan 2008  Posts: 3  :   Items 

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


daj95376 wrote:  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. 
Can you explain what you meant by "backtracking"? I believe my algorithm took that into account.
Also, I did not understand when you said "create a puzzle from a filled grid". Again, the way I interpret this is also considered in the algorithm. So, I think I misunderstood.
Finally, it seems to me that difficulty  unless in the trivial sense of how many cells are initially filled  is subjective.
If you could point me to or explain an algorithm that describes what you're saying I would really appreciate it. 

Back to top 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

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. 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

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


Code:  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? 
Yes
Most sudoku grid solution generators are biased to extent.
See here
Streams of "random" minimal puzzles can be generated  from this valid solution grids can be generated.
The grids may have a small bias in the number of small unavoidable sets.
Here is an unavoidable set [U4].
In a puzzle with this pattern one of these clues must be in the original puzzle........without one of these clues there are two grid solutions.
Code:  ++++
12.......
.........
.........
++++
21.......
.........
.........
++++
.........
.........
.........
++++
++++
127356489
438729516
569814237
++++
213675894
874931652
695248371
++++
741563928
382497165
956182743
++++
or
++++
217356489
438729516
569814237
++++
123675894
874931652
695248371
++++
741563928
382497165
956182743
++++ 
http://www.setbb.com/phpbb/viewtopic.php?t=121&mforum=sudoku
might also help
C 

Back to top 


 Icebone1000
 Joined: 18 Jan 2008  Posts: 3  :   Items 

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 ? 

Back to top 


 m_b_metcalf
 Joined: 13 Mar 2006  Posts: 210  :  Location: Berlin  Items 

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


Icebone1000 wrote:  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 ? 
That's almost what I do:
1. set row 1 to the digits 1 to 9 in random order;
2. set the next row to the digits 1 to 9 in random order;
3. where necessary, shuffle the digits in the row to conform to the box/column constraints;
4. repeat at 2. until row 8;
5. row 9 has only one possible arrangement.
There is a deadlock possibility at row 6 that as to be dealt with; otherwise, this is fast and unbiased.
Regards,
Mike Metccalf 

Back to top 


 Icebone1000
 Joined: 18 Jan 2008  Posts: 3  :   Items 

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


m_b_metcalf wrote:  Icebone1000 wrote:  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 ? 
That's almost what I do:
1. set row 1 to the digits 1 to 9 in random order;
2. set the next row to the digits 1 to 9 in random order;
3. where necessary, shuffle the digits in the row to conform to the box/column constraints;
4. repeat at 2. until row 8;
5. row 9 has only one possible arrangement.
There is a deadlock possibility at row 6 that as to be dealt with; otherwise, this is fast and unbiased.
Regards,
Mike Metccalf 
why theres a deadlock at row 6?..
what i was tring to do is to take all 81 (19) numbers and put they in random positions, so check the sudoku rules, if theres a repeated number(in a block or in a row), change that number, and recheck all again..
this was working whit just 20 numbers..but now whit all 81 numbers it get stuck in the check loop...
the most weird, is that it didnt stuck in the same place every time, i think its cause it have to check so many times , and rechek every time a number changes, then the loop becames like unlimited, it get stucked cause it cant complete the grid until the end, it will do forever...
im not sure if that is what are happening...
the reason for what i want do this, its cause i didnt notice that doesnt matter if the 20 numbers are ok whit the sudoku rules, it still can be impossible to complete. so i noticed, and now i want all 81 numbers (cause whit that it will have at least one possibility) and show just 20 of those 81. 

Back to top 


 Icebone1000
 Joined: 18 Jan 2008  Posts: 3  :   Items 

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.. 

Back to top 


 m_b_metcalf
 Joined: 13 Mar 2006  Posts: 210  :  Location: Berlin  Items 

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


Icebone1000 wrote: 
why there's a deadlock at row 6?..

You have the following configuration in about 10% of the cases: Code: 
1 x x 
2 x x 
3 x x 
+
4 5 6 
7 8 9 
? 
Now no digit can be placed where the ? is. Note that by working with rows rather than cells, the row constraint is always fulfilled.
Regards,
Mike Metcalf 

Back to top 


 rkral
 Joined: 21 Oct 2005  Posts: 233  :   Items 

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


m_b_metcalf wrote:  Icebone1000 wrote:  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 ? 
That's almost what I do:
1. set row 1 to the digits 1 to 9 in random order;
2. set the next row to the digits 1 to 9 in random order;
[...] 
Since you're constructing a grid (a solution rather than a puzzle), how would random selection of rookeries compare to random selection of individual clues? Would it be faster or slower? Any difference in bias? 

Back to top 


 Ruud Site Admin
 Joined: 17 Sep 2005  Posts: 708  :  Location: Netherlands  Items 

Posted: Fri Jan 18, 2008 8:10 pm Post subject: 


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 

Back to top 


