Edge-matching Problems with Rotations∗
Martin Ebbesen
Appstract Consulting
DK-1300 København K
martin@appstract.dk

Paul Fischer
DTU Compute
Technical University of Denmark
DK-2800 Lyngby
pafi@dtu.dk

arXiv:1703.09421v1 [] 28 Mar 2017

Carsten Witt
DTU Compute
Technical University of Denmark
DK-2800 Lyngby
cawi@dtu.dk
March 29, 2017

Abstract
Edge-matching problems, also called edge matching puzzles, are abstractions of placement problems with neighborhood conditions. Pieces with colored edges have to be placed
on a board such that adjacent edges have the same color. The problem has gained interest
recently with the (now terminated) Eternity II puzzle, and new complexity results. In
this paper we consider a number of settings which differ in size of the puzzles and the
manipulations allowed on the pieces. We investigate the effect of allowing rotations of
the pieces on the complexity of the problem, an aspect that is only marginally treated
so far. We show that some problems have polynomial time algorithms while others are
NP-complete. Especially we show that allowing rotations in one-row puzzles makes the
problem NP-hard. The proofs of the hardness result uses a large number of colors. This
is essential because we also show that this problem (and another related one) is fixedparameter tractable1 , where the relevant parameter is the number of colors.

Keywords: Edge-matching puzzles, complexity, fixed-parameter tractability

1

Introduction

We consider the following combinatorial optimization problem. Let N and M be positive
integers. The puzzles considered in this paper consist of NM quadratic pieces whose edges are
colored. Let c0 , c1 , . . . , cK denote the colors. The pieces are placed in the cells of a rectangular
N × M grid. The edges of a piece are denoted right, top, left, bottom in the obvious way. A
A preliminary version of this paper appeared in Proceedings of FCT 2011, [1].
An NP-complete problem is fixed-parameter tractabel if there is algorithms which is exponential in only
one parameter which specifies the problem size an polynomial in the size of the input. When this parameter is
constant (or “small”), then the problem is efficiently solvable.
∗

1

1

piece P can then be specified by its position (i, j) on the grid and the colors cr,P , ct,P , cl,P , cb,P
on its right, top, left, and bottom edge, in this order. The image below shows a piece specified
by the color pattern (c1 , c2 , c3 , c4 ).
c2
c3

c1
c4

Two pieces are neighbors if they are placed in the same column and the difference of their
row coordinates in the grid is 1 (or with the roles of rows and columns interchanged), i.e.,
they share an edge. Given two pieces P and P ′ on neighboring positions, say at (i, j) and
(i, j + 1) respectively, we say that they match, if the adjacent edges have the same color, that is
cr,P = cl,P ′ . In this case we also say that the edge they have in common matches. Similarly, if
they are vertically adjacent, say at (i, j) and (i + 1, j), they match, if cb,P = ct,P ′ , see example
below.
c2
c2

c3 P c1

c6

c4
c4

c3 P c1 c1 P ′ c5
c4

c7

c6 P ′ c5
c7

We say that a board is solved if the pieces are placed in such a way that all edges match. At
this point one has to specify rules for the “border edges”, that is, the edges facing the border
of the board. We consider three cases here
Free There is no restriction, any color matches the border of the board.
Monochrome There is a single color for all border edges.
Cyclic We assume that the board actually is a torus, that is, the top edges are aligned with
the bottom ones and the left edges are aligned with the right ones.
An arrangement of the pieces which solves the board is called a solution.
The manipulations allowed in a board are:
Swap Two pieces P and P ′ interchange their position, without being rotated.
Rotate A piece P is rotated counter-clockwise in-place by 0 deg, 90 deg, 180 deg, or 270 deg.
Edge permutation The colors on the edges are permuted in one of the 24 possible ways. The
position of the piece is unchanged. Note that this manipulation includes rotations.
Flip The colors of the left and right or up and down edges of piece P are interchanged (that is
P = (c1 , c2 , c3 , c4 ) becomes Pf lipped = (c3 , c2 , c1 , c4 ) or P = (c1 , c2 , c3 , c4 ) becomes Pf lipped =
(c1 , c4 , c3 , c2 )). Flipping is an in-place operation.
Combinations of the manipulations are possible.
The edge matching problem is then formulated as follows.

