-3

我有一个任务，我应该解决一个摩天大楼难题，这个特定的问题。这是一个在 4x4 网格中制作的谜题，其中网格的每个字段在行和列中都有不同的值（类似于数独）。字段内的值向我们显示了在该字段上建造的 skyskcaper 的高度（1-4，4 是最高的建筑物）。网格外的数字是从该方向可见的摩天大楼数量。（例如，从这个方向您只能看到一栋摩天大楼，因为最高的（4 栋建筑）覆盖了其他建筑物的视野 -> 4312 <- 从这个方向您可以看到三栋建筑物（仅覆盖高度为 1 的建筑物））。只给出外面的数字，你必须填写网格。有关游戏规则的更多详细信息：这里

这是开始状态，也是可能的输出之一。

我正在尝试，但我想不出对建筑物秩序的良好约束。我刚刚为行和列中的不同值输入了约束。

problem = Problem()

variables = range(16)
domains = range(1, 5)
problem.addVariables(variables, domains)

for row in range(4):
    problem.addConstraint(AllDifferentConstraint(), [row * 4 + i for i in range(4)])

for col in range(4):
    problem.addConstraint(AllDifferentConstraint(), [col + 4 * i for i in range(4)])


solution = problem.getSolution()
print(solution)
4

1 回答 1

1

这是使用 MiniZinc 的解决方案（抱歉没有提供 Python 解决方案）：

include "globals.mzn";

int: N = 4;
set of int: POS = 1..N;
set of int: SEEN = 1..N;
set of int: HEIGHT = 1..N;

array[POS] of SEEN: top = [2, 1, 2, 2];
array[POS] of SEEN: bottom = [2, 4, 3, 1];
array[POS] of SEEN: left = [2, 3, 1, 2];
array[POS] of SEEN: right = [2, 2, 3, 1];    

array[POS, POS] of var HEIGHT: height;

constraint forall(p in POS)
    (all_different(row(height, p)) /\
     all_different(col(height, p)));

predicate sum_seen(array[POS] of var HEIGHT: values, int: seen) = 
    (sum(i in 2..N)(values[i] > max([values[j] | j in 1..i-1])) = seen - 1);

constraint forall(p in POS)
    (sum_seen(row(height, p), left[p]) /\
     sum_seen(reverse(row(height, p)), right[p]) /\
     sum_seen(col(height, p), top[p]) /\
     sum_seen(reverse(col(height, p)), bottom[p]));

solve satisfy;

output ["height = "] ++ [show2d(height)];

关键观察是，对于每一行，该行中最大建筑物高度增加的次数应等于该行中看到的建筑物数量（给定值）。相应的保持列，反向保持行和列。

于 2020-05-08T19:33:10.390 回答