如何判定由三角形和正方形构成的拼图集合能否在网格上有效拼接？

针对你提出的问题，以下是一套可落地的多项式时间判定方案，解决平面性检测仅为必要条件的不足：

核心思路 #

问题本质是带几何约束的网格嵌入问题：每个数字对应网格上的一个整数坐标点，每个拼图块的点集必须严格匹配正方形/三角形的几何属性，且相同数字对应同一坐标。我们通过约束传播+坐标可实现性验证来完成判定。

具体步骤 #

1. 构建几何约束集 #

首先将拼图块的形状要求转化为点对之间的距离平方约束（用距离平方避免浮点数误差，网格中两点距离平方必为整数）：

• 正方形拼图块（如[a,b,c,d]）：
  四个点的点对距离平方需恰好包含两个值：s（边长平方）和2s（对角线平方）。其中4对点的距离平方为s（正方形的四条边），2对点为2s（正方形的两条对角线，且这两对点必须是不相交的两组，即(a,c)和(b,d)）。
• 三角形拼图块（如[a,b,c]）：
  三个点的距离平方需满足三角形不等式，且若为网格可实现的非退化三角形（如直角三角形），需符合勾股定理：某一距离平方等于另外两个距离平方之和。

2. 约束一致性检查 #

通过约束传播验证所有约束无矛盾：

• 为每对点维护其距离平方的可能值，从拼图块的约束出发，逐步推导关联点对的约束（例如：若从正方形块得出a-b的距离平方为s，从三角形块得出a-b的距离平方为t，则必须s=t）。
• 可使用类似Floyd-Warshall的算法遍历所有点对，确保传递性约束成立（如a-b距离为s，b-c距离为s，则a-c的距离平方只能是s或2s，需匹配对应拼图块的约束）。

3. 坐标可实现性验证 #

当所有约束一致后，验证是否存在整数坐标满足所有距离要求：

• 选取任意节点作为原点(0,0)，选取另一节点设为(k,0)（k为边长的整数，由距离平方s=k²得出）。
• 逐步推导其他节点的坐标，利用整数坐标的性质检查是否存在合法解：例如，若a-b距离平方为s，b-c距离平方为s，a-c距离平方为2s，则c的坐标只能是(k,k)或(k,-k)，需符合其他约束。

复杂度说明 #

整个流程的时间复杂度为多项式级：

• 约束构建的时间与拼图块数量、点对数量线性相关；
• 约束传播的时间为O(n³)（n为节点总数）；
• 坐标验证的时间与节点数量线性相关。

为什么平面性检测不够？ #

平面性仅保证图可嵌入平面，但无法约束点集的几何形状（例如，平面嵌入可能将正方形的对角线拉伸为任意长度，不满足√2倍边长的要求），而上述方法通过几何约束严格限定了每个拼图块的形状，确保布局的有效性。

内容的提问来源于stack exchange，提问作者nuemlouno