Questions tagged [polyomino]

A polyomino is an edge-connected union of grid-aligned squares in the plane; in some contexts, they may be viewed as subsets of Z^2. This tag is for questions about the properties of polyominoes, including questions about how they tile different shapes, how they may be dissected, and assembly puzzles with a given set of polyominoes.

Filter by
Sorted by
Tagged with
5
votes
1answer
65 views

What is the minimum size of a region that can be tiled by every polyomino on up to $4$ cells?

I am interested in regions that can be tiled by all $k$-ominoes for each $k\le n$. If we take $n=3$, it is obvious that the $2\times 3$ rectangle is the minimal region that can be tiled by the ...
4
votes
2answers
65 views

Can the $X$ pentomino and the $2\times 2$ square mutually tile any nontrivial cofinite region?

It is easy to see that there is no nonempty finite region in the square grid that can be tiled by both the $X$ pentomino and the $2\times 2$ square: if we look at any cell of maximal $y$-coordinate, a ...
7
votes
2answers
95 views

Can every polyomino of even size be tiled by $L$-trominoes when scaled up by a factor of $3$?

The $L$-tromino does not tile a $3\times 3$ square. However, it can tile $3\times3$ squares glued together in various ways:                                                                     I am ...
6
votes
0answers
49 views

How many fixed polyominoes does it take to force an aperiodic tiling of the plane?

A longstanding open problem asks whether there is a single connected tile that only tiles the plane aperiodically. As far as I know, this is still open even in the case of polyominoes: we do not know ...
7
votes
2answers
153 views

Smallest non-space-filling polycube?

The title nearly says it all: what is the fewest number of cubes that can be fused face-to-face into a polyhedron that does not fill space? The smallest that seemed like a sure non-tiler to me was 9: ...
18
votes
1answer
247 views

How densely can the :…: polyomino fill the plane?

This is a follow-up to the question How good can a "near-miss" polyomino packing be?. Let $P$ be the heptomino shown below: I am interested in the packing density of $P$ on the square grid. ...
7
votes
0answers
59 views

Octahedron to tetrahedron ratio in generalized polyominoes in the tetrahedral-octahedral honeycomb

