Three-Coloring Penrose Tiles

The idea

Penrose tiles are briefly discussed on the aperiodic digraph fractiles page. John Conway has asked if Penrose tilings are three colorable in such a way that adjacent tiles receive different colors. Stan Wagon and Tom Sibley have proven that tilings by rhombs (like the one above) are three-colorable and William Paulsen has proven that tilings by kites and darts are three-colorable. As far as I know, the question is open for tilings by pentacles.

I have published a paper in Computers & Graphics which describes an algorithm which seems to three-color Penrose tiles of all types. The algorithm works by running a three state, stochastic cellular automaton on the piece of a tiling you want to three-color. The cellular automaton works as follows. First, assign one of three possible colors to each tile randomly. Then, allow the cellular automaton to evolve according to the following set of rules:

If the value of a cell (or tile) equals the value of a bordering cell which is closer to the origin (as measured by some arbitrary point chosen within each tile), then with 90% probability, the cell changes value randomly to one of the other two colors.
If the value of a cell does not equal the value of a bordering cell which is closer to the origin, but does equal the value of a cell farther away from the origin, then with 10% probability, the cell changes value.
If the value of the cell does not equal the value of any bordering cell, the cell does not change value.

Note that three-colorings are stable under these rules. The hope is that three-colorings are attractive equilibria.

More images

Here are some more images. The first three are large still gifs of Rhombs, Kites and Darts, and Pentacles. The third one is an animated gif illustrating the algorithm on a tiling of 115 Kites and Darts and evolving through 41 generations.

Code

The idea behind the code is as follows. The tilings by rhombs and by pentacles were generated using the DigraphFractals package as described on the aperiodic digraph fractiles page. The tilings by kites and darts were generated using Lyman Hurd's Penrose Tiles package. These images were then converted to PlanarMap and PlanarGraph objects as defined in the GraphColoring package by Stan Wagon. I wrote code to run the cellular automata on the PlanarGraph objects. Final three-colored images were rendered by the ShowMap function defined in the GraphColoring package. You may download the following files if you are interested in more details:

The paper in PDF format
The Mathematica notebook used to generate all the pictures on this page.

If you want to run the code in the notebook, you will also need my DigraphFractals package, Lyman Hurd's Penrose Tiles package, and as Stan Wagon's GraphColoring package which comes on the CD with his book Mathematica in Action. The book is well worth owning, by the way.