2

Problem 1.1 Given is a N × M board, K colors, NM pieces, a border rule and a set of
manipulations. The decision problem is given by the question “is it possible to solve the board?”
In the optimization version of the problem, a solution has to be produced.
Edge-matching has found applications in biology where it is used in a method for DNA
fragment assembly [2]. The problem has also gained interest recently with the Eternity II
puzzle, a 16 × 16-puzzle, with a $2 million prize for a solution (which was not found, though).
Another area where this kind of problems appears is chip-layout, where interfaces have to be
placed on a rectangular chip but their order is arbitrary.

1.1

Previous Work

Edge-matching with one row, swaps and no rotation corresponds to domino tiling [3] and is, as
we discuss in this paper (and as covered in [3]), equivalent to the problem of finding an Eulerian
path in a multi-graph. The computational complexity of edge-matching and related problems
has been studied for several decades. Early results show that the more general tiling problem,
i. e., solving the edge-matching problem with swaps for a quadratic board using only a subset
of a given set of un-rotatable pieces is NP-complete [4]. Goles and Rapaport showed in [5] that
the edge-matching problem with only in-place rotations (disallowing swaps) and free border
rule is NP-complete. More recently, Demaine and Demaine [6] proved that the edge-matching
variant considered here is NP-complete for quadratic boards with swaps and rotations. In 2010,
Antoniadis and Lingas showed that this problem is even APX-hard, i. e., hard to approximate,
already for boards with at least two rows [7].

1.2

Overview of the Paper

Most of the above-mentioned analyses of the edge-matching problem consider swaps, but do not
allow rotating pieces. The NP-hardness proof in [6], even though it formally allowed rotations,
forces the pieces to be used in a fixed orientation. Only recently, the APX-hardness proof in
[7] explicitly made use of rotation and swaps at the same time. In this paper we address the
question of what changes in the complexity of the problem occur when rotations of pieces are
allowed.
In Section 2 we consider puzzles with only one row (1 × M). For these puzzles there is a
known correspondence to Euler paths, which we describe along with some previous results. We
then show that single-row puzzles where only in-place rotations are allowed can be efficiently
solved. In contrast we show that solving single-row puzzles with rotations and swaps allowed
is an NP-hard problem. The proofs implicitly use the Euler path formulation of the problem.
In Section 3 we strengthen a result of [6] by showing that already boards with two rows
with swaps only are NP-hard to solve.
Having observed that the hardness proofs use a number of colors which is proportional to
the number of pieces in the puzzle, we show in Section 4 that the problem of solving a single-row
puzzle with rotations and swaps is efficiently solvable when the number of colors is constant or
logarithmic in the number of pieces. Thus this problem is fixed-parameter tractable. Similarly,
an efficient solution is also possible for the case of constant board size and number of colors.

2

Boards with One Row

Edge-matching with one row (N = 1) without rotation is equivalent to the problem of finding
an Eulerian trail in a multi-graph allowing loops. An Eulerian trail is a trail that visits each
3

edge of the graph exactly once, and the concept is applicable to both directed and undirected
graphs: An undirected graph is Eulerian (i.e. contains an Eulerian trail) iff it is connected
and has no more than 2 vertices with an uneven number of edges. An Eulerian circuit (a trail
starting and ending on the same vertex) requires that all vertices must have an even number of
edges. A directed graph has an Eulerian circuit iff it is weakly connected and all vertices has
equal in- and out-degree, while a path requires connectedness and 0 or 2 vertices with difference
in in- and out-degree equal to 1. The above facts are shown in, e. g., [3].
Swaps and flipping
An edge-matching instance with flipping, with M pieces and K colors is transformed to an
undirected multigraph containing K vertices and M edges. Each piece corresponds to an
edge connecting the vertices corresponding to the colors on opposing edges of the piece. Now
traversing a vertex using two different edges corresponds to matching two pieces having a
common color. A trail in the graph corresponds to a matched chain of pieces, and an Eulerian
trail corresponds to a solution where all pieces are fitted, and vice versa. Hence this variant of
the problem is efficiently solvable. Figure 1 shows an example, see [8] for more details.

