要求为没有子矩形具有所有相同颜色的网格着色的最佳方法是什么？

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())

要求为没有子矩形具有所有相同颜色的网格着色的最佳方法是什么？

What is the best way to ask for a coloring of a grid where no sub-rectangle has all of the same colors?

combinatorics

or-tools

sat