Drake Thomas and I have proposed a sequence A343909 to the On-Line Encyclopedia of Integer Sequences (OEIS), which counts "generalized polyforms": generalizations of free polyominoes (Tetris ...
6
votes
1answer
117 views

Are the only polyominoes that can tile triangles right trominoes?

A triangle $T(n)$ is a polyomino with columns on the same base with lengths $1, 2, 3, \cdots, n$. In this slide deck (original PPT, images may be corrupt), Friedman looks at tilings of these triangles ...
1
vote
1answer
82 views

Can you tile a heart with dominoes?

For a positive integer $n$, let $R_n$ be the set of integer lattice points $(x, y)$ such that $0 \leq x < 2n$ $0 \leq y < 4n$ $x \leq y$ $y \leq 5n - x$ $y \leq x + 3n$, and let $L_n = \{(-x, ...
10
votes
2answers
2k views

If a subset of the square grid can be tiled by $1\times n$ rectangles for every $n$, can it be tiled by infinite rays?

Suppose that we have some set $S$ of grid-aligned squares in the plane; equivalently, we can think of our set as $S\subset \mathbb{Z}^2$. Suppose that for every positive integer $n$, $S$ can be tiled ...
3
votes
0answers
42 views

If an animal tiles the plane via translation, can it do so in a lattice configuration?

It is known that if a polyomino tiles the plane using only translated copies, then it has at least one such tiling where the centroids of each tile form a lattice; see for instance the paper Arbitrary ...
13
votes
0answers
122 views

Random domino tilings: Is this distribution well-defined, and how can it be sampled from?

I'd like to ask questions about a "random domino tiling of the plane". However, it's not quite obvious how to go about precisely specifying what this means. My first instinct was to do ...
4
votes
1answer
64 views

If a polyomino tiles the plane, is there necessarily a larger tiling polyomino formed by two copies of it?

Say that we have a polyomino $P$ which tiles the plane. In may cases, it can do so by forming a two-tile "patch" which tiles the plane. For instance, with the T pentomino: Is there always a ...
21
votes
1answer
431 views

What is the smallest polyomino that can't surround a $1\times 1$ hole?

Given a polyomino $P$, we can ask if it is possible for disjoint copies of $P$ to surround a single cell in the square grid - i.e., for the complement of their union to have a connected component of ...
8
votes
1answer
91 views

How quickly can you mess up a domino tiling in 3D?

Suppose that we are trying to tile $\mathbb{Z}^3$ with dominoes, i.e., two face-adjacent cubes. We start going about this haphazardly, laying dominoes in random spots. How long can we keep this up ...
4
votes
0answers
50 views

What is the asymptotic behavior of large polyominoes? How many of them tile the plane?

The free polyominoes on $n$ cells can be classified into three categories: those with holes, those that tile the plane, and those without holes that do not tile the plane. (No polyomino with holes ...
7
votes
3answers
173 views

How good can a “near-miss” polyomino packing be?

Given a polyomino $P$ with $n$ cells, we can ask about its maximal packing density $\delta_P$ in the plane (perhaps the limsup if we are concerned about convergence issues, though I don't think this ...
6
votes
1answer
223 views

How many regions can be selected in a chess board?

How many regions can be selected in a 8 by 8 chess board? Definition of region: A region is a set of cells that are all connected together(by edge). i.e. a possible region: I want to run(or do ...
5
votes
0answers
31 views

Arrangements of triominoes and tetrominoes where each touches polyominoes of total area 4 times their own

Consider arrangements of triominoes and tetrominoes on a grid where each polyomino touches polyominoes of total area 4 times their own. (Here "on a grid" means the vertices of the ...
0
votes
2answers
133 views

Filling tiles into a space. [closed]

(Note: If a better title can be generated, please make an edit) Considers any shape that can be divided into multiple, congruent, smaller shapes. The above example shows a 4x6 rectangle divided into ...
0
votes
1answer
55 views

In how many ways $A_n$ can we cover a $2 \times n$ rectangle with $1 \times 2$ and $2 \times 2$ polyominoes?

This is my answer: (if rotations are allowed) Let An be the number of ways to completely cover a 2 times n checkerboard with 1x2 and 2x2 dominoes There 3 conditions: The upper right corner can be ...
1
vote
1answer
90 views

Proving T-tetrominoes fit in a chessboard

I'm fairly new to discrete math, and I wasn't sure how to prove the following. Prove that if $n\geq 2$, then every $2^n \times 2^n$ chessboard can be tiled with non overlapping T-tiles. If I draw ...
8
votes
1answer
73 views

Counting polysticks on the $n$-cube.

Over at Code Golf Stack Exchange, I put up a challenge asking people to count, among other things, the number of ways to take an $n$-cube and color $k$ (connected) edges up to isometries of the $n$-...
0
votes
1answer
43 views

Algorithm: Counting elements of Polyomino coverings

Given a set of free Polyominoes $\mathcal{P}$ (translation, flipping and rotating of pieces is allowed) and a test shape $S$ that is also a valid Polyomino, I am trying to find an algorithm $f(S, \...
6
votes
0answers
131 views

Is there a devious starting position to this tile puzzle?

I recently asked a question on the puzzling site, where I placed three colored T-tetraminos on the plane and asked for a tiling of the plane with T-tetraminos that fulfilled the following three ...
1
vote
0answers
20 views

Examples of fusenes that are not polyhexes

OEIS sequence A108070 describes Number of fusenes with n hexagons. OEIS sequence A000228 describes Number of hexagonal polyominoes with n cells. These sequences first disagree at $A108070(7) =...
0
votes
1answer
43 views

dominoes in $4\times4$ square grid

is there an organized way to count the possibilities, or just trial and error. Thanks!
1
vote
0answers
41 views

Closed Figures Made Up of Unit Squares

This is my first question. I am wondering if there is a formula to find the number of non-congruent figures of area n that are made up of 1 by 1 non-overlapping squares, in which any square must ...
12
votes
0answers
201 views

Are there polyominoes that tile L-shapes and not rectangles? (Except L-shapes)

An L-shape is a polyomino with 6 vertices (5 convex, 1 concave). I am investigating polyominoes that can tile some L-shape. Two non-square or three square rectangles can be put together to make an ...
7
votes
2answers
118 views

Minimal covering of a $5 \times 5$ square with $T$ shaped tetrominoes.

The title almost completely describes the problem. So you have a $5 \times5$ square. You have to fit the minimum number of $T$ shaped tetrominoes such that no more $T$ shaped tetrominoes can be fitted ...
12
votes
2answers
233 views

Are there polyominoes that can't tile the plane, but scaled copies can?

I'm wondering where there is a finite set $\mathcal{T}$ of polyominoes that are pairwise similar that can tile the plane, but a single element from the set cannot. (All orientations are allowed.) To ...
44
votes
9answers
4k views

Can any number of squares sum to a square?

Suppose $$a^2 = \sum_{i=1}^k b_i^2$$ where $a, b_i \in \mathbb{Z}$, $a>0, b_i > 0$ (and $b_i$ are not necessarily distinct). Can any positive integer be the value of $k$? The reason I am ...
14
votes
3answers
396 views

How to classify polyominoes by shape

I am trying to find a robust way to classify and distinguish polyominoes. I would like to write a simple algorithm that could identify similar free polyominoes (under translation, rotation, reflection ...
9
votes
3answers
371 views

The minimum $N \times N$ square covering problem for $1 \times 4$ shaped tetrominoes

OK, so me and my friend are working on a problem in which you do the opposite to trying to stuff as many of the I shape tetrominoes in a square as possible. Trying to find the smallest number of I ...
2
votes
0answers
47 views

Why do figures that can be tiled with two different polyominoes tend to be symmetric?

Two polyominoes are compatible when there is a figure that can be tiled by both; a smallest one is called a least common multiple. In looking through tables of these least common multiples of ...
4
votes
1answer
61 views

How many colors are necessary for a W-polyomino to never cover a color more than once?

A W-polyomino is a polyomino with 2 cells in each row (except possibly the last, which may have one cell), and each row offset once cell to the right. Below are the first few W polyominoes. How many ...
4
votes
1answer
73 views

Percolation related counting problem

I was trying to look into the following problem, which I intend to use for a lemma for a bigger problem. The question is: For the 2-dimensional integer lattice, what are some good lower and upper ...
3
votes
0answers
88 views

Finding all rectangles with fault-free tilings of the P-pentomino

I am trying to find all rectangles with fault-free tilings of the P pentomino. (A fault is a vertical or horizontal line inside the rectangle that is not crossed by any tiles; a fault-free tiling is ...
7
votes
1answer
106 views

Are all polyominoes with even sides tileable by dominoes?

In this paper (Section 8) the author states that it is "trivial" to show that a polyomino with all sides (including the sides of holes in the polyomino) even has a tiling by dominoes. It is indeed ...
5
votes
0answers
70 views

Where can I find out more about the nature of holes in plane regions?

Over the last few months I have been studying tilings of regions by polyominoes (mostly dominoes). I have been putting my findings together, mostly in the form of proving various things about ...
3
votes
1answer
96 views

If we remove a strip polyomino from a strip polyomino, is the result tileable by dominoes?

A strip polyomino is a polyomino through which we can draw a path $C_1, C_2, \cdots C_k$, such that all the cells in the polyomino is in the path, and no cell is repeated in the path, and $C_i$ and $...
4
votes
1answer
191 views

Can a $10\times 10$ square be entirely covered by 25 $T$-shape bricks?

Let $ABCD$ be a square in which length of a side is $10$ meters. Suppose that we have $T$-shape brick which consists of $4$ smaller squares in which a side of each smaller square has length of $1$ ...
2
votes
1answer
228 views

Find a great strategy to a pentomino type game

I have a game. Given an $8\times 8$ square and a set, which contains the pentominoes and four $1\times 1$ squares. Players alternately pick one item from the set. Then players (starting with the ...
15
votes
1answer
218 views

Is every “even” polyomino with one hole tileable by dominoes?

In Conformal Invariance of Domino Tiling the author defines an even polyomino as a polyomino with all corners (of all borders, inside and outside) "black" if the polyomino is colored with the ...
9
votes
2answers
98 views

Can all convex $3n$-iamonds be tiled by $3$-iamonds?

Background A polyiamond is a plane figure constructed by joining together equilateral triangles of the same size along their edges. The number of convex polyiamonds is given by A096004. Based on ...
16
votes
0answers
751 views

Smallest region that can contain all free $n$-ominoes.

A nine-cell region is the smallest subset of the plane that can contain all twelve free pentominoes, as illustrated below. (A free polyomino is one that can be rotated and flipped.) A twelve-cell ...
4
votes
1answer
82 views

Polyominoes with the most reflex exterior angles

What is the polyomino with the largest number $n$ of reflex (i.e., $270^\circ$) exterior angles that can fit in a $L \times L$ grid? How does $n$ scale with $L$?
3
votes
2answers
85 views

Generalization of pentomino-rectangle tiling

It is very well known that there are $12$ pentominos and they can tile $6 \times 10$, $5 \times 12$, $4 \times 15$ and $3 \times 20$ rectangles. Now, let's define a function for simplify this. $$t(n)=\...
3
votes
2answers
871 views

Placing tetrominos in square, maximum size

I am currently coding an algorithm which places a list of Tetrominos (tetris pieces) in the smallest square possible. My question is : is there a mathematical way to know the maximum size (upper ...
6
votes
1answer
498 views

Tiling squares with L-Trominoes

Is there a simple proof that any square besides a 3x3 square with area divisible by 3 is tileable with L-trominos?