Wang タイル
Jeandel と Rao が見つけた 11 枚の Wang タイルで、24×16 のマス目を敷き詰めた。
なにか
Wang タイルは、辺に色のついたただの正方形で、回転も裏返しも禁止される。規則は「隣り合う辺は同じ色」だけである。1961年に論理学者の王浩（Hao Wang）が「どんなタイル集合も、敷けるなら周期的に敷けるはずだ」と予想したが、弟子のバーガーが2万枚超の反例=非周期にしか敷けない集合を見つけて予想は崩れた。以来「最小何枚まで減らせるか」の競争が55年続き、2015年にジャンデルとラオが計算機探索（数百コア×約1年）で決着させた。11枚・4色が最小で、10枚以下では非周期集合は存在しない。この作品は、その11枚をそのまま使っている。
身近な顔もある。ゲームのグラフィックスでは、つなぎ目が合うタイル画像をランダムに敷いて「繰り返し感のない地面」を作る技法が Wang タイルと呼ばれ、まったく同じ数理が働いている。
どう作ったか
タイル表は、原論文と Labbé の後続論文（図と Sage パッケージ）の2つと突き合わせた。敷き詰めは、自分で書いたバックトラッキング探索で求めた。種によって解けるまでの手数が桁で違い、既定の種は 24×16 を約 70 万手（0.2 秒）で解く。11 種のタイルはすべて使われていて、隣り合う辺の色は、別の手順で確かめ直しても全部そろっている。できた長方形には、縦にも横にも並進の周期がない。
出典
- 数理
- E. Jeandel & M. Rao, "An aperiodic set of 11 Wang tiles", Advances in Combinatorics (2021, arXiv:1506.06492)。タイル表の突合は S. Labbé, arXiv:1808.07768 Figure 1。ゲームへの応用は Cohen ら "Wang Tiles for Image and Texture Generation" (2003)
- 生成
- generators/wang.js（バックトラッキング・種固定＝決定的・24×16）