面试题 —— 数字幻方

请将 1～9 这 9 个数字填入 3x3 的矩阵，使得矩阵的横三行竖三列以及两对角线的数字和相等，找出所有的填充方案。比如下面的这个幻方就是满足条件的方案之一

很明显我们可以使用穷举法求解，一共有 9! = 362880 中排列，然后再对这么多排列进行一一验证。但是这么做有点费劲，下面我们提出一种简单的解决方案，其实这都不算编程题。

第一步：公共和 sum 是 15，这里的公共和就是一行、一列或对角线的和

这个非常显而易见，三行的公共和正好覆盖了 9 个单元格，也就是 1～9 这 9 个数字，那么「公共和」自然就是 1～9 数字和除以 3，得到 15.

第二步：中间单元格必须是 5

这个不是那么显而易见，需要进行简单推理。

我们将中间一行、中间一列以及两对角线的数字加在一起，那就是 4 个公共和，它们正好覆盖了这 9 个单元格以及额外 3次中心的格子。

于是中心单元格的值 cell[1,1] * 3 = sum * 4 - (1+2+3...9) = 15，所以得到 cell[1,1] = 5

第三步：确定数字 1 和数字 9 的位置，必须不在对角上

首先我们假设 1 和 9 在对角，那么 1 所在的行或列剩下两个单元格必须是 6 和 8，才能满足第一行的公共和等于 15。但是不论右上角 cell[1,2] 是 6 还是 8，都会导致第三列和超出 15。

所以可以得出结论，1 和 9 必须不在对角。根据对称性，1 和 9 可以互换，还可以排成横向，共有 2*2=4 种。

那么继续填充第一行的 6 和 8，根据对称性，6 和 8 也可以互换，又是 2 个选择。

第四步：把剩下的所有单元格都挨个算出来吧

根据第二步和第三步，我们得出结论，所有的排列共有 2*2*2 = 8 种。如果你有很好的空间想象力，你可以将上面这个矩阵在脑海里进行翻转 90 度、180度、270度，再分别进行镜像，最终就是 8 种结果。

如果进一步推广，对于 4 阶、5 阶、 N 阶 的幻方求解呢，使用上面的方法那肯定是不够的了。

字节跳动会出这样的题么，我也不知道，要是候选人没见过，短时间内我觉得绝大多数应该都想不出来吧。