2

3

0
0
0
0

1

3

1

3

0
0
0
0

4

4

1

3

4

3

0
0

4 4

0
0

3 3

0
0

1 1

0
0

2

2

Figure 1: An example for a single-row puzzle with swaps and flips. The colors of the vertical
edges are denoted 1, 2, 3, and 4; the irrelevant color at the top and bottom is 0. The multi-graph
has a one node for each relevant color and one edge for every piece. The edge connects the
nodes corresponding to the colors of the vertical edges. The graph has an Euler trail, 2, 1, 3, 4, 3
and thus the puzzle is solvable. The corresponding solution is shown at right.

Swaps only
Edge-matching with swaps (no flipping) correspond to Eulerian cycles in directed multigraphs,
and vice versa. Hence this variant of the problem is efficiently solvable.
Rotations only
With free border rule, if the board consists of only one piece it will always be solved. Obviously,
for a board with two pieces there will be a solution if the two pieces can be rotated such that
their touching edges match. This can be generalized:
Theorem 2.1 Single-row edge matching puzzles with in-place rotations can be solved or determined to be unsolvable by an algorithm that has time complexity linear in the number of
pieces.
Proof The proof is by induction. The pieces are numbered from left to right as p0 , p1 , ..., pM −1 .
L(pi ) is the set of colors that can be on the left edge of piece pi which is equivalent to the set
4

of unique colors on the 4 edges of pi . R(pi ) is the set of colors that can be on the right edge of
pi such that pi fits pi−1 , that is, such that L(pi ) ∩ R(pi−1 ) 6= ∅. L(pi ) and R(pi ) can both have
at most 4 members since a piece has 4 edges.
Base case: For p0 there is no constraint, as one piece always represents a solution to a 1 × 1
board: R(p0 ) = L(p0 ).
Induction step: Given that R(pi ) is known and the board is solvable up to pi then piece
pi+1 can be fitted if R(pi ) ∩ L(pi+1 ) 6= ∅. If not, the board must be unsolvable. R(pi+1 ) can be
calculated by finding the color on the opposite edge of pi+1 for each member in R(pi ) ∩ L(pi+1 ).
This operation takes constant time because of the bound on the sizes of the two sets.
The theorem holds because each step in the induction, i. e., each additional piece, only adds
a constant time overhead.
q.e.d.
Swaps and Rotations
Theorem 2.2 If both swaps and rotations are allowed, single-row edge-matching with free border rule is NP-complete.
Proof We use a polynomial-time reduction from the NP-complete Monotone 1-in-3-SAT problem [9]: given m monotone (i. e., disallowing negation) clauses c1 , . . . , cm over n variables
x1 , . . . , xn , the question is whether there exists an assignment which satisfies exactly one variable in each clause.
Let mi , i = 1, . . . , n, denote the number of occurrences of variable i, i. e., m1 +· · ·+mn = 3m.
The instance of Monotone 1-in-3-SAT is mapped to a single-row board with free border at the
top and bottom and cyclic border to the left and right (which can be simulated by a free border
using a polynomial number of extra pieces). There are M = 10m pieces and K = 13m − n + 1
colors. We denote colors by lower-case and pieces by upper-case letters. The set of pieces
′
consists of all Vj,q , Vj,q
, Sj , where j = 1, . . . , m and q = 1, 2, 3, and Ai,k , where i = 1, . . . , n and
k = 1, . . . , mi . The colors are ℓ, tj,q , t′j,q , fj,q , sj , and ai,k , where k = 1, . . . , mi − 1. We define
and name the different classes of pieces as follows:
′
= (ℓ, t′j,q , fj,q , ℓ).
Value Vj,q := (fj,q , tj,q , sj , ℓ); Vj,q

