SudoCue Users Forum Index SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Help in Generating 9x9 Sudoku variant

 
Post new topic   Reply to topic    SudoCue Users Forum Index -> Help Me! I'm stuck!
View previous topic :: View next topic  
Author Message
Chocolategirl
New kid on the Grid
New kid on the Grid


Joined: 13 Sep 2006
Posts: 3
Location: Mauritius

PostPosted: Wed Sep 13, 2006 5:37 pm    Post subject: Help in Generating 9x9 Sudoku variant Reply with quote

Hey there

Am wondering whether someone knows Rolling Eyes
if there exits a particular approach (technique)to generate 9x9 Sudoku variant puzzles of different level of different.
And what is the idea adopted when making various the sysmetry of puzzles of different level
Plz this is a urgent request for guide Cool
_________________
Always
Smile
Back to top
View user's profile Send private message
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Wed Sep 13, 2006 6:23 pm    Post subject: Reply with quote

Hi,

welcome to the forum.


There is no method to make a sudoku or variant with an exact difficulty level.

Most programmers use the alternative: Use a fast method to generate a random puzzle and test its difficulty. Repeat this until you find the correct difficulty level.

The fast generation method works like this:

1. Create a completed grid that complies with the rules.
2. Remove a number (or 2, 4 or 8 numbers in you want to use symmetry)
3. Solve the puzzle with a fast backtracking solver.
4. Repeat until the puzzle cannot be solved, restore the last numbers removed in step 2.
5. Test the difficulty.
- too easy? Restart with step 1.
- too difficult? Add a number (or more for symmetry) and repeat step 5.
- just right? Finished.

For symmetry, create pairs or groups of cells. For instance, 180 degrees rotational symmetry uses pairs 1-81, 2-80, 3-79, .... 40-42 and a single cell 41.
When you clear cell 1, also clear cell 81. When you restore cell 1, also restore cell 81.

Hope this helps,

Ruud
_________________
“If the human brain were so simple that we could understand it, we would be so simple that we couldn't.” - Emerson M Pugh
Back to top
View user's profile Send private message Send e-mail
Chocolategirl
New kid on the Grid
New kid on the Grid


Joined: 13 Sep 2006
Posts: 3
Location: Mauritius

PostPosted: Thu Sep 14, 2006 1:30 pm    Post subject: Reply with quote

Hi
thank you for ur quick reply Mr Ruud Wink

Right now am working on sudoku generator for my final project for BSc in Information System
If anyone has related articles concerning on the generating of a 9*9 sudoku puzzles
plz do post me their links.
thanks you once again Laughing
_________________
Always
Smile
Back to top
View user's profile Send private message
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Thu Sep 14, 2006 2:21 pm    Post subject: Reply with quote

You can find a lot more info here: http://www.setbb.com/sudoku/viewforum.php?f=2

Ruud
_________________
“If the human brain were so simple that we could understand it, we would be so simple that we couldn't.” - Emerson M Pugh
Back to top
View user's profile Send private message Send e-mail
Chocolategirl
New kid on the Grid
New kid on the Grid


Joined: 13 Sep 2006
Posts: 3
Location: Mauritius

PostPosted: Fri Sep 22, 2006 7:18 am    Post subject: Reply with quote

7 5 6 9 8 3 1 4 2
8 9 3 2 4 1 6 7 5
4 2 1 5 7 6 3 8 9
2 1 4 3 9 8 7 5 6
9 3 8 6 5 7 4 2 1
5 6 7 1 2 4 8 9 3
3 8 9 4 1 2 5 6 7
6 7 5 8 3 9 2 1 4
1 4 2 7 6 5 9 3 8

Could you plz tell the step you undergo to remove the clues from this filled solution. Shocked
What is the basic approach when removing clues with respect of creating different level of difficulty. Rolling Eyes
It is said that the level of difficulty is not dependent on the number of givens available but instead on how the given are placed that makes the puzzle challenging to solve.To what extend is that true Question
Moreover some says that number of backtracking on a particular puzzle determine it's level of difficult.
But contraint to that there are some solver that mimic the human logic to determine the level of difficulty.
Which is the best to dertermine the level of difficulty and what particular concern do i must adopt while generating the puzzles.

Thank you for your most welcoming suggestion Wink
_________________
Always
Smile
Back to top
View user's profile Send private message
unkx80
Hooked
Hooked


Joined: 26 Aug 2006
Posts: 33
Location: Singapore

PostPosted: Wed Sep 27, 2006 1:52 am    Post subject: Reply with quote

For your reference, this is part of the algorithm I use to generate my own sudokus:

Code:

generate_sudoku(grid)
    if grid has no solution  // 1
        return false
    if grid has exactly one solution  // 2
        return true
    select a random empty square s in grid
    for i = 1 to 9  // 3
        assign square s in grid with value i
            if generate_square(grid)
                return true
    return false


Call generate_sudoku() with an empty grid.

A few points:
1. As to how to find out how many solutions a grid has (marked with 1 and 2), its simple recursion and a person doing a BSc in Information Systems should know how to do it.
2. For better randomness of values, the loop marked with 3 can be modified, I also leave it to you to figure this out.
3. The grid generated by generate_sudoku() is 99% of the time not minimal. I leave it to you to figure out how to make it minimal. On average, after making it minimal, my generator creates a grid with 20+ clues.
4. There are no gurantees as to how easy or difficult the generated sudoku is. It can be terribly easy, it can be terribly hard.

Just for fun, this is one of the hardest sudokus that is generated by my generator. To solve it, you need very advanced techniques. SudoCue uses a couple of almost locked sets and one 3D Medusa colouring to solve it. I have yet to figure out how to interpret the colours shown by SudoCue for the 3D Medusa technique though.
Code:
006200000000004300800035000020000000000000731190000060004053002000700600050082100
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    SudoCue Users Forum Index -> Help Me! I'm stuck! 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


Powered by phpBB © 2001, 2005 phpBB Group