View previous topic :: View next topic |
Author |
Message |
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Sun Mar 05, 2006 11:45 am Post subject: Filled Grid Generator |
|
|
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 |
|
|
| Soultaker
| Joined: 28 Feb 2006 | Posts: 49 | : | | Items |
|
Posted: Sun Mar 05, 2006 1:41 pm Post subject: |
|
|
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 |
|
|
| LotusBG
| Joined: 25 May 2006 | Posts: 2 | : | | Items |
|
Posted: Fri May 26, 2006 11:24 am Post subject: sodoku generator |
|
|
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 |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Fri May 26, 2006 12:48 pm Post subject: Re: sodoku generator |
|
|
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 |
|
|
|