Satisfying Sj := (sj , sj , sj , sj ).
Accordance If mi = 1 then Ai,1 := (ℓ, ℓ, ℓ, ℓ). Otherwise, let the k-th occurrence of xi be at position qk ∈ {1, . . . , 3} in clause cjk , k = 1, . . . , mi . Then define Ai,k := (t′jk ,qk , ai,k−1, tjk ,qk , ai,k ),
where ai,0 := ai,mi := ℓ.
This completes the transformation, which is obviously polynomial-time computable.
Rotations can deactivate up to two colors from a piece, namely those that are facing the
border and thus need not be matched. Active colors must occur an even number of times in
a solved board. When placing a piece Vj,q , either fj,q and sj , or tj,q and ℓ will be deactivated.
′
Actually, since fj,q only appears in Vj,q and Vj,q
, a solution requires that these pieces either
both deactivate fj,q or that both activate this color. If they both activate fj,q (which also
activates sj once), they will be adjacent in a solution. Later, active fj,q will model that the
q-th variable in cj is false, and inactive fj,q will model a true setting. Since sj appears only in
Vj,1 , Vj,2, Vj,3 and Sj , but cannot be deactivated in Sj , where it will be used twice, it is necessary
for a solution that an even, positive number of pieces from Vj,1 , Vj,2, Vj,3 use sj . This forces two
of the variables in cj to a “false” and one to a “true” setting.
Finally, the interplay of the tj,q and t′j,q within the V - and A-pieces will ensure the consistency
of the truth assignment. We fix a variable xi and assume mi > 1 as there is nothing to show
5

otherwise. Since color ai,k , k = 1, . . . , mi − 1, is only used in Ai,k and Ai,k+1, these two
pieces must either both be rotated to activate the t and t′ colors on their edges, or the pieces
must be adjacent, which inductively requires that the solution contains all Ai -pieces as a chain
Ai,1 , Ai,2 , . . . , Ai,mi in this or reverse order. In the case of a chain, the colors tjk ,qk and t′jk ,qk
must be inactive for all k = 1, . . . , mi , which means that the pieces Vjk ,qk and Vj′k ,qk are adjacent
by virtue of color fjk ,qk , hence a “false” setting of xi . Otherwise, the colors are all active, which
is (by the uniqueness of the colors) only possible if Ai,k is fit between the pieces Vjk ,qk and
Vj′k ,qk , both of which are rotated to a “true” setting. Hence, all mi occurrences of xi must be
consistent.
We now prove that there is a solution to Monotone 1-in-3-SAT if and only if there is one to
the puzzle. Let us first prove the implication ⇒, i. e., we consider an assignment to x1 , . . . , xn
which satisfies exactly one variable in each clause. We lay down the pieces as subsequences
in clause-wise order. When considering a clause cj = (uj,1 ∨ uj,2 ∨ uj,3), j = 1, . . . , m, let
q ∈ {1, . . . , 3} be the index of its unique satisfied variable, say this variable is xi in its k-th
occurence. The subsequence for cj starts with Vj,q rotated by 270◦ (left-hand side has color ℓ),
′
followed by Ai,k unrotated and Vj,q
rotated by 90◦ . Note that the right-hand side is ℓ. Let q ′ and
′′
′
q be the indices of the other two unsatisfied variables in cj . We proceed by placing Vj,q
′ rotated
◦
◦
by 180 , then Vj,q′ rotated by 180 and afterwards Sj . The construction for clause j is continued
′
by placing Vj,q′′ and Vj,q
′′ unrotated, which again ends in color ℓ. Note that we have placed all
Vj,· -pieces and the Sj -piece as well as a single A-piece corresponding to the occurrence of the
satisfied variable. Finally, if they have not been placed before, we use all A-pieces corresponding
to the unsatisfied variables as follows: If uj,q′ = xr then Ar,1 , Ar,2 , . . . , Ar,mr are appended in
the chained way described above (again ending in ℓ), completed by the chain for variable uj,q′′ .
The construction ends with ℓ on the right-hand side and is continued with the next clause,
resulting in all pieces being used and the puzzle being solved.
For the implication ⇐, assume now that the puzzle is solved. We have already argued that
′
for any j, there must be exactly one q such that the pair (Vj,q , Vj,q
) is rotated according a “true”
setting and two other q such that the pair is in a “false” setting. We set the variables in cj
accordingly. If a variable contains in another clause, we already know that the corresponding
pieces must be rotated in a consistent way, which proves that we have a solution to Monotone
1-in-3-SAT.
q.e.d.

