algorithm - 一个很酷的算法来检查数独领域？

Question

有谁知道检查数独配置是否有效的简单算法？我想出的最简单的算法是伪代码(对于大小为 n 的棋盘)

for each row
  for each number k in 1..n
    if k is not in the row (using another for-loop)
      return not-a-solution

..do the same for each column

但我很确定一定有更好的(在更优雅的意义上)解决方案。效率并不重要。

Answer 1

您需要检查数独的所有约束:

• 检查每一行的总和
• 检查每列的总和
• 检查每个方框的总和
• 检查每一行的重复数字
• 检查每列是否有重复的数字
• 检查每个盒子上的重复数字

总共 6 次检查.. 使用暴力方法。

如果您知道棋盘的大小(即 3x3 或 9x9)，则可以使用某种数学优化

编辑:总和约束的解释:首先检查总和(如果总和不是 45，则停止)比检查重复项快得多(也更简单)。它提供了一种丢弃错误解决方案的简单方法。