Function Repository Resource:

FindMinimalTilings

Source Notebook

Find minimal sets of templates for constructing tiling patterns

Contributed by: Wolfram Research

ResourceFunction["FindMinimalTilings"][mask,n,s]

finds a minimal, mask-consistent set of n binary templates and a corresponding tiling pattern of size s×s.

ResourceFunction["FindMinimalTilings"][mask,n,s,c]

allows for c-colored templates, with the binary case recovered by c=2.

ResourceFunction["FindMinimalTilings"][templates,…]

draws pattern constraints from a given set templates.

ResourceFunction["FindMinimalTilings"][…,n,{h,l}]

finds tiling patterns with matrix dimensions h×l.

Details

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.

Examples

Basic Examples (4)

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]:=

With[{res = ResourceFunction["FindMinimalTilings"][{
{1, 1}, {1, 1}}, 2, 4]},
Row[KeyValueMap[Labeled[ArrayPlot[#2,
PixelConstrained -> 20],
Row[ArrayPlot[#, PixelConstrained -> 10
] & /@ #1, Spacer[2]]
] &, res], Spacer[10]]]

Out[3]=

Change the mask shape:

In[4]:=

With[{res = ResourceFunction["FindMinimalTilings"][{
{1, 1, 0}, {0, 1, 1}}, 2, 4]},
Row[KeyValueMap[Labeled[ArrayPlot[#2,
PixelConstrained -> 20],
Row[ArrayPlot[#, PixelConstrained -> 10
] & /@ #1, Spacer[2]]
] &, res], Spacer[10]]]

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]:=

With[{res = ResourceFunction["FindMinimalTilings"][{
{1, 1}, {1, 1}}, 3, 4, 3]},
Grid[Partition[KeyValueMap[
Labeled[ArrayPlot[#2,
ColorRules -> {0 -> Red, 1 -> Green, 2 -> Blue},
PixelConstrained -> 20],
Row[ArrayPlot[#,
ColorRules -> {0 -> Red, 1 -> Green, 2 -> Blue},
PixelConstrained -> 8
] & /@ #1, Spacer[2]]
] &, res], 4], Spacings -> {2, 1}]]

Out[6]=

Scope (2)

FindMinimalTilings now works with rectangular tiling patterns:

In[7]:=

With[{res = ResourceFunction["FindMinimalTilings"][{
{1, 1}, {1, 1}}, 2, {4, 6}]},
Row[KeyValueMap[Labeled[ArrayPlot[#2,
PixelConstrained -> 20],
Row[ArrayPlot[#, PixelConstrained -> 10
] & /@ #1, Spacer[2]]
] &, res], Spacer[10]]]

Out[7]=

FindMinimalTilings now works with seed values:

In[8]:=

With[{res = ResourceFunction["FindMinimalTilings"][{
{1, 1}, {1, 1}}, 2, {4, 6}, {{1, 0}}]},
Row[KeyValueMap[Labeled[ArrayPlot[#2,
PixelConstrained -> 20],
Row[ArrayPlot[#, PixelConstrained -> 10
] & /@ #1, Spacer[2]]
] &, res], Spacer[10]]]

Out[8]=

Properties and Relations (1)

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

In[9]:=

With[{res = ResourceFunction["FindMinimalTilings"][
Partition[#, 2] & /@ Tuples[{0, 1}, 4], 2, 4]},
Row[KeyValueMap[Labeled[ArrayPlot[#2,
PixelConstrained -> 20],
Row[ArrayPlot[#, PixelConstrained -> 10
] & /@ #1, Spacer[2]]
] &, res], Spacer[10]]]

Out[9]=

Possible Issues (1)

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

In[10]:=

$With[{tileset = { {{_, _, 1}, {1, _, 0}, {_, 0, 0}}, {{_, _, 1}, {0, _, 1}, {_, 0, 0}}, {{_, _, 1}, {1, _, 0}, {_, 1, 0}}, {{_, _, 0}, {0, _, 1}, {_, 1, 0}}, {{_, _, 1}, {1, _, 1}, {_, 1, 0}}, {{_, _, 0}, {1, _, 0}, {_, 0, 1}}, {{_, _, 1}, {1, _, 1}, {_, 0, 1}}, {{_, _, 0}, {0, _, 0}, {_, 1, 1}}, {{_, _, 1}, {0, _, 0}, {_, 1, 1}}, {{_, _, 1}, {1, _, 0}, {_, 1, 1}}, {{_, _, 1}, {0, _, 1}, {_, 1, 1}}, {{_, _, 0}, {1, _, 1}, {_, 1, 1}}}}, ResourceFunction["FindMinimalTilings"][tileset, 11, 20]]$

Out[10]=

Neat Examples (1)

Show a tiling pattern for a more difficult tiling set:

In[11]:=

$AbsoluteTiming@With[{tileset = { {{_, _, 1}, {1, _, 0}, {_, 0, 0}}, {{_, _, 1}, {0, _, 1}, {_, 0, 0}}, {{_, _, 1}, {1, _, 0}, {_, 1, 0}}, {{_, _, 0}, {0, _, 1}, {_, 1, 0}}, {{_, _, 1}, {1, _, 1}, {_, 1, 0}}, {{_, _, 0}, {1, _, 0}, {_, 0, 1}}, {{_, _, 1}, {1, _, 1}, {_, 0, 1}}, {{_, _, 0}, {0, _, 0}, {_, 1, 1}}, {{_, _, 1}, {0, _, 0}, {_, 1, 1}}, {{_, _, 1}, {1, _, 0}, {_, 1, 1}}, {{_, _, 1}, {0, _, 1}, {_, 1, 1}}, {{_, _, 0}, {1, _, 1}, {_, 1, 1}}}}, ArrayPlot[ Last[Last[ Normal[ResourceFunction["FindMinimalTilings"][tileset, 12, 20]]]]] ]$