3

Boards with at Least Two Rows

We consider boards with two rows and arbitrarily many columns. Of course, the roles of
columns and rows can be interchanged.
In [6] edge-matching is shown to be NP-complete for quadratic boards. More recently, [7]
showed in a much more involved proof that the problem is even APX-complete, already for
rectangular boards with only two rows. We focus on Demaine’s and Demaine’s technique from
[6], which does not use rotations, and show that it can be strengthened to also include boards
with row-count two – by extension edge-matching with any width-height ratio is NP-complete
(with the exception of single-row puzzles), since it is trivial to force a board to contain more rows
by adding uniformly colored pieces. However, as stated in Section 2, edge-matching without
rotation is efficiently solvable when the row-count is 1.
Theorem 3.1 Two-row edge matching puzzles with swaps and free or monochromatic border
is NP-complete.
Proof The transformation is from 3-partition in which the task is to partition a set of 3m
positive integers into m sets, each consisting of 3 integers such that the integers in each set
6

sum to the same value S. This problem can be visualized as the task of, given a collection of
bars of varying length, placing the bars in rows, such that each row has 3 bars and all rows
have the width S. Importantly 3-partition is also NP-complete when all the integers are limited
to values in the range (S/4, S/2), meaning that any row with width S must contain exactly 3
bars – this is the version of the problem used in this proof. The problem remains NP-complete
when S and m are polynomially related.
Bar:
$

%

%

%

%
%
x x x $

x x x x x

Board structure:
a0 a1 a1 a2
%
%

c0 c1 c1 c2 c2 c3
%
%
@
@
$ $

b0 b1 b1 b2 b2 b3
%
%
@
@
$ $

S

S

...

Converting this problem into an edge-matching puzzle with height 2 proceeds as follows: A
section of pieces (a ’bar’) is defined for each of the 3m integers. The internal left-right edge-color
(shown as ’x’ in the figure) is unique for each bar, and every bar starts and ends on the specific
color ’$’. A board with height N = 2 and width M = mS + m − 1 is constructed, where the
upper row is forced to have a particular layout as illustrated in the figure by using unique colors
for every edge pair, and the lower row is separated into areas of length S, each of which can
contain 3 bars. All separators will fit any bar left and right (color ’$’), and all bars will fit in
any position below the fixed upper row (color ’%’). If the 3-partition has a solution then it will
be possible to place the m bars into the board giving a solution to the edge matching puzzle.
If the edge matching puzzle can be solved it will be because all sections can be placed into
the forced layout of the grid, meaning that there is a solution to the corresponding 3-partition
problem.
q.e.d.

4

Dependence on the number of colors.

In the proof of Theorem 2.2 (and other hardness results concerning puzzles), the number of
colors used is linear in the the size of the reference problem. It is natural to ask whether the
problem remains hard, when the number of colors is limited to a constant. We now show that
the problem of Theorem 2.2 becomes efficiently solvable if the number of colors is at most
c(log(M))1/4 , for c constant.
Theorem 4.1 If both swaps and rotations are allowed, single-row edge-matching with free border and two colors is solvable in time O(M), where M is the number of pieces. For K colors
4
the problem is solvable in time O(M + 5K ).
The last part of the theorem leads to the following corollary.
Corollary 4.2 If both swaps and rotations are allowed, the single-row edge-matching problem
with free border is fixed-parameter tractable.
Proof (Of the theorem) We start by exemplifying the proof method by looking at the case of
one and two colors, black (b) and white (w).
If there is only one color, the puzzle is solvable, by placing the pieces in a row.
7

