# Questions tagged [tiling]

The tag has no usage guidance.

36 questions
Filter by
Sorted by
Tagged with
1 vote
72 views

### NP-complete problems with aperiodic Wang tiles

Consider the problem of tiling a rectangular region with a given set of Wang tiles. It is well-known that this problem is NP-complete: every NP problem can be encoded as some form of tiling problem (...
96 views

### Maximize enclosed area of given figures on 2d grid

I need to solve an optimization problem for a given set of polyominoes, for example the five Tetrominoes known from Tetris. The goal is to place each one of the figures on the 2d grid, so the area ...
• 33
163 views

### Minimizing number of MxM squared tiles in an infinite grid covered by any part of a shape

Without restriction (e.g. continuity or convexity are not guaranteed), we're given an W x H raster-based shape that needs to be placed on an infinite tiling of <...
1 vote
24 views

### How to cover a surface with a predefined set of objects

I'm making a program that's supposed to be able to find pieces of wood in a dataset to cover a surface. For now I'm focusing on parallelepipedic shapes to simplify the problem (eventually I'd like it ...
56 views

### Efficient algorithm to compute the Heesch number of a shape

The Heesch number of a shape is the maximum number of layers of copies of the same shape that can surround it. For example the following shape (in the center) has a Heesch number of 4, because we can ...
100 views

### Dynamic Programming - Tiling Question

I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which ...
612 views

### Constructing a rectangle of size nx2 with dominos and L-shaped trominos [duplicate]

The Question is from DP tiling a 2xN tile with L shaped tiles and 2x1 tiles? I want an explanation about this question or theory
• 9
1 vote
50 views

### Calculating complexity for recursive algorithm with codependent relations

I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2x1 dominoes: F(n) = F(n-2) + 2*G(n-1) G(n) = G(n-2) + F(n-1) ...
1k views

### 3xN tiling problem with blocks of size 3x1 or 2x2

I know there are a number of different tiling problems and some of them have been discussed here: Number of ways of tiling a 3*N board with 2*1 dominoes problem Domino and Tromino Combined Tiling DP ...
• 161
1 vote
91 views

### Are tiny point-symmetric grids of two Pentominos impossible to solve?

The game of Pentomino is a tiling puzzle game played on a grid. A Pentomino piece is a two dimensional shape of five non-diagonally connected tiles. There are exactly 12 unique pieces (ignoring ...
• 329
1 vote
934 views

### Number of ways of tiling a 3*N board with 2*1 dominoes problem

I came across this problem, Tiling with Dominoes and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a ...
541 views

### Algorithms to generate random nowhere-neat rectangulation?

I want to generate random rectangular partition of a given $m*n$ rectangle under the constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle ...
124 views

### How to generate snowflakes of a fixed area as challenges for the FridgeIQ puzzle?

I have been presented a set of FridgeIQ by a friend and she has planted an idea in my head. FridgeIQ is a geometric disection puzzle consisting of 16 polygonal tiles as seen in the terrible picture ...
1 vote
127 views

### Is there an efficient algorithm for solving tiling puzzles?

As an example of the type of problem, consider Stewart Coffin's Cruiser puzzle: Let R be a 48 × 31 rectangle. Let T be a 30°-60°-90° triangle with hypotenuse 34.565 (so legs are 17.2825 and 29....
• 213
1k views

### DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?

https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php The second question in the above link requires us to fill an 2xN grid with tiles of dimension 2x1 and an L shaped tile. ...
• 131
1 vote
97 views

### Filling a 3x3 board with connected tiles

long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern ...
1 vote
20 views

### Given a JPG of a wallpaper, how can I find the smallest section which contains the pattern?

I recently made the photo of tapestry, but I am not able to identify the smallest patch which contains the pattern. Now I wonder: How could I write a program that does so? A first step could be ...
• 2,340
874 views

### Domino tiling of a 2xN rectangle in O(ln n)

I solved this problem using Dynamic Programming in $\mathcal{O}(n)$ time. I found that is equivalent to the Fibonacci Numbers. $F(0) = F(1) = 1$ $F(n) = F(n-1)+F(n-2)$ Where the $F(n-1)$ term is ...
• 233
361 views

### Modeling tiling problems as SAT problems

I read that tiling problems can be modeled as satisfiability problems (2-SAT?), but the author did not explain how. Is this true? What would be an example? By a "tiling problem" I mean you have a ...
• 668
3k views

### Domino and Tromino Combined Tiling

If I have a nx2 grid which I need to fill using 2x1 dominoes and L shaped trominoes in any combination, how many different combinations are possible? I am aware that when only 2x1 dominoes are used ...
1 vote
344 views

### Wang tile turing machine tile placement

I've read numerous links on the fact that wang tiles are turing complete, and details about them (links at end). However there is little talk of how to actually place the tiles. One place i read ...
• 1,318
189 views

### For tiling simply connected regions with shapes beyond just rectangles, is there a lower # of tile shapes needed for NP-completeness?

In "TILING SIMPLY CONNECTED REGIONS WITH RECTANGLES" by Igor Pak and Jed Yang, they show there is a set of "no more than $10^6$ rectangles" such that the problem of tiling an arbitrary simply ...
• 1,691
46 views

### n-polygon lattice datastructure?

I'm trying to simulate a boardgame what can be played on a board with an arbitrary lattice, anything from triangles to heptagons to 37-sided regular polygons is allowed. Moreover the shape of the ...
443 views

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ...
• 71.8k
1 vote
80 views

### Algorithm to generate graph of specific known form

I am trying to generate a graph (the structure with edges and nodes), that as a structure like an Order-7 triangular tiling of specified diameter around a central node. http://en.wikipedia.org/wiki/...
• 213
54 views

### Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square?

This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula ...
• 1,691
81 views

### Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes?

So I was thinking about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with $2 \times 1$ dominoes. If $m \leq n$, then we can use recursion on $n$ ...
• 1,691
1 vote
310 views

### choice of data structure for domino tilings

A domino tiling is a tesselation of a region in the plane by 2 × 1 squares. What is a good data type for storing and manipulating such objects? In my current manipulation, use an array to ...
• 1,911
1 vote
99 views

### Computational approach deciding whether a set of Wang Tile could tile the space up to some size [closed]

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
1k views

### How to convert a Turing Machine program to a tiling using Wang Tiles?

This is a cross-post from a post on MathSE due to lack of answers. To illustrate my question I provide the following example. The website Online Turing Machine provides a Turing Machine simulator. ...
139 views

### Packing rectangles to generate a sprite sheet

I am writing a sprite sheet generator tool in adobe AIR, and I have to force with the question: How to pack a collection of 2D rectangles to smallest possible 2D rectangle with power of two. (like ...
• 899
807 views

### What is the minimum square partition of an almost-square rectangle?

This question is motivated by an older question about tiling an orthogonal polygon with squares. It is a generalisation of my former question about how to prove that the minimum square partition of a ...
• 6,171
252 views

### How to prove that the minimum square partition of a 3X2 rectangle has 3 squares

This question is motivated by an older question about tiling an orthogonal polygon with squares.         Given a $3\times 2$ rectangle like the first image, the ...
• 6,171
2k views

### Tiling an orthogonal polygon with squares

Given an orthogonal polygon (a polygon whose sides are parallel to the axes), I want to find the smallest set of interior-disjoint squares, whose union equals the polygon. I found several references ...
• 5,844
Dominosa is a relatively new puzzle game. It is played on an $(n+1)\times(n+2)$ grid. Before the game begins, the domino bones $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$ are ...
I'm interested in a slight variant of tiling, the 'jigsaw' puzzle: each edge of a (square) tile is labeled with a symbol from $\{1\ldots n, \bar{1}\ldots\bar{n}\}$, and two tiles can be placed ...