algorithm - 创建数独谜题时出现重复问题

Question

我正在尝试创建自己的普通 9x9 sudoku puzzle .

我把问题分成了两部分——

1. 创建一个完全填满的数独，以及
2. 从中删除不必要的数字网格

现在，我卡在了第一部分。

---

这是我简要使用的算法:

a) 首先我选择一个数字(比如 1)，生成一个随机的单元格位置，然后将它放在那里

• 单元格尚未被占用，并且
• 如果该行还没有编号，并且
• 如果该列还没有数字，并且
• 如果 3x3 盒子中没有数字

b) 现在我检查在一行、一列或一个框中只有一个地方是空的，然后我填充它

c) 我检查是否有一个数字没有出现在一个盒子里但出现在同一行和同一列的盒子里(我在这里说的是 3x3 的盒子)，这个数字的位置是固定的并且我填。

d) 我重复上述步骤，直到每个数字在网格上出现九次。

---

我面临的问题是，我经常遇到这样的中间情况:

 0  1  0 | 0  0  3 | 0[4/2]0 
 0 [2] 0 | 0 [4] 1 | 3  0  0 
 3  0 [4]|[2] 0  0 | 0  0  1 
---------+---------+---------
 2  0  3 | 0  5  4 | 0  1  0 
 0  0  1 | 3  0  2 |[4] 0  0 
 0  4  0 | 0  1  0 |[2] 3  0 
---------+---------+---------
 1  0  2 | 0  3  0 | 0  0 [4] 
 4  3  0 | 1  0  0 | 0  0 [2] 
 5  0  0 | 4  2  0 | 1  0  3

看到写[4/2]的地方了吗？这是 2 和 4 的位置，因为标有 [] 的方框。

我该怎么做才能避免陷入这种情况(因为这种情况是一个僵局 - 我无法进一步前进)

Answer 1

还有另一种生成数独谜题的方法:从已知良好的网格开始 - 任何人都可以 - 然后通过应用不破坏不变量的操作随机“打乱”它。有效操作包括:

• 在 block 内交换行
• 在 block 内交换列
• 交换整行 block (例如，前 3 行、中间 3 行、最后 3 行)
• 交换整列 block
• 将一个数字的所有实例与另一个数字交换
• 反射(reflect)董事会
• 旋转棋盘

通过这些操作，您可以生成非常大范围的可能板。但是，您需要注意如何应用这些操作 - 就像天真的洗牌一样，很容易编写一种算法使某些棋盘比其他棋盘更有可能出现。类似于 Knuth 洗牌的技术可能会有所帮助。

编辑:评论中指出，仅靠这些操作不足以创建所有可能的网格。