With exactly two colors, the pieces can be classified as either constants or switches. Constants are pieces that have the same color on the left and right edge, regardless of the rotation.
Switches can be rotated such that there are different colors on the left and right edge.

Constants

Switches

If the puzzle consists of constants only it can be solved if and only if it does not contain
both a completely black and a completely white piece.
Otherwise there is both a monochromatic black piece and a white one. We claim that the
puzzle has a solution if and only if there is at least one switch. Consider the multi-graph
modeling as defined in Section 2. Recall that an Euler path corresponds to a solution when
swaps and flips are allowed, but not general rotations. We now show, how this method can be
used also in the case of few colors when also rotations are allow. For two colors the graph has
two nodes w and b, one for each color. Consider the constant pieces first. The monochromatic
ones give rise to loops at the node corresponding to their color. The non-monochromatic pieces
give rise to a loop on one of the nodes. Which node this is depends on the rotation. In absence
of a switch piece there is no edge between the nodes, hence no Euler path and no solution.
If the puzzle contains at least one switch, then this can be rotated in such a way that it
forms an edge {b, w} between the two nodes. Regardless how the other pieces are rotated, the
resulting graph has an Euler path. One starts at, say, w and traverses all loops at that node,
then one uses one edge {w, b} to get to node b. Then one traverses all loops at b. Finally one
uses the remaining {w, b}-edges (if any) exactly once. The Euler path corresponds to a solution
as described above.
Consider the case of a puzzle with M pieces and K colors. Let X = abcd be a color scheme,
i.e., a counter-clockwise order of four (not necessarily distinct) colors. We assume that the
cyclic order of the color scheme is such that it is lexicographically minimal. This is to avoid
treating an abcd and bcda as different color schemes.
Every arrangement of the M pieces gives rise to a multi-graph. The graph has K nodes and
one edge for every piece. A piece with color scheme abcd will correspond to an edge {a, c} if a
and c are the colors on the vertical edges. Otherwise the piece gives rise to an edge {b, d}. Let
ma,b denote the number of edges between nodes a and b. Loops (a = b) are allowed, however
they do not have any influence in the solvability of the puzzle, as discussed in the example for
two colors.
Given an arrangement of the M pieces, let nX be the number of pieces having color scheme
X = abcd. Let nX,ac denote the number of pieces with color scheme X which are rotated to
become an {a, c}-edge. Similar nX,bd . We make the convention that nX,ac = 0 if X does not
contain the colors a and c on opposing edges. Then
nX = nX,ac + nX,bd
and
mac =

X

nX,ac

(2)

X

Furthermore
deg(a) =

X

mab +

X
c : c<a

b : b>a

8

(1)

mca + maa

