Imaginary Space【科普 解法】level11 解法大全

Imaginary Space【科普 解法】level11 解法大全如下：

1.引子：

在这里首先给出一个直观的小定理。这个定理在构建十一关的逻辑上有着重要作用。

定理：

完成每关方块搭建所需的最少方块个数n大于等于每个视图中的方块个数

即：

n≥max{num.左视图，num.主视图，num.俯视图}

这个定理适合检验最少通关最少方块数量，如果n为给定方块数，则所有方块均需要用到。现在我们不妨分析一下level11的情况，三个视图中16个格子全部被覆盖，本关中方块数共有16个，也就是说，完成本关最少方块个数大于16个，结合本关有解法，我们可以得出，最少需要16个方块。

2.思考方向

I.数学模型建立

假设红线是X轴，蓝线是Y轴，绿线是Z轴。如图。

已知每个视图可见16个方块的面，共有16个方块可供搭建，结合定理一，可以大胆得出，从任何一个视图看过去，均无方块遮挡。

所以只要在搭建方块过程中体现出无遮挡的特性即可。为了方便分析，我们认为每个正方体长度为1。很容易从 Y=1，Y=2，Y=3这三个平面将搭建空间分为三层，为了方便说明，将Y=0~Y=1之间的空间区域记作第一层，如果有方块填充，标记为1，依此类推，共有四层，共1，2，3，4四种标记。于是，容易有，在4*4的格子中填充满16个数就能体现出Y轴方向的无遮挡性，X轴和Z轴的无遮挡性，通过4*4方格的横轴方向、纵轴方向无相同数来体现。

II.算法思考

在二维方格中填充数，满足一定的规则，很容易想到著名的8皇后问题，以及对应的优秀解法——回溯法。八皇后问题的详情可见百度百科。

回溯法的主要思想就是，每做一次遍历计算就立刻检验，如果不能达到检验标准，立刻返回到上一层计算，免去了遍历法当中繁琐的计算。

以这个问题为例，我们简单的说明一下回溯法的算法规则。简单的说就是走不通再退回的算法，相比遍历计算，计算时间复杂度更小。

这时候，思路就很清晰了，使用回溯法依次判定四个平面，就可以得到所有解。

在这里我使用matlab编程，使用for循环语句遍历，并编写check函数文件进行检验。

一般来说，回溯法和递归调用共用可大大简化程序代码，提高程序复用性。（比如改为5*5空间，只需要改变几行代码即可

。

程序运算之后共有576个解法。

以第一层为1234为例，共有24种解法，分别为：

以第一行为例，逐行填充后结果为：

那么问题已经基本解决了。

III.排列组合与其他

还有一个问题就是很多人认为共有864种结果，即，36*24。第一层排列方法有A44，24种第一层固定，第二层共有9种，第三层四种，当前三层确定，第四层也被确定，所以共有864种结果，真的是这样吗？

看下这两种情况的差异就明白了：当第二层为2143时，第三层共有四种排列方法，但第二层为2341时，第三层只有2种排列方法。因为随着层数增加，排列会出现干涉现象。所以第一层确定的基础上，共有24种，并非36种，24*24=576种。

同理，使用排列组合解决该问题时，先建立数学模型，在固定一层，的基础上，写出下面三层的可能情况，共24种，根据轮换对称，24*A44即可得到结果。

如果不考虑坐标（就是说仅仅考虑形状）。任意一种形状，取六个面中一个面为正方向，正方向矢量平行于X、Y、Z法向量的时候为不同解法，故576/6=96。共有96种不同形态解法。

3.总结

在本问题中，共有576种解法，不考虑空间位置，共有96种解法。随着排列的进行，不同行列之间会出现相互干涉，随着填充矩阵的增大，问题复杂度急剧增大。

，提取码：rudz

以上。

以上就是Imaginary Space【科普 解法】level11 解法大全相关内容。