|
前阵子外甥女突然问我，“姨酱，你会填9宫格吗？就是9个格子分别填入1-9这9个数字，使得每一行，每一竖排，对角线加起来都等于15？” 这个问题真难倒我了，因为我想起了高中那会儿给化学方程式配平，总是按下葫芦浮起瓢，填好这个系数那个系数又不平衡了。不过后来我还是用线性代数+R语言后搞定了这一心中遗憾。于是我脑海里灵光一闪：会不会用线性代数的方法也可以解出这个问题呢？我觉得这个思路还是靠谱的。为什么这么说呢？ 我们看，九宫格其实就相当于一个3×3的矩阵，要求每个矩阵的元素按照特定的方向求和后，代数和为相等的一个值，也就是15。 转变成线性方程组的形式就是： 从上面的未知数个数和方程个数相比来看，因为未知数个数要＞方程个数，所以在实数范围内，解是有无穷多个的。 不过，由于9宫格的要求，限定了所填的数必须是1-9这9个自然数，因此，则需要加入一些约束条件，来让它在解集中找到合适的解。 加入哪些约束条件，才可以表示“只能从1-9这9个自然数里挑选”呢？ 单纯一个代数式恐怕是很难表现出来的，但是可以从4个约束条件来实现，即 这样一来，俨然构成了一个线性规划求解的的雏形了。只不过，如果用笔算来求解的话，够呛。因此得借助计算机软件。 那么最亲民的软件就是excel了，于是我们可以选择excel里面的规划求解模块的功能，来计算求解。 只不过在正式开机之前，我们得把上面的资料整理一下，让它能够符合线性规划求解的范式，直接代入到excel你是无法计算的。究竟怎么转变呢？其实不难 首先要有个目标函数。这个目标函数按道理来说就是刚才所说的“从1-9这9个自然数中挑选数字填到矩阵的各个元素位置上”，但是我们做不到将这个汉语直接翻译成代数式，刚才我们也用了4个约束条件，只满足了这个语文句子的前半句。因此，我们必须转变一下思路：将目标函数设定的简单一些，然后把约束条件加多一些，这样就可以间接实现了。请看如下操作 目标函数： 约束条件： 好，这样我们就可以开始excel的操作了 第一步，点击进入excel的线性规划求解模块 第二步，分别填入目标函数，约束条件 点击“求解”后，不到半秒钟，就计算出结果了 是不是很快呢？ 其实在之前我提示到，因为线性方程组的未知数个数要＞方程个数，因此方程组没有唯一解，实际上在这里也是成立的。比方说上面的9宫格看成3阶方阵的话，那么对其转置，或者对其进行初等行变换，也是成立的： 好，知道了方法之后，再去求16宫格，25宫格，下面就是求得的16宫格、25宫格的解 不过呢，25宫格倒是花了2分多钟让excel来跑才跑出结果。我的电脑配置是I5处理器，8G内存。如果你的电脑配置比我高，那么会跑的比我的更快就出结果了。 在这里补充一下： 如果是求16宫格，那么目标函数应该为所有单元格求和=136，约束条件要修改成每一行、列、对角线的和应该为34； 如果是求25宫格，目标函数就应该为所有单元格求和=325，约束条件为每一行、列、对角线的和应该是等于65。这个是我在数据分析师群里面，有个老司机告诉我的规则。 用数学表达就是
那么，是不是有了excel之后，36、49……任意n×n宫格都可以计算呢？ 我倒不推荐你这么做，因为随着矩阵的阶数不断增大，线性规划求解的所要计算的子问题就越多，运算量就越大！而且有些数量的X宫格还不一定有解呢。 End. |
|
|
