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
10 votes
2 answers
666 views

Can we form a rectangle with integral lengths using an odd number of copies of this domino?

Question: This figure is made up of 6 unit cells. Can we form a rectangle with integral lengths using an odd number of copies of this domino? Rotating and flipping of the figure is allowed. This ...
IraeVid's user avatar
  • 3,161
3 votes
1 answer
372 views

How many Katamino solutions are there on a $5 \times 12$ board?

Katamino is the puzzle of placing twelve polygonal pieces so as to form a $5\times 12$ rectangular array. The pieces consist of all possible arrangements of five connected $1\times 1$ squares. For ...
Hypatia's user avatar
  • 33
0 votes
1 answer
64 views

All the solutions to tile an 8 by 8 square with tetrominoes

I want to fully tile an 8x8 board using the 19 fixed Tetrominoes, allowing repeats of Tetrominoes. For example, this is a valid solution: Here are the 19 fixed Tetrominoes: I am looking for a list ...
Cohensius's user avatar
  • 301
4 votes
1 answer
126 views

Coloring a polyomino tiling so that no two pieces with the same color have a common point

How many colors are enough to color all polyomino tilings so that no two adjacent or touching polyominoes have the same color? In the following example 6 colors are required (each region has a common ...
mezzoctane's user avatar
5 votes
0 answers
134 views

How many domino tilings of a $2n\times 2n$ board are uniquely 3-colourable?

The closed-form formula for the number of domino tilings of a $2n\times 2n$ board is known to be $$\prod_{j=1}^{n}\prod_{k=1}^{n}\Big{(}4\cos^2\frac{\pi j}{2n+1} + 4\cos^2\frac{\pi k}{2n+1}\Big{)}.$$ (...
Giedrius Alkauskas's user avatar
3 votes
1 answer
81 views

Largest number of corner pieces in an $m \times n$ grid?

The other day the following combinatorics problem popped into my head: Given an $m \times n$ grid, how many corner pieces can fit in it without overlapping? A corner piece is defined as such: ...
David's user avatar
  • 31
15 votes
2 answers
723 views

Union of two disjoint congruent polygons is centrally symmetric. Must the polygons differ by a 180 degree rotation?

Let $P$ be a polygon with $180^\circ$ rotational symmetry. Let $O$ be the center of $P$ and suppose $P$ is dissected into congruent polygons $A$ and $B$. Must the $180^\circ$ rotation around $O$ ...
greenturtle3141's user avatar
4 votes
2 answers
166 views

A game from fault lines in domino tilings

It is known that, for any tiling of a $6\times6$ rectangle with dominoes, there must exist a fault line, or a line cutting the square without cutting any domino. (There is a nice elementary proof of ...
Akiva Weinberger's user avatar
1 vote
0 answers
184 views

Recurrence relation convex polyominoes of perimeter $2n+8$

This question concerns Exercise 4.24 from generatingfunctionology. Find a three term recurrence relation, whose coefficients are polynomials in $n$, that is satisfied by $$ f(n) = (2n+11)4^n - 4(2n+1) ...
girishrussel's user avatar
1 vote
1 answer
51 views

Name of polyomino using shapes other than a square [closed]

Is there a name to describe polyominoes that use shapes other than a square? Wolfram alpha could not answer this.
The Empty String Photographer's user avatar
5 votes
1 answer
145 views

Tile homotopy and T-tetromino packing of rectangles

From my old question (Which rectangles can be tiled with L-trominos, when only two orientations are allowed?), I learned a very interesting way to deal with tiling problems. I was wondering about T-...
Mykola Hordeichyk's user avatar
4 votes
0 answers
86 views

Which pentacube oddities can be solved or improved?

A few years ago I studied pentacube oddities. A pentacube is a polycube with 5 cells, and an oddity is an arrangement of an odd number of copies of a polyform that has binary symmetry (or stronger). ...
George Sicherman's user avatar
4 votes
2 answers
121 views

Which rectangles can be tiled with triangles $T_n$, when only two orientations are allowed?

This question is a generalization of another question asked here: Which rectangles can be tiled with L-trominos, when only two orientations are allowed? A triangle $T_n$ is a polyomino with columns on ...
Herman Tulleken's user avatar
3 votes
1 answer
686 views

A recursive relation for the number of ways to tile a 2 x n grid with 2x1, 1x2, 1x1 and 2x2 dominos

I'm trying to solve this problem: In how many ways can you cover a 2xn grid with 1x1, 1x2, 2x1, 2x2 dominos? And here is my attempt: Let a(n) be the number of ways we can cover the grid. Then if we ...
Labi's user avatar
  • 93
1 vote
1 answer
64 views

Area of math dealing with sliding tiles?

I am not sure if this may be better suited for Computer Science, but I have recently gotten interested in problems having to do with different shapes of tiles sliding around in a grid. For example, ...
Jeff Bass's user avatar
  • 221
0 votes
1 answer
240 views

Tiling of a grid using triominoes

I want to tile a $12 \times 12$ grid using L-shaped triominoes. There must be no overlaps or missing spaces, and I know that it is possible to do so. Now, I want to know about a new condition: each ...
user avatar
9 votes
2 answers
461 views

Which rectangles can be tiled with L-trominos, when only two orientations are allowed?

This is a question that I got after reading this: https://www.cut-the-knot.org/Curriculum/Games/LminoRect.shtml. (This link already gave me the same result as theorem 1.1 of the article https://www....
Mykola Hordeichyk's user avatar
4 votes
0 answers
55 views

Are maximum-density fixed polyomino packings always isohedral?

Consider, for a polyomino $P$ made from $n$ unit squares joined at the edges, the arrangements of non-overlapping translations of $P$. Sometimes we can cover the infinite plane with such translations ...
RavenclawPrefect's user avatar
16 votes
1 answer
204 views

Does the $Z$ pentomino tile a 3D box?

Some polyominoes are rectifiable, meaning they can tile some rectangle in the plane. For instance, the following tiling shows the $Y$-pentomino is rectifiable:                                          ...
RavenclawPrefect's user avatar
1 vote
1 answer
107 views

Prove that any polyomino of size n > 1 and perimeter p can be built by adding 1 square to some other polyomino of size n-1 and perimeter p or p-2.

It is well known that any polyomino of size n > 1 can be built by adding a square to a smaller one. Can the same thing be proven if we add the criterion that said smaller polyomino has a perimeter ...
John Mason's user avatar
7 votes
1 answer
215 views

Is there a polyhedron all of whose faces are distinct polyominoes?

The title is pretty much the complete question. An example of this would (I believe) have to be a nonconvex polycube. If there is one, I am also interested in the smallest example. The analogous ...
Glen Whitney's user avatar
  • 1,352
12 votes
1 answer
171 views

Finding all 15-ominoes that tile the plane and have distinct internal adjacencies

Problem Description: This problem oddly came up in Minecraft with some friends. Not sure what the best terms are; but that's partly why I'm here. So a polyomino is built up from squares. This problem ...
WhiteStoneJazz's user avatar
2 votes
1 answer
93 views

Can a scaled $L$-tromino be cut into two congruent polyominoes?

The $L$-tromino can trivially be cut into two congruent trapezoidal pieces: It can also be trivially cut into three squares, and into four other $L$-trominoes of half the side length. I am curious ...
RavenclawPrefect's user avatar
1 vote
1 answer
411 views

Can the following figures be divided into 6 equal parts?

This question asks whether a figure can be divided into $2$ and $3$ equal parts, but not $6$. It is in turn based off of an earlier puzzling.SE question. One natural approach is to consider the case ...
Evan X's user avatar
  • 67
3 votes
2 answers
252 views

How to find winning Strategy for 4 celled animals of Harary's generalized tic tac toe

A polyomino is a structure made of unit squares joined along their sides. A single square is called a monomino. Two make a domino. Three join in two different ways to make two trominoes. Let's call ...
Rajat Kumar's user avatar
0 votes
0 answers
57 views

Finding the largest polyominoes that can fit in a rectangular space

I am making a program that generates $3$ random polyominoes of size $x \le n$ (referring to the number of squares in the shape). Each polyomino fits within a space: $k \times k$ ($k=6$ in my case). I ...
Radiant_Waffle's user avatar
6 votes
3 answers
261 views

Determine whether a polyomino has a hole

Suppose I know the $(x,y)$ coordinates of the corners of all the unit squares making up a connected polyomino. Is there a simple/elegant way to determine if the polyomino has a hole in it, merely by ...
Nick C's user avatar
  • 171
1 vote
1 answer
60 views

Are there polyominoes which tile half-plane but tile no strip with any width?

In Golomb's hierarchy: If a polyomino tiles strip then tiles half-plane. (Ok, it's trivial.) But what is with other direction? Is there an example which tiles half-plane but doesn't tile any strip?
Máté Belényesi's user avatar
4 votes
1 answer
125 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 ...
RavenclawPrefect's user avatar
6 votes
2 answers
155 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 ...
RavenclawPrefect's user avatar
8 votes
2 answers
241 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 ...
RavenclawPrefect's user avatar
7 votes
1 answer
163 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 ...
RavenclawPrefect's user avatar
7 votes
2 answers
315 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: ...
Glen Whitney's user avatar
  • 1,352
20 votes
1 answer
404 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. ...
RavenclawPrefect's user avatar
8 votes
1 answer
241 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 ...
Peter Kagey's user avatar
  • 5,032
9 votes
1 answer
257 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 ...
Herman Tulleken's user avatar
1 vote
1 answer
114 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, ...
Robert D-B's user avatar
  • 2,206
10 votes
2 answers
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 ...
RavenclawPrefect's user avatar
3 votes
1 answer
112 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 ...
RavenclawPrefect's user avatar
14 votes
0 answers
165 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 ...
RavenclawPrefect's user avatar
8 votes
1 answer
172 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 many cases, it can do so by forming a two-tile "patch" that tiles the plane. For instance, with the T pentomino: Is there always a ...
RavenclawPrefect's user avatar
24 votes
1 answer
693 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 ...
RavenclawPrefect's user avatar
8 votes
1 answer
591 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 ...
RavenclawPrefect's user avatar
5 votes
0 answers
81 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 ...
RavenclawPrefect's user avatar
9 votes
3 answers
358 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 ...
RavenclawPrefect's user avatar
6 votes
1 answer
255 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 ...
Mahdi's user avatar
  • 429
6 votes
0 answers
88 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 ...
Erich Friedman's user avatar
0 votes
1 answer
764 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 ...
John Carter's user avatar
1 vote
1 answer
184 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 ...
user3479472's user avatar
8 votes
1 answer
85 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$-...
Peter Kagey's user avatar
  • 5,032