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   

Efficient generator

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  

Is it an efficient way of doing it?
Yes
25%
 25%  [ 1 ]
No
75%
 75%  [ 3 ]
Total Votes : 4

Author Message
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Wed May 14, 2008 7:10 pm    Post subject: Efficient generator Reply with quote

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

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Sat May 17, 2008 12:59 pm    Post subject: Reply with quote

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

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Sat May 17, 2008 2:37 pm    Post subject: Reply with quote

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

Joined: 05 Mar 2008
Posts: 32
:
Location: Cambodia

Items
PostPosted: Sun May 18, 2008 1:16 am    Post subject: Reply with quote

This is an interesting paper on creating puzzles.

http://www.scanraid.com/Sudoku_Creation_and_Grading.pdf
Back to top
View user's profile Send private message Send e-mail Visit poster's website
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Sun May 18, 2008 6:06 pm    Post subject: Reply with quote

Thanks both of you.

I'll see if i can improve it now. Smile

Mark
Back to top
View user's profile Send private message
mrmarky2

Joined: 13 Jan 2007
Posts: 64
:

Items
PostPosted: Sun May 18, 2008 7:49 pm    Post subject: Reply with quote

Woot Very Happy Very Happy Very Happy
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 Very Happy.

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 Very Happy 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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming 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