Wang tiles enable efficient pattern compression while avoiding the periodicity in tile distribution via programmable matching rules. However, most research in Wang tilings has considered tiling the infinite plane. Motivated by emerging applications in materials engineering, we consider the bounded version of the tiling problem and offer four integer programming formulations to construct valid or nearly-valid Wang tilings: a decision, maximum-rectangular tiling, maximum cover, and maximum adjacency constraint satisfaction formulations. To facilitate a finer control over the resulting tilings, we extend these programs with tile-based, color-based, packing, and variable-sized periodic constraints. Furthermore, we introduce an efficient heuristic algorithm for the maximum-cover variant based on the shortest path search in directed acyclic graphs and derive simple modifications to provide a 1/2 approximation guarantee for arbitrary tile sets, and a 2/3 guarantee for tile sets with cyclic transducers. Finally, we benchmark the performance of the integer programming formulations and of the heuristic algorithms showing that the heuristics provide very competitive outputs in a fraction of time. As a by-product, we reveal errors in two well-known aperiodic tile sets: the Knuth tile set contains a tile unusable in two-way infinite tilings, and the Lagae corner tile set is not aperiodic.

Department of Decision Making Theory Institute of Information Theory and Automation Czech Academy of Sciences Pod Vodárenskou věží 4 18200 Prague 8 Czech Republic

Department of Mechanics Faculty of Civil Engineering Czech Technical University Prague Thákurova 7 16000 Prague 6 Czech Republic

Zobrazit více v PubMed

Wang, H. Dominoes and the AEA case of the decision problem. In Symposium on Mathematical Theory of Automata 23–55 (1963).

Wang H. Proving theorems by pattern recognition-II. Bell Syst. Tech. J. 1961;40:1–41. doi: 10.1002/j.1538-7305.1961.tb03975.x. DOI

Berger R. The undecidability of the domino problem. Mem. Am. Math. Soc. 1966 doi: 10.1090/memo/0066. DOI

Turing AM. On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. 1937;s2–42:230–265. doi: 10.1112/plms/s2-42.1.230. DOI

Davis M. Computability & Unsolvability. Dover Books on Computer Science Series. Dover Publications; 1958.

Kahr AS, Moore EF, Wang H. Entscheidungsproblem reduced to the PubMed DOI PMC

Lewis HR. Complexity of Solvable Cases of the Decision Problem for the Predicate Calculus. IEEE; 1978. pp. 35–47.

Lewis H, Papimitriou C. Elements of the Theory of Computation. Prentice-Hall Software Series. Pearson Education Canada; 1981.

Cohen MF, Shade J, Hiller S, Deussen O. Wang tiles for image and texture generation. ACM Trans. Graph. 2003;22:287–294. doi: 10.1145/882262.882265. DOI

Derouet-Jourdan A, Kaji S, Mizoguchi Y. A linear algorithm for brick Wang tiling. Jpn. J. Ind. Appl. Math. 2019;36:749–761. doi: 10.1007/s13160-019-00369-z. DOI

Lagae A, Dutré P. A procedural object distribution function. ACM Trans. Graph. 2005;24:1442–1461. doi: 10.1145/1095878.1095888. DOI

Ollinger, N. Two-by-two substitution systems and the undecidability of the domino problem. In Logic and Theory of Algorithms 476–485 (Springer, 2008). 10.1007/978-3-540-69407-6_51

Kovalsky SZ, Glasner D, Basri R. A global approach for solving edge-matching puzzles. SIAM J. Imaging Sci. 2015;8:916–938. doi: 10.1137/140987869. DOI

Lagae A, Dutré P. The tile packing problem. Geombinatorics. 2007;17:8–18.

Rui Yu, C. R. & Agapito, L. Solving jigsaw puzzles with linear programming. In Proceedings of the British Machine Vision Conference (BMVC) (eds Wilson, R. C., Hancock, E. R. & Smith, W. A. P.) 139.1–139.12 (BMVA Press, 2016). 10.5244/C.30.139.

