Help in Generating 9x9 Sudoku variant

When you have problems solving a Sudoku, ask fellow members to help you
Post Reply
Chocolategirl
New kid on the Grid
New kid on the Grid
Posts: 3
Joined: Wed Sep 13, 2006 5:22 pm
Location: Mauritius

Help in Generating 9x9 Sudoku variant

Post by Chocolategirl »

Hey there

Am wondering whether someone knows :roll:
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 8-)
Always
Smile
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

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
Chocolategirl
New kid on the Grid
New kid on the Grid
Posts: 3
Joined: Wed Sep 13, 2006 5:22 pm
Location: Mauritius

Post by Chocolategirl »

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 :lol:
Always
Smile
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

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
Chocolategirl
New kid on the Grid
New kid on the Grid
Posts: 3
Joined: Wed Sep 13, 2006 5:22 pm
Location: Mauritius

Post by Chocolategirl »

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. :shock:
What is the basic approach when removing clues with respect of creating different level of difficulty. :roll:
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 :wink:
Always
Smile
unkx80
Hooked
Hooked
Posts: 33
Joined: Sat Aug 26, 2006 9:52 am
Location: Singapore

Post by unkx80 »

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

Code: Select all

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: Select all

006200000000004300800035000020000000000000731190000060004053002000700600050082100
Post Reply