在《人工智能 – 现代方法》这本书中以及这个链接中的回答：避免重复状态的搜索算法

我有一个问题。我大致理解了我们是如何得到2 d²作为不同状态的数量的，但我没有理解几何方法。为了参考，我展示了矩阵和解决方案。

6 5 4 3 4 5 65 4 3 2 3 4 54 3 2 1 2 3 43 2 1 0 1 2 32 3 2 1 2 3 45 4 3 2 3 4 56 5 4 3 4 5 6

在上面，你有一个7×7的矩阵，它包含了从中心到距离3的所有单元格，正如你所见 – 通过计数可达状态的数量并看到它符合公式：

#reachable_cells(0) = 2*0*1 + 1 = 1#reachable_cells(1) = 2*1*2 + 1 = 5#reachable_cells(2) = 2*2*3 + 1 = 13#reachable_cells(3) = 2*3*4 + 1 = 25

这是由Google的工程师Amit回答的。

回答：

这个想法是，同距离的单元格形成一个菱形形状（45°的正方形）。

当你查看3的出现时，你有4个边，总共有4*3=12个单元格：

6 5 4  3  4 5 6
5 4 3 2 3 4 5
4 3 2 1 2 3 4
3 2 1 0 1 2 3
2 3 2 1 2 3 4
5 4 3 2 3 4 5
6 5 4  3  4 5 6

对于其他距离，我们得到以下结果：

  distance   occurrences  ----------------------     0            1     1            4     2            8     3           12     ..     n           4n

公式4n对于所有n都成立，除了n=0时，它是1。

现在，要知道距离n（包括n）以内的不同单元格的数量，我们得到这个表格：

  distance   occurrences  ----------------------     0            1     1            1+4     2            1+4+8     3            1+4+8+12     ..     n            1 + ∑4i, for i in [1..n]

现在1 + ∑4i = 1+4∑i，而∑i是三角数，这意味着我们可以简化为：

1+4( ½n(n+1) ) = 1+2n(n+1)，这就是你在示例中给出的公式：

#reachable_cells(0) = 2*0*1 + 1 = 1#reachable_cells(1) = 2*1*2 + 1 = 5#reachable_cells(2) = 2*2*3 + 1 = 13#reachable_cells(3) = 2*3*4 + 1 = 25  ...#reachable_cells(n) = 2*n*(n+1) + 1