Salassa, F., Vancroonenburg, W., Wauters, T., Della Croce, F. & Berghe, G. V. MILP and max-clique based heuristics for the Eternity II puzzle (2017). arXiv:1709.00252.

Garvie MR, Burkardt J. A parallelizable integer linear programming approach for tiling finite regions of the plane with polyominoes. Algorithms. 2022;15:164. doi: 10.3390/a15050164. DOI

Berger, R. The Undecidability of the Domino Problem. Ph.D. thesis, Harvard University (1964).

Wang H. Notes on a class of tiling problems. Fundam. Math. 1975;82:295–305. doi: 10.4064/fm-82-4-295-305. DOI

Robinson RM. Seven polygons which permit only nonperiodic tilings of the plane. Not. Am. Math. Soc. 1967;14:835.

Poizat B. Une théorie finiement axiomatisable et superstable. Groupe d’étude des théories stables. 1980;3:1–9.

Knuth DE. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley Educational Publishers Inc; 1968.

Knuth DE. The Art of Computer Programming, Volume 4B, Fascicle 5: The: Mathematical Preliminaries Redux; Backtracking; Dancing Links. Addison-Wesley Professional; 2018.

Robinson RM. Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 1971;12:177–209. doi: 10.1007/bf01418780. DOI

Grünbaum B, Shephard GC. Tilings and Patterns. Dover Publications; 2016.

Robinson RM. Undecidable tiling problems in the hyperbolic plane. Invent. Math. 1978;44:259–264. doi: 10.1007/bf01403163. DOI

Senechal M. Quasicrystals and Geometry. Cambridge University Press; 1996.

Kari J. A small aperiodic set of Wang tiles. Discrete Math. 1996;160:259–264. doi: 10.1016/0012-365x(95)00120-l. DOI

Čulík K. An aperiodic set of 13 Wang tiles. Discrete Math. 1996;160:245–251. doi: 10.1016/s0012-365x(96)00118-5. DOI

Kari J, Papasoglu P. Deterministic aperiodic tile sets. Geom. Funct. Anal. 1999;9:353–369. doi: 10.1007/s000390050090. DOI

Labbé S. A self-similar aperiodic set of 19 Wang tiles. Geom. Dedicata. 2019;201:81–109. doi: 10.1007/s10711-018-0384-8. DOI

Labbé, S. & Lepšová, J. A numeration system for Fibonacci-like Wang shifts. In Lecture Notes in Computer Science 104–116 (Springer International Publishing, 2021). 10.1007/978-3-030-85088-3_9.

Jeandel E, Rao M. An aperiodic set of 11 Wang tiles. Adv. Comb. 2021;1:1–37. doi: 10.19086/aic.18614. DOI

Lagae A, Dutré P. An alternative for Wang tiles: Colored edges versus colored corners. ACM Trans. Graph. 2006;25:1442–1459. doi: 10.1145/1183287.1183296. DOI

Lagae, A., Kari, J. & Dutré, P. Aperiodic sets of square tiles with colored corners. Report CW (2006).

Nurmi, T. From checkerboard to cloverfield: Using Wang tiles in seamless non-periodic patterns. In Bridges Finland Conference Proceedings (2016).

Kari J. Reversibility of 2D cellular automata is undecidable. Phys. D: Nonlinear Phenom. 1990;45:379–385. doi: 10.1016/0167-2789(90)90195-u. DOI

Conway J, Lagarias J. Tiling with polyominoes and combinatorial group theory. J. Comb. Theory Ser. A. 1990;53:183–208. doi: 10.1016/0097-3165(90)90057-4. DOI

Mozes S. Tilings, substitution systems and dynamical systems generated by them. J. d’Analyse Mathématique. 1989;53:139–186. doi: 10.1007/BF02793412. DOI

Stam, J. Aperiodic Texture Mapping. Technical report R046 (European Research Consortium for Informatics and Mathematics, 1997).

Liu X, Li C, Lu L, Deussen O, Tu C. Fabricable multi-scale Wang tiles. Comput. Graph. Forum. 2022;41:149–159. doi: 10.1111/cgf.14610. DOI

Hiller, S., Deussen, O. & Keller, A. Tiled blue noise samples. In Proceedings of the Vision Modeling and Visualization Conference 265–272 (Stuttgart, Germany, 2001).

Radin C. Low temperature and the origin of crystalline symmetry. Int. J. Mod. Phys. 1987;1:1157–1191. doi: 10.1142/S0217979287001675. DOI

Winfree E, Liu F, Wenzler LA, Seeman NC. Design and self-assembly of two-dimensional DNA crystals. Nature. 1998;394:539–544. doi: 10.1038/28998. PubMed DOI

Seeman NC, Mao C, LaBean TH, Reif JH. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature. 2000;407:493–496. doi: 10.1038/35035038. PubMed DOI

Novák J, Kučerová A, Zeman J. Compressing random microstructures via stochastic Wang tilings. Phys. Rev. E. 2012;86:4–7. doi: 10.1103/PhysRevE.86.040104. PubMed DOI

Doškář M, Novák J, Zeman J. Aperiodic compression and reconstruction of real-world material systems based on Wang tiles. Phys. Rev. E. 2014;90:062118. doi: 10.1103/PhysRevE.90.062118. PubMed DOI

Braides A, Riey G, Solci M. Homogenization of Penrose tilings. C. R. Math. 2009;347:697–700. doi: 10.1016/j.crma.2009.03.019. DOI

Doškář M, Novák J. A jigsaw puzzle framework for homogenization of high porosity foams. Comput. Struct. 2016;166:33–41. doi: 10.1016/j.compstruc.2016.01.003. DOI

Doškář M, Zeman J, Rypl D, Novák J. Level-set based design of Wang tiles for modelling complex microstructures. Comput. Des. 2020;123:102827. doi: 10.1016/j.cad.2020.102827. DOI

Tyburec M, Zeman J, Doškář M, Kružík M, Lepš M. Modular-topology optimization with Wang tilings: An application to truss structures. Struct. Multidiscip. Optim. 2020;63:1099–1117. doi: 10.1007/s00158-020-02744-8. DOI

Tyburec M, Doškář M, Zeman J, Kružík M. Modular-topology optimization of structures and mechanisms with free material design and clustering. Comput. Methods Appl. Mech. Eng. 2022;395:114977. doi: 10.1016/j.cma.2022.114977. DOI

Jílek M, Somr M, Kulich M, Zeman J, Přeučil L. Towards a passive self-assembling macroscale multi-robot system. IEEE Robot. Autom. Lett. 2021;6:7293–7300. doi: 10.1109/LRA.2021.3096748. DOI

Jilek M, et al. Self-stabilizing self-assembly. IEEE Robot. Autom. Lett. 2022;7:9763–9769. doi: 10.1109/lra.2022.3191795. DOI

Doškář M, Zeman J, Jarušková D, Novák J. Wang tiling aided statistical determination of the Representative Volume Element size of random heterogeneous materials. Eur. J. Mech. A/Solids. 2018;70:280–295. doi: 10.1016/j.euromechsol.2017.12.002. DOI

Coulais C, Teomy E, de Reus K, Shokef Y, van Hecke M. Combinatorial design of textured mechanical metamaterials. Nature. 2016;535:529–532. doi: 10.1038/nature18960. PubMed DOI

Yang W, Liu Q, Gao Z, Yue Z, Xu B. Theoretical search for heterogeneously architected 2D structures. Proc. Natl. Acad. Sci. 2018;115:E7245–E7254. doi: 10.1073/pnas.1806769115. PubMed DOI PMC

Nežerka V, et al. A jigsaw puzzle metamaterial concept. Compos. Struct. 2018;202:1275–1279. doi: 10.1016/j.compstruct.2018.06.015. DOI

Yasuda H, et al. Mechanical computing. Nature. 2021;598:39–48. doi: 10.1038/s41586-021-03623-y. PubMed DOI

Knuth DE. Two notes on notation. Am. Math. Mon. 1992;99:403–422. doi: 10.1080/00029890.1992.11995869. DOI

Korte B, Vygen J. Combinatorial Optimization. Springer; 2006.

Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual (2022). http://gurobi.com.