Algorithm for coloring a hexagon tile map with minimum distance (3) for reoccurring colors

Question

I need to create a hex-tile map, using at most 19 colors, where each color must keep a distance of at least 3 tiles. However, I do not need to use all 19 colors. If there exists an algorithm that solves this distance constraint with less than 19 colors, this is completely fine.

The Beckman-Quarles theorem [1] looks related, and there is a 7-color tile map shown where same colored tiles keep a distance of 2 to each other.

But I have a hard time to find an understandable description or even implementation for constructing a hex tile map with a distance of 3.

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

Answer 1

Let's set up a coordinate system where the hex with coordinates (i,j) is adjacent to (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)

I'm going to apply a shear transform so that I can draw hex grids compactly with ASCII art. The transformed 7-hex region looks like this.

**
***
 **

What you want to do is tile the plane with the following 19-color layout.

ABC
DEFG
HIJKL
 MNOP
  QRS

The tiles can fit together like so.

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

I've marked the tile centers with -. These form a lattice generated by two vectors: (5,-3) and (3,2). Given hex coordinates (i,j), we can (inelegantly, perhaps) solve the matrix equation

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

in rational variables u, v, then, trying all four integer roundings of u and v to nearby integers u* and v* respectively, determine which tile (i,j) lies in and apply the appropriate color, where the tile center is

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