Function Repository Resource:

FindMinimalTilings (1.0.0) current version: 2.0.0 »

Source Notebook

Find minimal tilings from a given tile shape

Contributed by: Wolfram Research

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

finds minimal tilings with a pattern of size s for n tiles of a given tileset.

ResourceFunction["FindMinimalTilings"][tileset,n,{w,l}]

finds minimal tilings with a pattern with width w and length l for n tiles of a given tileset.

Details

A pattern is a rectangular array of positive integer values suitable for use in an ArrayPlot.

A tile mask is a subset of positions within a rectangular array, such as the a values in {{a,a,a},{_,a,_}}. This particular mask is also known as the Tetris T shape.

A tile is an array that can contain integers or blanks.

All tiles in a tileset fit in an array of the same size, say {a,b}. If all subarrays of that size in a larger pattern matches a tile in the tileset, then that tileset can be used to make the given pattern.

An all zero tile

leads to an all white or all zero pattern

An all one tile

leads to an all black or all one pattern

The two tiles

lead to a checkboard pattern

. No subset of the tiles will make a larger pattern, so these two tiles produce a minimal tiling.

The tileset

will produce the all white pattern, but the second tile isn't necessary. Therefore, this is NOT a minimal tileset.

The above patterns have a size of 4×4.

The tileset should be specified as a dense array.

An all zero array is a tiling pattern, and a single all zero tile is a minimal tileset for it. Adding another tile to that tileset gives a non-minimal tileset.

Examples

Basic Examples (2)

Generate all possible 2×2 binary tiles:

In[1]:=

Out[1]=

Find subsets of size 2 that can lead to minimal tiling patterns of size 4×4:

In[2]:=

Out[2]=

Find 3-sets of 2×2 tiles leading to minimal tiling patterns of size 8×8:

In[3]:=

Out[3]=

Show the patterns:

In[4]:=

Out[4]=

Show the minimal tilesets leading to these patterns:

In[5]:=

Out[5]=

Scope (2)

Using the resource function TilingPatternPlot, show 4-sets of 2×2 tiles leading to minimal tiling tiling patterns:

In[6]:=

Out[6]=

Show 4-sets of Z-tetrominoes leading to minimal tiling tiling patterns:

In[7]:=

$ArrayPlot /@ KeyMap[ResourceFunction["TilingPatternPlot"], ResourceFunction["FindMinimalTilings"][ Partition[Flatten[{_, #, _}], 3] & /@ (IntegerDigits[#, 2, 4] &) /@ Range[0, 15], 4, 15]]$

Out[7]=

Possible Issues (1)

A given tileset may have no minimal tilings in subsets of a given size:

In[8]:=

$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[8]=

Neat Examples (1)

Show a tiling pattern for a more difficult tiling set:

In[9]:=

$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]]]]]$

Out[9]=

Version History

2.0.0 – 08 August 2022
1.0.0 – 29 November 2021

Related Resources

License Information

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