Sudoku generator algorithm [closed]

Question

I made an algorithm to generate sudokus, but it was terribly inefficient. Each puzzle took minutes to generate. So now I am trying to write it again in optimal way. But I am experiencing some problems I need help with.

There are two aproaches:

1. Start with blank grid and add numbers, then check if it is solvable.
2. Create full valid grid with all 81 numbers and then remove until we are happy with number of remaining numbers and it is still solvable.

First I used first approach but now I am going to use second because I think it is more effective (we are starting with valid puzzle which is guaranteed to be solvable). I am right that second approach is better?

When I am trying to generate full populated grid I am running into difficulties. My algorithm is:

• Set candidates for each cells. Initialy they are numbers 1 through 9.
• Pick random cell without value.
• Select random candidate from that cell and assign it as cell value. Other candidates are discarded.
• Now for each row, cell and square corresponding to assigned cell I remove value of cell from these candidates, so each number is unique in a row/column/square
• Repeat

This technique guarantees random grid without duplicate numbers. However, most of times, when I do not break any rules of placement a run to conflict - like empty cells where all candidates have been removed etc and I need to start over. Is there more elegant/efficient way to filling entire grid with numbers without breaking rules of placement and still random numbers?

Inapproachable

Answer 1

Have you looked at existing algorithms and/or code?

Check out https://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf for an algorithmic description, and Peter Norvig's article at http://norvig.com/sudoku.html.

There are some implementations out there in Python. So far I've never seen a published C# solution.

Spangle

Answer 2

My approach is combining your first and second methods together.

First, you must have a sudoku solver. Apply the solver on an empty sudoku. That is to find a solution for a sudoku with no clues. Filling in numbers from top left to right bottom in order. Otherwise, there is a time issue. I don't know why. Anyway, it works very fast wait no time to have a completed sudoku puzzle. When you apply backtracking, shuffle the list of possible numbers for each position. Otherwise, you will get the same puzzle everytime.

Second, randomize a new list of all positions. That is a list of 81 positions in random order. According to this list of order, try removing numbers from the above puzzle. Everytime, you remove a number, you have to check if it has more than one solution. If it has more than one solution. The number should put back and try next position in the random list. This process continues until the end of list or you already has removed 64 numbers from the puzzle successfully. The number is 64 because somebody has proved that there is no sudoku with less than 17 clues with unique solution. This process is varies from 15 seconds to 2 minutes. Usually 30 seconds to get a sudoku puzzle.

Third, if you don't want to wait 30 seconds to 2 minutes for each sudoku puzzle, you may apply some mutations to the above sudoku. This includes switching rows and columns, rotating. You may also remap the numbers. For example, 1->2, 2->3...9->1. After rotating and remapping, no one will notice this is the original sudoku.

Tagmeme

Answer 3

If you are looking at some existing algorithms then there are a c# project for that. That acually comes from the same solution as Peter Norvig's. Read more about it here

Hope this will help!

Silvana

Answer 4

I use programming to remove all prior entries that conflict with the last entry. With this method, I can enter some givens and periodically take a count of the solutions or enter the entire grid. I have not used random entry of the entire grid because random removal of prior entries could result in a long setup. For random entry, I would expect that blocking entry of a conflict would lead to a blank cell, so the answer may be to live with a long setup while removing prior conflicting entries. You will need to return to all empty cells until no empty cell remains. When all cells are filled, the solution must be valid, otherwise a conflict would have been removed.

Caston