如何生成5x5 sudoku拼图？

Question

我已经编写了生成5x5 sudoku字谜的算法。下面是它的工作原理。在我的5x5 sudoku上，只有两个违禁品。在每一行和每列中只能有一种项目。

1. 产生随机位置(0，4)
2. 如果位置已满，请返回1。
3. 生成随机数(1，5)
4. 如果行或列中已经有此数字，请返回到3。
5. 用数字填充位置
6. 如果还有空位，请返回到1。
7. 删除随机数。

主要有两个问题。

1. 该算法生成死锁，因此我检查尝试，如果超过10次尝试填充位置，我重置所有，然后再试一次。
2. 太慢了。由于我希望我的sudoku移动设备，我需要优化它。我的nexus 5秒最多需要5秒，而三星星系的旧趋势则需要2分钟。

Answer 1

您可以替换步骤1-6，方法是从一个已知的有效填充网格开始，然后对其应用保持约束不变的转换。

例如，您可以从这个网格开始，这很容易通过将grid[i][j]设置为((i + j) % 5) + 1来生成。

1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

然后，如果您交换两行，则仍然有一个有效的网格，例如交换行1和3：

1 2 3 4 5
4 5 1 2 3 <
3 4 5 1 2
2 3 4 5 1 <
5 1 2 3 4

您还可以交换两列，但仍然得到一个有效的网格，例如交换列2和4：

1 2 5 4 3
4 5 3 2 1
3 4 2 1 5
2 3 1 5 4
5 1 4 3 2
    ^   ^

所以先从普通网格开始，然后在循环中生成随机行对和随机列对，然后交换它们。您也可以交换数字(例如，将所有5s改为3s，反之亦然)。您将始终得到一个有效的结果。

然后，您可以继续到步骤7。

然而，第7步比它看起来更复杂，因为你需要你的谜题是可以解决的。换句话说，在每个点上，玩家应该可以逻辑地推断出至少一个单元格的值，而不需要猜测。

因此，您需要编写一个函数来计算空单元格的有效值列表，使用这些约束(您只需要一个不存在于同一行或同一列中的所有值的列表)。当删除步骤7中的数字时，在循环中：

• 选择一个随机单元
• 根据网格中其他非空单元格计算该单元格的有效值。
• 如果只有一个可能的值(单元格中的值)，则可以删除它。

另一种可以推断单元格值的方法是，如果它是其行或列中唯一可能存在该值的单元格。要验证这一点，您需要为单元格所在的行或列中的每个单元格计算一个有效值列表(在同一行或同一列的其他非空单元格中不存在的值)，即使单元格包含多个可能的值，如果它是其列中包含该值的该行中唯一的单元格，或者其列中的唯一单元格，则可以确定该值，以便可以删除它。

您可以重复此操作，直到移除所需数量的单元格为止。因为您删除的每个单元格在被删除时都能够被推断出来(因为一旦单元格为空，它是该单元格的唯一可能值)，那么播放机应该能够通过将值添加回删除它们的相反顺序来解决这个难题。

如果这没有产生足够的“有趣”谜题，那么您可以采取“欺骗”的方法，即拥有一个现有手工创建的谜题数据库，然后选择一个，然后随机交换行和列，或者交换数字。这可能有一些版权问题，作为“衍生作品”，但这不是一个程序问题。