For the graph to have an Euler cycle the mxy have to be chosen such that they obey the
constraints (1) and (2) and all degrees are even. For the graph to have an Euler path the mxy
have to be chosen such that they obey the constraints (1) and (2) and exactly two nodes have
odd degrees.
As we are only interested in connectivity and parity of degrees, we replace the nX as follows
(that is we remove pieces with color scheme X):
• If nX ≤ 4 it is unchanged.
• If nX > 4 and even then set nX = 4.
• If nX > 4 and odd then set nX = 3.
We claim that this does not change the fact whether the puzzle is solvable or not. Assume
nX > 4 and is even. The number of pieces rotated such that they produce an {a, c}-edge is nX,ac ,
number of pieces rotated such that they produce an {b, d}-edge is nX,bd and nX = nX,ac + nX,bd .
Assume that the puzzle is solvable. Then there is a way to choose nX,ab and nX,bd such that
the resulting graph has an Euler cycle or path, especially it is connected. We only discuss the
case of an Euler cycle, the arguments for a path are identical. Then the degrees of all nodes,
especially a, b, c, d are even. As nX is reduced by an even number but remains at least 3, we
can reduce both nX,ac and nX,bd (that is remove the corresponding edges) by an even number
each, without being forced to make one of them zero. If some nX,ac is zero in the beginning,
it will remain unchanged, therefore we only consider nX,ac > 0 in the following. The resulting
graph is connected and all degrees are even. Hence it still has an Euler cycle.
Now assume that the puzzle is not solvable. Then there is no way to choose the numbers
nX,ab and nX,bd such that the resulting graph has an Euler cycle. That is the graph is unconnected or has nodes with odd degree for any such choice. If there is no way to choose nX,ab
and nX,bd to make the graph connected, then reducing the number of pieces maintains that
property.
Assume therefore that for some choices of the numbers nX,ab and nX,bd the graph is connected, but always has nodes with odd degree.
Consider a given partition of the nX = nX,ac + nX,bd . If nX is odd then one of nX,ac and
nX,bd is odd the other is even. Replacing nX by 3 (and changing nX,ac and nX,bd to satisfy (1))
maintains this property. Thus it is not possible to introduce a new distribution of parities of
the nodes (for example one with only even node degrees).
If nX is even then nX,ac and nX,bd are either both even of both odd. Replacing nX by 4 and
changing nX,ac and nX,bd to satisfy (1)) maintains this property. If nX,ac and nX,bd were both
even and positive, we set both to 2. If both were odd and positive, we set them to 3 and 1.
Again it is not possible to introduce a new distribution of parities of the nodes (for example
one with only even node degrees).
Hence reducing the nX as described still allows the graph to be connected and does not
allow the graph to have only vertices of even degree.
Now, check all possibilities to partition the reduced nX into nX,ac , nX,bd and compute the
mxy . For each partition check whether it leads to a degree sequence ensuring an Euler cycle.
Each nX can be partitioned into nX,ac and nX,bd in 4, or 5 ways, depending on it being 3 or
4; these are the possibilities for the latter case (0, 4), (1, 3), (2, 2), (3, 1), and (4, 0).
Hence the number of possibilities to try is at most 5ℓ , where ℓ is the number of color
schemes. The quantity ℓ can be upper-bounded by K 4 , where K is the number of colors.
For each partition it has to be checked, whether the resulting degree sequence is Eulerian.
Computing the nX is linear in the number of pieces.
9

Hence the total time for deciding a puzzle with M pieces and K colors is
4

O(M + 5K )
which is linear for constant K, and polynomial for K = c(log(M))1/4 , for c constant.

q.e.d.

The last result shows that the number of colors seems to play an essential role for complexity
of puzzle problems. The following result supports this by showing that also puzzles with inplace rotations can be efficiently solved when the number of colors and rows is constant. As
mentioned in section the unrestricted problem is NP-complete, see [5]. This resembles fixedparameter tractability, but requires two parameters to be constant.
Theorem 4.3 Puzzles with N rows, M columns, and K colors and in-place rotations are
solvable in polynomial time for constant N and K.
Proof Consider a column in the puzzle. For each of the N pieces in the column, there are 4
possible rotations, giving 4N configurations for the column. An N-color pattern is a sequence
[c1 , . . . , cN ] of N colors. Given K colors there are at most K N N-color patterns, which we
number 1, . . . , K N . For each column there are at most 4N possible color patterns at the left
and at the right edge of the column. Consider column j and construct a bipartite graph Gj as
follows. The vertex set is V = Vj,left ∪ Vj,right where Vleft and Vright each contain K N vertices,
one for each color pattern. Let Vj,left = {vj,1, . . . , vj,K N } and Vj,right = {wj,1, . . . , wj,K N }. We
then try all 4N configurations of the pieces in column j. If a configuration gives color pattern
a at left and pattern b at right and the colors at the N − 1 horizontal edges match then we
add a directed edge (vj,a , wj,b) to the graph. Let Gj denote the resulting bipartite graph. The
construction of Gj can be performed in time O((4N ) + (K N )) given that the index of the color
pattern can be computed in time Θ(K + N). Graph Gj has 2K N nodes and at most 4N edges.
Next we connect the consecutive graphs Gj , Gj+1 , j = 1, . . . , M − 1 by adding the directed
edges (wj,a, vj+1,a ), a = 1 . . . , K N . Finally we add a source node s and connect it to all left
nodes of G1 by directed edges (s, v1,a ). We also add a sink node t and connect it to all right
nodes of GM by directed edges (wM,a , t). Let G = (V, E) be the resulting graph. Note that
|V | = 2MK N + 2 and |E| ≤ M4N + (M − 1)K N + 2K N and that G can be constructed in time
O(M(K M + 4N )).
Now, compute whether there is directed path from s to t in G. We claim, that if so, there
is solution for the puzzle otherwise there is not. Assume there is a directed path from s to t.
Let (s, v1,a1 ) be the first edge of the path and (wn,bn , t) be the last one. In between there are
alternating edges inside the Gj and in between the Gj . This means that for every j = 1, . . . , n−1
the path contains an edge (wj,cj , vj+1,cj ) for some color pattern cj . Hence there are matching
color patterns between all rows. Within every Gj the path uses an edge (vj,aj , wj,bj ). That is,
the color patterns at the left and at the right of column j can be realized simultaneously by
an appropriate configuration of the pieces in that column. Hence the puzzle has a solution. As
finding the shortest path can be done in time linear in the graph size, the total running time
is polynomial in for constant N and K.
Conversely, any solution of the puzzle gives rise to at least one path from s to t by the
definition of the graph.
q.e.d.

