以最小距离(3)为重复出现的颜色着色六边形瓦片 map 的算法

Question

我需要创建一个六边形 map ，最多使用 19 种颜色，其中每种颜色必须保持至少 3 个图 block 的距离。但是，我不需要使用全部 19 种颜色。如果存在一种算法可以用少于 19 种颜色解决这个距离约束，那就完全没问题了。

Beckman-Quarles 定理 [1] 看起来很相关，并且显示了一个 7 色瓦片 map ，其中相同颜色的瓦片彼此保持 2 的距离。

但我很难找到构建距离为 3 的六边形瓦片 map 的可理解描述甚至实现。

[1] http://de.wikipedia.org/wiki/Satz_von_Beckman_und_Quarles

Answer 1

让我们建立一个坐标系，其中坐标为 (i,j) 的十六进制与 (i-1,j), (i-1,j+1) 相邻， (i,j-1), (i,j+1), (i+1,j-1), (i+1,j).

(0,3)       (2,2)       (4,1)
      (1,2)       (3,1)
(0,2)       (2,1)       (4,0)
      (1,1)       (3,0)
(0,1)       (2,0)
      (1,0)
(0,0)

我将应用剪切变换，以便我可以使用 ASCII 艺术紧凑地绘制六边形网格。转换后的 7 十六进制区域如下所示。

**
***
 **

您要做的是用以下 19 色布局平铺平面。

ABC
DEFG
HIJKL
 MNOP
  QRS

瓷砖可以像这样拼在一起。

   111
   1111
00011-11
00001111333
00-001113333
 000022233-33
  00022223333555
     22-223335555
      222244455-55
       22244445555
          44-44555
           4444
            444

我用 - 标记了图 block 中心。它们形成了一个由两个向量生成的格:(5,-3) 和 (3,2)。给定十六进制坐标 (i,j)，我们可以(可能不够优雅)求解矩阵方程

[5 -3] [u]   [i]
[3  2] [v] = [j]

在有理变量 u, v 中，然后尝试将 u 和 v 的所有四个整数四舍五入为附近的整数 u* 和 v* 分别确定 (i,j) 所在的图 block 并应用适当的颜色，图 block 中心位于

[5 -3] [u*]
[3  2] [v*].