Three coloring Penrose rhombs

According to page 27 of Martin Gardner’s Penrose Tiles to Trapdoor Ciphers, John Conway wondered if Penrose tiles could always be colored using only three colors in such a way that adjacent tiles never had the same color. This was proved affirmative for Penrose Rhombs in 2000. In 2002, I published a stochastic algorithm that appears to do the job. This webpage illustrates that algorithm.

The algorithm is based on a so-called stochastic cellular automaton. To begin, we assign one of three possible colors to each tile randomly. Then, we 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 that 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 that 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.