Questions tagged [polyomino]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
18 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 ...
7
votes
1answer
46 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
28 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, \...
4
votes
0answers
111 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 ...
0
votes
0answers
12 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
34 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
34 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 ...
11
votes
0answers
141 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
101 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 ...
10
votes
2answers
125 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 ...
40
votes
7answers
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
300 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 ...
0
votes
0answers
24 views

Using dominating sets to solve a tetrominoe covering problem

So this question is a consequence of The minimum $N \times N$ square covering problem for $1 \times 4$ shaped tetrominoes where Rob Pratt used dominating sets coupled with an integer linear ...
8
votes
3answers
187 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 ...
1
vote
0answers
33 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 ...
3
votes
1answer
44 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
61 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 ...
2
votes
0answers
64 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 ...
5
votes
1answer
79 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 ...
4
votes
0answers
65 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 ...
2
votes
1answer
77 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
180 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
148 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 ...
14
votes
1answer
176 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 ...
8
votes
2answers
86 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 ...
15
votes
0answers
669 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 ...
3
votes
1answer
76 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
74 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)=\...