Questions tagged [tiling]
The tiling tag has no usage guidance.
36
questions
1
vote
0
answers
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 (...
- 11
3
votes
2
answers
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
2
votes
1
answer
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
0
answers
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 ...
5
votes
0
answers
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 ...
0
votes
1
answer
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 ...
- 9
-1
votes
2
answers
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
1
answer
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)
...
- 13
5
votes
4
answers
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
1
answer
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
1
answer
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 ...
- 165
7
votes
0
answers
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 ...
- 4,387
3
votes
1
answer
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
1
answer
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
3
votes
1
answer
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
1
answer
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 ...
- 31
1
vote
0
answers
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
3
votes
1
answer
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
0
votes
2
answers
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
3
votes
1
answer
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 ...
- 53
1
vote
1
answer
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
3
votes
1
answer
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
3
votes
1
answer
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 ...
- 31
19
votes
3
answers
443
views
How many cookies in the cookie box? -- Tiling stars
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
0
answers
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
2
votes
0
answers
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
2
votes
1
answer
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
2
answers
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
0
answers
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 ...
- 93
5
votes
1
answer
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. ...
- 153
3
votes
0
answers
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
5
votes
1
answer
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
3
votes
1
answer
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
12
votes
2
answers
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
26
votes
2
answers
2k
views
Is Dominosa NP-Hard?
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 ...
- 481
19
votes
1
answer
1k
views
Are 'zero-one' jigsaw puzzles NP-complete?
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 ...
- 2,372