Sudoku generator algorithm

问题:

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.

1. There are two aproaches, start with blank grid and add numbers, then check if it is solvable. Second approach is to 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?

1. 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?

Thank you.

回答1:

Have you looked at existing algorithms and/or code?

Check out http://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.

Good luck!

回答2:

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!

回答3:

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.