Hot answers tagged

22

${\rm D{\small OMINOSA}}$ is NP-hard Playing the game is an optimization problem; finding a valid domino tiling such that it covers all the squares. The decision version of this problem is: Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles? Obviously, the optimization problem, the problem of actually finding a ...


16

I will try to show this problem is NP-hard, by reduction from $\text{Planar-}3\text{-SAT}$. Reduction from $\text{Planar-}3\text{-SAT}$ Some basic Gadgets Gadgets are internal configurations of geometry that will allow us to construct gates for use in a circuit, to which we will reduce $\text{Planar-}3\text{-SAT}$. 4X3-gadget This gadget has two valid ...


15

Let me answer your question partially for the hexagram case. You can make the following tiling $\hskip1.2in$ By this you will cover 12/14=6/7 of the plane (count the triangles in the dashed quadrilateral). Is this optimal? I would think so. Although I am not giving a proof I will provide some arguments. One can ask, how good we can fill the space (...


9

Note: This is a continuation and revision of my other answer. Problems with the reduction Recall the decision problem: Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles? So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables. But: Our reduction requires a lot of unique variables, much more than $\...


8

An old paper I coauthored establishes that the covering problem is polynomial for a polygon without holes, and NP-complete with holes. We showed that a key underlying graph is chordal. Please note: the algorithm is polynomial in the number $N$ of unit squares in the polygon, $O(N^{3/2})$. "Covering orthogonal polygons with squares." L. J. Aupperle and H....


6

There is a mutual recursion in two variables $f(n)$ for the $n\times 2$ grid and $g(n)$ for the $n\times 2$ grid with a single square sticking out. It does not matter where the square sticks out (first or second row) because their number of tilings is the same. Note the trominos indeed come in pairs, but they do not need to form a $3\times 2$ block. You ...


6

A similar question was asked on Mathoverflow. The commenters mentioned a paper of Kenyon, which shows that the minimum number of squares required to tile a $w \times (w-1)$ rectangle is $\Theta(\log w)$. See also a related paper of Walters. You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).


5

Here is a systematic way to approach it. I suggest you define three values: $A_0(n)$ is the number of ways to tile a $3 \times n$ region. $A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered. $A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of ...


4

From my answer on math.SE: If you just used $1\times2$ rectangles, then this is same as finding the number of matchings in the $m \times n$ rectangle graph, and a formula for that has been given by Kastelyn: $$ \sqrt{\left|\prod_{j=1}^{m}\prod_{k=1}^{n} \left(2 \cos \frac{\pi j}{m+1} + 2i\cos \frac{\pi k}{n+1}\right)\right|}$$ This was done, by mapping ...


4

This counting problem is one of the classical problems that can be solved efficiently by dynamic programming. Since we should find the number of ways to fill a 3 by $n$ rectangle, a natural set of subproblems is the number of ways to fill a 3 by $m$ rectangle, where $m\le n$. However, it turns out it is practically impossible to find a recurrence relation ...


3

Let $f[m]$ be the number of ways to cover the shape shown below, an $m$ by $2$ rectangle. Our ultimate goal is $f[n]$. ┌───────────┐ 2 │ │ └───────────┘ m Let $g[m]$ be the number of ways to cover the first shape shown below, an $m$ by $2$ rectangle with an extra 1x1 square at the top-right corner. By symmetry, $g[m]$ is ...


3

The case $w = 3$ is somewhat boring. Here is how to show that you need at least three squares. There is some square $S_1$ touching the bottom-left corner. There is some square $S_2$ touching the bottom-right corner. These squares must be different. At least one of them doesn't go all the way to the top, and so one of the other two corners remains uncovered, ...


3

Since you mentioned you are interested in solving this problem for small values of $n$, I would suggest that you try implementing this in a SAT solver or as an integer linear program (ILP). Either one will be able to encode the constraints, but in a slightly different way: For SAT, there is a very clean encoding of the choice of which tile goes into each ...


3

There is an alternative, more compact kind of array representation which might be better if you are working with diamonds as defined in the paper you linked (for axis aligned rectangles you need to find the smallest covering diamond). The idea is to checkerboard the plane and assign a 2-bit number to each "black" cell, such that the number represents the ...


3

