C# 数独生成器算法

Sudoku generator algorithm

提问by

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.

1. 有两种方法，从空白网格开始并添加数字，然后检查它是否可解。第二种方法是使用所有 81 个数字创建完整的有效网格，然后删除直到我们对剩余数字的数量感到满意并且它仍然可以解决。

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

1. 当我尝试生成完全填充的网格时，我遇到了困难。我的算法是：

   • 为每个单元格设置候选。最初它们是数字 1 到 9。
   • 选择没有价值的随机单元格。
   • 从该单元格中选择随机候选并将其分配为单元格值。其他候选人被丢弃。
   • 现在，对于与指定单元格对应的每一行、单元格和方块，我从这些候选中删除单元格的值，因此每个数字在行/列/方块中都是唯一的
   • 重复

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.

谢谢你。

采纳答案by Roy Dictus

Have you looked at existing algorithms and/or code?

您是否查看过现有的算法和/或代码？

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

查看http://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf中的算法描述，以及http://norvig.com/sudoku.html 上Peter Norvig 的文章。

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

Python 中有一些实现。到目前为止，我从未见过已发布的 C# 解决方案。

Good luck!

祝你好运！

回答by Arion

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

如果您正在查看一些现有算法，那么就有 ac# 项目。这实际上来自与 Peter Norvig 相同的解决方案。在此处阅读更多相关信息

Hope this will help!

希望这会有所帮助！

回答by Keith

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.

我使用编程来删除与最后一个条目冲突的所有先前条目。使用这种方法，我可以输入一些给定并定期计算解决方案或输入整个网格。我没有使用整个网格的随机条目，因为随机删除先前条目可能会导致设置时间过长。对于随机条目，我希望阻止冲突条目会导致空白单元格，因此答案可能是在删除先前冲突条目的同时忍受较长的设置。您将需要返回到所有空单元格，直到没有空单元格为止。当所有单元格都被填满时，解决方案必须有效，否则将消除冲突。