在没有一个子矩形的颜色全部相同的情况下，要求对网格进行着色的最佳方法是什么？

Question

我有一个 m 乘 n 的矩形网格，每个网格点有 c 种可能的颜色。 我想使用 OR-Tools 找到一个有效的着色。 最好的方法是什么？

我在想，可能是为每行的每对列添加一个OnlyEnforceIf子句（基于颜色赋值平等），然后断言如果两个不同行中的对齐对也是相等的，那么这两对对齐对不能有相同的颜色。

然而，这看起来非常啰嗦，而且引入了很多新的变量。

Answer 1

只要创建

color[x, y, c] 一个布尔变量，点(x, y)的颜色为真，则其颜色为c。

然后添加约束条件。

每个点只有一种颜色

for each (x, y): 
    sum over c color[x, y, c] == 1

任何矩形都不是统一的颜色。

for each x1, y1, x2, y2, c:   # (x2 > x1, y2 > y1)
    BoolOr(color[x1, y1, c].Not(),
           color[x1, y2, c].Not(),
           color[x2, y1, c].Not(),
           color[x2, y2, c].Not())