# Questions tagged [tiling]

The tag has no usage guidance.

24 questions
1answer
19 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 ...
0answers
99 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 ...
1answer
35 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 ...
1answer
46 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....
1answer
64 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 ...
0answers
17 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 ...
1answer
431 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 ...
2answers
178 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 ...
1answer
170 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 ...
1answer
86 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 ...
1answer
36 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 ...
3answers
387 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 ...
0answers
73 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/...
0answers
52 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 ...
1answer
76 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$ ...
2answers
224 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 ...
0answers
82 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 ...
1answer
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. ...
0answers
124 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 ...
1answer
554 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 ...
1answer
208 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 ...
2answers
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 ...
2answers
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 ...
1answer
743 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 ...