Sudoku generator algorithm

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?

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.