In your second attempt you tried to fixate the $(k+1)$th term. But instead of the two cases 1 2 ... k k+1 k+2 ... n | | and 1 2 ... k k+1 k+2 ... n ----- ----- there exist a third case: 1 2 ... k k+1 k+2 ... n ---- ---- So if $n = 2 k$, then you have $f(k)f(k-1)$ for the first case, $f(k)f(...


3

(partial answer) via wikipedia, the conversion/reduction of TMs to Wang tiling was 1st proven in this paper, & there are possibly later simplifications: Berger, R. (1966). "The undecidability of the domino problem", Memoirs Amer. Math. Soc. 66 (1966). (Coins the term "Wang tiles", and demonstrates the first aperiodic set of them).


3

Found their paper on ArXiv. It is quite easy to go from coloured Wang tiles to uncoloured shapes by introducing zig-zag boundaries, like a jig-saw, as illustrated in their Figure 3. So then still 23 tiles are needed, as colours are simply replaced by boundaries. Their contribution is to move from boundaries to only rectangular tiles. The authors state in ...


2

The board you want to draw is a planar graph whose faces (enclosed areas between edges) are the polygonal tiles: call this $G_\mathrm{b}$. The data structure you have in memory is a graph $G_\mathrm{m}$ whose vertices are the tiles and whose edges are the adjacency relation on the tiles. This graph is known as the dual of $G_\mathrm{b}$. So, you need to ...


2

One example of a tiling problem that was successfully attacked by reducing it to a SAT instance was rectangular grid coloring. In "Extremely Complex 4-Colored Rectangle-Free Grids: Solution of Open Multiple-Valued Problems" the authors describe how they tackled 17x17, 17x18, and 18x18 grid colorings using a SAT solver plus some previous knowledge of grid ...


2

One way to think of it would be elementary blocks, i.e. blocks that cannot be split by cutting them vertically. There's one elementary block of size 1x2 (one vertical B). There's one elementary block of size 2x2 (two horizontal Bs). There are two elementary blocks of size 3x2 (the last two shown in your figure, Example I). There are two elementary blocks of ...


2

In general, you would change the question slightly: "How many ways are there to tile an X by N area by adding tiles individually and always adding the next tile so that it covers the topmost of the leftmost uncovered squares". Obviously that doesn't change the number of possible tilings at all since each square must eventually be covered. Since you are ...


2

Let's see what happens after you rotate the partition around the board's center. The region in which one part maps onto the other part is point symmetric around the board's center. Therefore, the region in which one part is mapped onto the same part is: also point symmetric with the same center itself partitioned into two point symmetric regions with the ...


2

These two cases are already counted in the recursive calls g(n-1). A**** A**** BB*** g(n-1) g(n-1) counts all possibilities to fill the empty space in this ^ form. One way would be to fill it out like the following image, so this case already gets counted and you don't need to add another recursive call. AC*** AC*** BB***


2

SAT solvers are my favorite "big sledgehammer" to apply to this kind of problem, so let me describe how you could use a SAT solver for this problem. Let's constrain the shape to fit within a 15x15 grid (say), and express the problem of finding a valid shape as a SAT problem. It gets a bit messy, so you'll have to be willing to tolerate that, but the ...


1

Tiling figures of the plane with two bars shows that this problem is NP-complete in the general case. Simply have the horizontal and vertical bar the same size $\geq 3$.


1

Q1. Of course you can consider a third variable in the recursion, but that would not simplify the analysis. In fact from the case where you put the single horizontal domino, the next step would automatically put the second horizontal one below it. So the given recursion takes a little shortcut. Q2. That is precisely the point. We have to make sure the ...


1

There are only $9^9$ possible ways to fill each cell with one of the 9 tiles. That's a bit under 400 million possibilities. So, I suggest a simple approach: enumerate all of them, and for each, check whether or not it meets your conditions. That should run pretty fast: you should be able to very quickly test a candidate configuration to see if it ...


1

It's possible that you're talking about Wang tiles. Imagine that you have to fill up a matrix with tiles that cannot be rotated. Each side of each tile is a given color. If two tiles are placed next to each other (share an edge), they must have the same color along that edge. While the color vs number aspect is not important, this differs from your ...


1

Any proof that the Wang tiling problem is undecidable by reduction from undecidability of the halting problem of Turing machines will contain instructions on how the Wang tiles simulate the operation of the machine, and indeed a proof that a tiling exists if and only if the machine doesn't halt. There is more than one such proof. If you look at different ...


1

i had a similar issue in order to store (crossword) puzzle grids, which can have different types of squares (eg letter cells, definition cells, images, etc..) The representation was this (which can be easily serialized into json) dimensions:{ rows, columns, etc..} // for my example this covers almost all default cells then a series of attributes ...


Only top voted, non community-wiki answers of a minimum length are eligible