What is the best way to create a Sudoku?

briturner

Greetings,

I got some time to build a Sudoku generator, but I am not very happy with my results. I set my solver to generate 1,000,000 puzzles, but the quality of the puzzles is very heavily slanted towards easy puzzles.

I judge my puzzles based on solving time, and rate very easy puzzles as puzzles that take under 20 usec to solve. My first pass generator created 98.36% easy puzzles, compared to Zerothbase's 35.59%. I added a test to remove any given not needed, but was still hitting 71.52% easy. So, for generating complex puzzles, Zerothbase's method looks twice as good as mine, if not better, though I do not know how quickly his runs.

I am thinking of 3 obvious methods to generate puzzles:

1) start with a given random completed sudoku, and remove cells randomly verifying it still produces a unique sudoku. At some point, check each remaining cell to see if it can be removed.

2) start with a desired random completed sudoku, and add givens based on the desired final solution, until a unique solution is achieved.

3) start randomly placing cells, and solve for uniqueness. If the puzzle has no solution, go back, if multiple solutions, add another cell.

I implemented method 3, and can generate many puzzles quickly (1,000,000 sudokus with unique solutions in 9.4 minutes). I then added a check to see if each given cell could be removed, which increased the time to 21 minutes per million.

So, my question is, what method do people use, and method works best for making difficult puzzles? Please feel free to add better methods.

Thanks
Brit

zerothbase · Posted: Sun Nov 30, 2008 2:16 am Post subject:

I'll give you my method in detail:

1) Generate a filled solution grid.

I use a simple backtracking "solver" on a blank grid. I iterate over the squares 0 to 80, and at each square, I choose a random value of the possibilities to put in that square. If no possibilities, then backtrack. This is very fast - I can generate ~100,000 solutions per second this way.

Lunatic · Posted: Sun Nov 30, 2008 8:17 am Post subject:

Step 1: Generate a random solution by simply using backtracking brute force on all cells. I only randomly change the order of the cells before starting the brute force.

Step 2: Remove as much cells as possible from the solution, while checking on unique solution for each cell removed. If multiple solutions, replace that cell and try next cell until all cells are tried. Again, i randomly change the order of the cells before removing.

Depending on the type of sudoku you want (horizontal mirroring, vertical mirroring, diagonal, anti-diagonal, 90° rotational, 180° rotational, or whatever..., you can remove cells in pairs or quads (and replace them if multiple solutions).

Click here to view sample c-code.

On the other hand i've made a pattern based generator too. In that case, clues are randomly generated for a given pattern, and tested if the generated clues leads to a unique solution.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

gsf · Posted: Sun Nov 30, 2008 1:20 pm Post subject:

briturner · Posted: Sun Nov 30, 2008 7:10 pm Post subject:

I found this post by George Marsaglia at http://www.bobwheeler.com/statistics/Password/MarsagliaPost.txt. It provides a few different random number generators.

I use the combination multiply-with-carry, 3-shift-register, congruential generator.

Here is the main lines of the generator, but the link provides more information:

m_b_metcalf

m_b_metcalf · Posted: Tue Jan 13, 2009 9:58 am Post subject:

zerothbase · Posted: Sat Jan 17, 2009 6:53 am Post subject:

The later.

Each puzzle starts from a blank grid and uses the first solution found as its solution grid.

--zerothbase

briturner · Posted: Sat Jan 17, 2009 2:30 pm Post subject:

Greetings,

I have been trying to generate hard puzzles, but I have to admit, I and not in the same league as the big boys on the players forum yet. My top score so far is around 98423 Q2 rating.

I am on my 3rd generation method. Here are the 3 I tried:

1) pick a random cell, place a random number, then pick another random spot and place another random number. Continue until you have a unique solution, then minimize. I later altered my solver to indicate which cells were different in multiple solutions, so I would not randomly pick a cell that was already set.
Pros - fast, simple
Cons - while you could theoretically generate any puzzle, and thus hard ones, I did not generate a single difficult puzzle out of millions of puzzles.

2) started with a filled grid, added in 3 cells from each box such that no 2 were on the same row or column. If needed, added more to make the solution uniqu
Pros - still very fast, and generated harder puzzles then complete randomness
Cons - Still no real hard puzzles

3) started with a predefined set, in this case I set the corner 4 boxes with 123 123 on the diagonal and 456 456 in the boxes next to them. Then placed a single number the remaining boxes and completely filled in the last box. If I have a unique solution, I minimize it. I then iterated around variations on this puzzle.
Pros - Much harder puzzles generated (over 1000 with 95000+ Q2 rating)
Cons - very time consuming. been running for days now, and probably another week just to finish this variation.

So, puzzle generation is now running as a background task, and I just let it run. I already have new patterns as a baseline for the next run.

brit

gsf · Posted: Sat Jan 17, 2009 4:44 pm Post subject:

lkSudoku · Posted: Thu May 21, 2009 4:31 pm Post subject:

My generator chooses difficulty by trying to solve the puzzle with different methods without backtracking. If you create a solver that is powerfull and uses strong methods, then if your solver cannot solve a puzzle, this means it is a hard puzzle

If the puzzle is not hard enough, the puzzle creation process begins again