View previous topic :: View next topic |
Is it an efficient way of doing it? |
Yes |
|
25% |
[ 1 ] |
No |
|
75% |
[ 3 ] |
|
Total Votes : 4 |
|
Author |
Message |
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Wed May 14, 2008 7:10 pm Post subject: Efficient generator |
|
|
I have been told a way of generating sudoku:
1. Fill a grid with random numbers
2. Delete cells until you have a good sudoku puzzle
I still need a little help to make an efficient generator
I already have it filling a grid with random numbers..
But, then is this the best way of doing step two?
Delete 46 random clues. (Giving you 35 clues now on the board)
If not solvable:
> Put the clues back and delete 46 random clues until it is solvable.
> Delete another clue
> Check to see if it solves still.
> Repeat until no more can be deleted and you have your puzzle.
Is this the best easy way to do it?
Thanks
Mark |
|
Back to top |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Sat May 17, 2008 12:59 pm Post subject: |
|
|
Quote: |
Construction of a sudoku is fairly straightforward when a fast solver program is available: Start with an empty grid. Fill in candidate clues one by one, either randomly or according to some design rule. If a candidate leads to an illegal puzzle, discard it and try a different candidate. When the set of clues (or givens) define a valid puzzle, that is a puzzle with exactly one solution, the process is finished. This process will always result in a valid puzzle. However, the puzzles found may not have the desired qualities, where quality means anything like difficulty level, pattern symmetry, number of given clues, minimality, etc. In order to achieve a certain quality, it is often possible to improve the puzzle. Alternatively, just make new ones until the quality is satisfactory.
|
Quote from wikipedia.
This is basically what im doing, but instead of filling in numbers, I generate a solution and delete to a certain amount of numbers. This means that I have a valid sudoku to start with, then I check each cell in a random order. Delete it, if it solves still I delete another. Until I have tried every clue to get the best possible puzzle. If I come across a clue that when i delete it, it wont solve I put it back and don't use it again.
But this takes a long time to generate puzzles.
How does everyone else generate puzzles?
Thanks
Mark |
|
Back to top |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Sat May 17, 2008 2:37 pm Post subject: |
|
|
I start with an empty grid. Fill in candidate clues one by one according to a predefined pattern. If a candidate leads to an illegal puzzle, discard it and try a different candidate. When the set of clues (or givens) define a valid puzzle, that is a puzzle with exactly one solution, the process is finished.
That's the way it is implemented in my Soduku Generator _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
Back to top |
|
|
| Sisophon2001
| Joined: 05 Mar 2008 | Posts: 32 | : | Location: Cambodia | Items |
|
|
Back to top |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Sun May 18, 2008 6:06 pm Post subject: |
|
|
Thanks both of you.
I'll see if i can improve it now.
Mark |
|
Back to top |
|
|
| mrmarky2
| Joined: 13 Jan 2007 | Posts: 64 | : | | Items |
|
Posted: Sun May 18, 2008 7:49 pm Post subject: |
|
|
Woot
My program is actually a proper exe file, and was originally a solver. The actual program runs slow at the minute because each little pencilmark and each cell is a picture. I'm about to change this to one big image to improve the speed of the program.
At each stage of the generator I made it output what it was doing on the images. So when I made it generate a randomly filled grid, I made it show me on my pictures what it had done, so I could see each stage and where my code wasn't working.
I was complaining about the speed of the generator because I thought my code was inefficient, actually I never new how much my generator was being slown down by outputing each stage on the pictures.
Now that I have changed that, even the very hard puzzles are generating in seconds .
Thanks for your help.
Heres some puzzles I've generated.
I haven't introduced symmetry into my program yet:
Code: | 1...4....
.6..5.7.8
..9....5.
9.34.....
.....8.9.
.....32.4
.7.....8.
...3..1..
...6.7..2 |
Code: | .....94..
...3579.2
7....6..1
3.7......
..9....4.
52.14....
..267.5..
8.....3..
.....4..7 |
Code: | .241...5.
....4.3..
67.......
7....48.3
...8.....
..6.2..9.
9.5.3.1..
8..5..6..
1.....98.
|
Code: | 8..3.5..7
..6......
.....6..8
..2...4.6
.3.5...8.
.....4..2
723.....9
.9.1.....
1....7.5. |
Code: | ........2
...65...3
3.72.....
1.....4..
.5.8.1...
..4.3.5..
.4...9.6.
.35.1..9.
.8...6... |
These are my top difficulty, which took more than 10 minutes to generate before, I got fed up and terminated the program after that. Now its about 5 seconds hardest techniques are up to X wing, everything below on this page is in my generator. http://www.sudocue.net/guide.php#NakedSingle
All of the puzzles above should have 1 solution and have at least one of these 5 techniques: Hidden Pairs, Naked Quads, Hidden triples and Quads, X wing. |
|
Back to top |
|
|
|