php - 数独算法解释公式

Question

我正在使用人道算法实现数独求解器。其中有 3 个约束，不同编号的 ini 行、单元格和框。

我用谷歌搜索得到 http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/ .但我不明白这家伙是如何得到 floor($cell/9) 的 return_row 函数或 floor(return_row($cell)/3) * 3 + floor(return_col($cell)/3) 用于 return_block。

我试着通过在 excel 中写下数据来弄清楚，我知道有这样的模式:

[cell] [column]
0      0
1      1
2      2
3      3
4      4
5      5
6      6
7      7
8      8
9      0

但是他是怎么算出公式是 $cell % 9 的呢？

我想知道，如果我不知道公式的答案，我该如何计算？我如何确定该公式？我应该使用什么方法？

谢谢

Answer 1

这来自单元格的计数方式，我们可以称之为行优先。

您可以在这张图片上看到 block 号和单元格号以及它们各自的行号和列号:

行和列

第一行 (0) 包含单元格 0 到 8，第二行包含单元格 9 到 17，依此类推直到第 8 行，其中包含单元格 72 到 80。

如果您对 0 到 8 行以及 0 到 8 列进行编号，我们可以看到对应于此编号的单元格的公式为 cell = 9 * row + col，其中应该解释 get_row 和 get_col 的公式。

当从任何单元格向右移动一列时，您会将单元格计数加 1，这意味着单元格编号的公式类似于 something + col。

当向下移动一行时，您将每行的单元格数量添加到单元格编号，此处为 9，因此公式也类似于 9 * row + something。

将它们放在一起，您会得到一个公式，即 9 * row + col + offset:“+ something”的依赖项是 row 和 col 已确定，但也许它们仍然包含一个常量值.在我们的例子中，公式给出了我们想要的编号，偏移量 = 0，但如果您从 1 开始编号，您的公式将是 9 * row + col + 1。

然而，您不必每次都进行这种推理。刚才，当你有一个矩形，你可以逐行计算项目时，项目编号的公式是总是 row * row_size + col + number at (0,0)。这也是在 C 中为 double 数组分配连续内存的方式，例如，一种非常常见的模式。如果逐列计数，则 col * col_size + row + number at (0,0)

积木

现在 block 的编号方式相同，但只有 3 行和 3 列。您可以将get_block公式中的元素一一替换来理解它:floor(row/3) * 3 + floor(col/3)

由于有 3 行 block 但有 9 个单元格，因此(单元格)行 0、1 和 2 对应于第一行 block ，3 到 5 对应于第二行 block ，6 到 8 对应于最后一行和第三排 block 。我们从中得到的是，一行 block rb 包含单元格行 3 * rb、3 * rb +1 和 3 * rb + 2。相反的操作是除以 3 和 flooring，对于上面的任何表达式，它都会得到 rb。

这对列来说完全一样。

因此在表达式中替换时，我们现在有:block_row * 3 + block_col。这与我们用于单元格编号的公式完全相同(使用 3 而不是 9)，因此您可以从其行和列中获得 block 的编号。