带有Python中约束模块的摩天大楼拼图

Question

我有一个任务，应该解决一个摩天大楼难题，这个特定的问题。这是一个在4x4网格中制作的难题，其中网格的每个字段在行和列中都有不同的值（类似于数独）。字段中的值向我们显示了在该字段上构建的skyskcaper的高度（1-4，4是最高建筑物）。网格外部的数字是从该方向可见的摩天大楼的数量。 （例如，从这个方向您只能看到一个摩天大楼，因为最高的（4座建筑物）覆盖了其他摩天大楼的视图-> 4312 here

This是开始状态，this是可能的输出之一。

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

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)

Answer 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)];

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