algorithm - 将线拟合到网格矩阵中 [Competition , Not HW]

Question

在“AmDocs”最近组织的比赛中，我遇到了以下问题:(问题的基本思路)

给定一个大小固定为 12x12 的矩阵。给定六个长度为 6、5、5、4、3、2 的线段。矩阵有空的空间和填充的空间。您必须返回 "Yes"或 "No"，是否所有 6 个线段都可以同时适合矩阵。线条只能水平或垂直放置。

应该使用什么算法来解决这个问题？包装 ？背包？

Answer 1

我会将问题映射到 SAT 并使用 SAT 求解器。有一个非常自然的映射。定义变量:

x_s_i_j_d = segment s starts at coordinates (i,j) and goes in direction d

(d是“右”或“下”)

首先，遍历所有段和起始位置，并查看给定起始矩阵哪些是可行的。例如，男:

000000000000
111111111111
...

如果段 1 的长度为 2，则 L_seg1_0_0_down = false，因为它碰到了填充空间。

然后，编写禁止两个交叉段的子句。如果段 1 和段 2 的长度都是 2，那么我们添加子句:

(!L_seg1_0_0_right || !L_seg2_1_0_right)

因为如果段 1 使用坐标 (0,0) 和 (1,0)，则段 2 也不能使用 (1,0)。

最后加上每个段必须至少使用一次的条件:

(L_seg1_0_0_right || L_seg1_0_1_right || ...)

对于 seg1 可以到达的所有位置。然后把你最​​喜欢的 SAT 求解器扔给它。