5

Summary and Conclusions

In this paper, we have focused on several problem aspects of edge-color puzzles whose impact
on complexity was unknown or only marginally treated before, in particular rotating pieces,
10

in-place pieces, border rules, number of colors and shapes of pieces. With regard to single-row
boards, it has been shown that introducing rotations makes the otherwise easy problem NPhard. In basically all hardness results, a large number of colors is used, usually linear in the
number of pieces. For two cases we have shown that the problem is fixed-parameter tractable,
i.e., it becomes efficiently solvable when the number of colors is constant or logarithmic in the
number of pieces.
The table below summarizes the known hardness results for boards with one row compared
to boards with at least two rows.
Rows:
Swap
Rotation
Both

1
P
P
NP-complete, fixed-parameter tractable

≥2
NP-complete
NP-complete
NP-complete

This paper has raised further questions concerning the hardness of edge-matching problems.
For example, are there more hard problems which are fixed-parameter tractable? Furthermore,
it is unknown whether the single-row case with rotations is hard to approximate.

Acknowledgement
The second author gratefully acknowledges support by the DTU’s Corrit travel grant.

References
[1] M. Ebbesen, P. Fischer, C. Witt, Edge-matching problems with rotations, in: Fundamentals
of Computation Theory - 18th International Symposium, FCT 2011, Oslo, Norway, August
22-25, 2011. Proceedings, 2011, pp. 114–125.
[2] P. Pevzner, H. Tang, M. Waterman, An Eulerian path approach to DNA fragment assembly,
Proceedings of the National Academy of Sciences of the United States of America 98, no.
17 (2001) 9748–9753.
[3] O. R. Lesniak, Linda; Oellermann, An Eulerian exposition, Journal of Graph Theory 10
(1986) 277–297.
[4] M. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, W.H. Freeman and Company, 1979.
[5] E. Goles, I. Rapaport, Complexity of tile rotation problems, Theoretical Computer Science
188 (1997) 129–159.
[6] E. D. Demaine, M. L. Demaine, Jigsaw puzzles, edge matching, and polyomino packing:
Connections and complexity, Graphs and Combinatorics 23 (2007) 195–208.
[7] A. Antoniadis, A. Lingas, Approximability of edge matching puzzles, in: Proc. of SOFSEM 2010, Vol. 5901 of LNCS, Springer, 2010, pp. 153–164.
[8] M. Ebbesen, Analysis of restricted edge-matching problems, Master’s thesis, Technical University of Denmark, master thesis, Technical University of Denmark, reference no. IMMM.Sc.-2011-08, http://etd.dtu.dk/thesis/275156/ (2011).

11

[9] T. J. Schaefer, The complexity of satisfiability problems, in: Proceedings of the tenth annual
ACM symposium on Theory of computing, STOC ’78, 1978, pp. 216–226.

12

