Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

How to create a valid sudoku puzzle
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
xiaolu

Joined: 17 Oct 2006
Posts: 1
:

Items
PostPosted: Tue Oct 17, 2006 7:59 pm    Post subject: How to create a valid sudoku puzzle Reply with quote

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
Back to top
View user's profile Send private message
Moritz

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

Items
PostPosted: Sat Oct 28, 2006 3:43 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
atkman

Joined: 04 Jan 2008
Posts: 4
:

Items
PostPosted: Fri Jan 04, 2008 6:36 pm    Post subject: Reply with quote

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
View user's profile Send private message
ka1n

Joined: 05 Jan 2008
Posts: 3
:

Items
PostPosted: Sat Jan 05, 2008 6:41 am    Post subject: Reply with quote

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))?
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Jan 05, 2008 5:40 pm    Post subject: Reply with quote

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
View user's profile Send private message
ka1n

Joined: 05 Jan 2008
Posts: 3
:

Items
PostPosted: Sat Jan 05, 2008 7:27 pm    Post subject: Reply with quote

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
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Jan 05, 2008 9:05 pm    Post subject: Reply with quote

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
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Thu Jan 17, 2008 1:23 am    Post subject: Reply with quote

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

+---+---+---+
|127|356|489|
|438|729|516|
|569|814|237|
+---+---+---+
|213|675|894|
|874|931|652|
|695|248|371|
+---+---+---+
|741|563|928|
|382|497|165|
|956|182|743|
+---+---+---+

or

+---+---+---+
|217|356|489|
|438|729|516|
|569|814|237|
+---+---+---+
|123|675|894|
|874|931|652|
|695|248|371|
+---+---+---+
|741|563|928|
|382|497|165|
|956|182|743|
+---+---+---+


http://www.setbb.com/phpbb/viewtopic.php?t=121&mforum=sudoku

might also help

C
Back to top
View user's profile Send private message
Icebone1000

Joined: 18 Jan 2008
Posts: 3
:

Items
PostPosted: Fri Jan 18, 2008 5:35 am    Post subject: Reply with quote

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
View user's profile Send private message MSN Messenger
m_b_metcalf

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

Items
PostPosted: Fri Jan 18, 2008 12:42 pm    Post subject: Reply with quote

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
View user's profile Send private message
Icebone1000

Joined: 18 Jan 2008
Posts: 3
:

Items
PostPosted: Fri Jan 18, 2008 6:32 pm    Post subject: Reply with quote

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 (1-9) 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 re-check 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 re-chek 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
View user's profile Send private message MSN Messenger
Icebone1000

Joined: 18 Jan 2008
Posts: 3
:

Items
PostPosted: Fri Jan 18, 2008 7:08 pm    Post subject: Reply with quote

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
View user's profile Send private message MSN Messenger
m_b_metcalf

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

Items
PostPosted: Fri Jan 18, 2008 7:24 pm    Post subject: Reply with quote

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
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Fri Jan 18, 2008 7:43 pm    Post subject: Reply with quote

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
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Jan 18, 2008 8:10 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron