# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find minimal sets of templates for constructing tiling patterns

Contributed by:
Wolfram Research

ResourceFunction["FindMinimalTilings"][ finds a minimal, | |

ResourceFunction["FindMinimalTilings"][ allows for | |

ResourceFunction["FindMinimalTilings"][ draws pattern constraints from a given set | |

ResourceFunction["FindMinimalTilings"][…, finds tiling patterns with matrix dimensions |

A mask is a rectangular array containing only zeroes and ones.

A template is a rectangular array containing non-negative integers or Blank (_) values.

A complete set of binary templates follows from a mask by turning 0's into blanks, 1's into independent slots, and then filling the slots with 1's and 0's in all possible ways.

Similarly, a complete set of *c*-color templates follows by filling the mask slots with all possible Tuples of the numbers 0,1, …, *c*-1, where of course *c* is a positive integer.

A template is mask-consistent if it belongs to the complete *c*-color set derived from mask.

Sets of potentially many templates should have the same bounding size, say {*a*,*b*}, and they certainly do if derived from a single mask of bounding size {*a*,*b*}.

A tiling pattern is any rectangular array of non-negative integers.

If all {*a*,*b*} subarrays of an {*m*,*n*} pattern match a template from input templates, the tiling pattern is said to be "consistent with local constraints listed in templates", or for short, "template consistent".

By "minimal" we mean that any found subset of templates can not be reduced by removing a single templates without making it impossible to form a tiling pattern of size *s*.

There are two methods to search for minimal sets. One is to start with cardinality n subsets and, for positive results, check reducibility to cardinality *n*-1 subsets. The other is to perform a breadth-first search of increasingly large subsets up to *n* cardinality. This resource switches between methods automatically according to coverage.

The smallest resulting constraint sets can have only one template:

In[1]:= |

Out[1]= |

Find minimal pairs of 2×2 templates leading to valid binary tiling patterns of size 4×4:

In[2]:= |

Out[2]= |

Show the patterns:

In[3]:= |

Out[3]= |

Change the mask shape:

In[4]:= |

Out[4]= |

Find minimal pairs of 2×2 templates leading to valid 3-color tiling patterns of size 4×4:

In[5]:= |

Out[5]= |

Depict results of a 3-color search on an 8×8 grid:

In[6]:= |

Out[6]= |

FindMinimalTilings now works with rectangular tiling patterns:

In[7]:= |

Out[7]= |

FindMinimalTilings now works with seed values:

In[8]:= |

Out[8]= |

Instead of inputting a mask, the same results can be obtained by inputting all possible templates directly:

In[9]:= |

Out[9]= |

A given set of templates may have no minimal tiling patterns in subsets of a given size:

In[10]:= |

Out[10]= |

Show a tiling pattern for a more difficult tiling set:

In[11]:= |

Out[11]= |

In[12]:= |

Out[12]= |

- 2.0.0 – 08 August 2022
- 1.0.0 – 29 November 2021

This work is licensed under a Creative Commons Attribution 4.0 International License