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   

Filled Grid Generator

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sun Mar 05, 2006 11:45 am    Post subject: Filled Grid Generator Reply with quote

As a first project, I wrote a modest generator that creates filled grids.

Does anyone have or know of a program that will take a filled grid as input and produce a puzzle from it?

Thanks!
Back to top
View user's profile Send private message
Soultaker

Joined: 28 Feb 2006
Posts: 49
:

Items
PostPosted: Sun Mar 05, 2006 1:41 pm    Post subject: Reply with quote

Yes, I used this method as well. To generate a puzzle you will need a solver. A simple way to generate a puzzle from a grid is then is to remove a random symbol and see if it the solution is still unique; if not, put it back. If you can not remove any more symbols the grid is (locally) minimal.

If you care especially about the number of clues, you could add a backtracking step, so you can backtrack when you reach a minimal grid that has to many clues for your taste.

The advantage of starting from a filled-in grid is that backtracking solvers are slow when the grid is empty but fast when it's nearly full, so generating the puzzle will be faster. Starting from an empty grid is particularly useful with a logic-based solver, because it can fill in part of the grid and then let you pick another hint to add. Backtracking solvers are usually unable to fill in only the part of the grid that can be deduced from the hints; they find complete solutions or nothing.

So, which puzzle generation algorithm is best depends largely on the solver you are going to use.
Back to top
View user's profile Send private message MSN Messenger
LotusBG

Joined: 25 May 2006
Posts: 2
:

Items
PostPosted: Fri May 26, 2006 11:24 am    Post subject: sodoku generator Reply with quote

So you developed a program that fills a 9x9 with nubers according to the SoDoKu rules? What language did you program it in? If it's C++ would you be willing to share the code because I have to do that as a school project.
THX
LOTUS
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Fri May 26, 2006 12:48 pm    Post subject: Re: sodoku generator Reply with quote

there is another way to use a full grid to generate
generate the full grid and save it
then start with an empty grid and only fill in values from the full grid
this way you know any placement made is correct except for
knowing when enough clues have been added for unique solution
if symmetry is desired then make symmetric placements from the start

the backtrack solver is ok for the unique solution test
just tune it to bail when it finds a second solution and
don't even try with < 17 clues unless you are feeling very lucky
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
Page 1 of 1

 
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