Nonemptiness problems of Wang tiles with three colors
This investigation studies nonemptiness problems of plane edge coloring with three colors. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of p colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set B  of Wang tiles, the nonemptiness problem is to determine whether or not ?(B)?? ? ( B ) ? ? , where ?(B) ? ( B ) is the set of all global patterns on Z2 Z 2 that can be constructed from the Wang tiles in B. Wang's conjecture is that for any B  of Wang tiles, ?(B)?? ? ( B ) ? ? if and only if P(B)?? P ( B ) ? ? , where P(B) P ( B ) is the set of all periodic patterns on Z2 Z 2 that can be generated by the tiles in B. When p?5 p ? 5 , Wang's conjecture is known to be wrong. When p=2 p = 2 , the conjecture is true. This study proves that when p=3 p = 3 , the conjecture is also true. If P(B)?? P ( B ) ? ? , then B  has a subset B? B ? of minimal cycle generators such that P(B?)?? P ( B ? ) ? ? and P(B?)=? P ( B ? ) = ? for B??B? B ? ? B ? . This study demonstrates that the set C(3) C ( 3 ) of all minimal cycle generators contains 787,605 787 , 605 members that can be classified into 2,906 2 , 906 equivalence classes. N(3) N ( 3 ) is the set of all maximal non-cycle generators: if B?N(3) B ? N ( 3 ) , then P(B)=? P ( B ) = ? and P ( B  ) ? ? for B  ? B . Wang's conjecture is shown to be true by proving that B?N(3) B ? N ( 3 ) implies ?(B)=? ? ( B ) = ? .
nonemptiness wang tiles edge coloring periodic patterns decidability transition matrix