解决方案


思路

一个简单的解决方案是遍历该 9 x 9 数独 次,以确保:

  • 行中没有重复的数字。
  • 列中没有重复的数字。
  • 3 x 3 子数独内没有重复的数字。

实际上,所有这一切都可以在一次迭代中完成。


方法:一次迭代

首先,让我们来讨论下面两个问题:

  • 如何枚举子数独?

可以使用 box_index = (row / 3) * 3 + columns / 3,其中 / 是整数除法。

  • 如何确保行 / 列 / 子数独中没有重复项?

可以利用 value -> count 哈希映射来跟踪所有已经遇到的值。

现在,我们完成了这个算法的所有准备工作:

  • 遍历数独。
  • 检查看到每个单元格值是否已经在当前的行 / 列 / 子数独中出现过:
    • 如果出现重复,返回 false
    • 如果没有,则保留此值以进行进一步跟踪。
  • 返回 true

!?!../Documents/36_LIS.json:1000,616!?!

复杂度分析

  • 时间复杂度:,因为我们只对 81 个单元格进行了一次迭代。
  • 空间复杂度: