View previous topic :: View next topic 
Author 
Message 
Chocolategirl New kid on the Grid
Joined: 13 Sep 2006 Posts: 3 Location: Mauritius

Posted: Wed Sep 13, 2006 5:37 pm Post subject: Help in Generating 9x9 Sudoku variant 


Hey there
Am wondering whether someone knows
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 _________________ Always
Smile 

Back to top 


Ruud Site Owner
Joined: 30 Dec 2005 Posts: 601

Posted: Wed Sep 13, 2006 6:23 pm Post subject: 


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 181, 280, 379, .... 4042 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 


Chocolategirl New kid on the Grid
Joined: 13 Sep 2006 Posts: 3 Location: Mauritius

Posted: Thu Sep 14, 2006 1:30 pm Post subject: 


Hi
thank you for ur quick reply Mr Ruud
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 _________________ Always
Smile 

Back to top 


Ruud Site Owner
Joined: 30 Dec 2005 Posts: 601

Posted: Thu Sep 14, 2006 2:21 pm Post subject: 


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 


Chocolategirl New kid on the Grid
Joined: 13 Sep 2006 Posts: 3 Location: Mauritius

Posted: Fri Sep 22, 2006 7:18 am Post subject: 


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.
What is the basic approach when removing clues with respect of creating different level of difficulty.
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
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 _________________ Always
Smile 

Back to top 


unkx80 Hooked
Joined: 26 Aug 2006 Posts: 33 Location: Singapore

Posted: Wed Sep 27, 2006 1:52 am Post subject: 


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 


