monthyeardate[],

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 NP-completeness
    2. 2.2 Rectilinear Planar Monotone 3SAT
    3. 2.3 Solution framework
  3. 3 Arbitrarily shaped Double Choco is NP-complete
    1. 3.1 Wire gadget and supporting gadgets
    2. 3.2 The variable gadget
    3. 3.3 Clause gadget
    4. 3.4 Connecting the dots
  4. 4 Double Choco is NP-complete
    1. 4.1 Shielding the wire and rotation gadgets
    2. 4.2 Shielding the complete variable gadget
    3. 4.3 Shielding the complete clause gadget
    4. 4.4 Connecting the dots

’You can’t connect the dots looking forward; you can only connect them looking
backward.’

S. J.

##  Chapter 1 Introduction

Nikoli is a leading publisher of pencil-and-paper logic puzzles, having
presented many different puzzles over the past few decades in their Puzzle
Communication Nikoli magazine and website [Nik22]. Perhaps the most well known
of their brain teasers is Sudoku [Nik86], which was proven to be NP-complete
in the year 2003 [YS03].

As Nikoli expanded into the field of puzzles, their puzzles and the study of
their computational properties have gained an increasing amount of popularity.
Consequently, the concept of the Nikoli gap [Add+18] was established to define
the number of years between the year a puzzle is introduced and the year a
paper about the puzzle‘s computational complexity is published.

Year the puzzle is introducedNikoli gap Figure 1: Nikoli gap. Source: [Add+18]

Papers on the computational complexity of the puzzles appearing in Figure 1
can be found in: Kakuro (Cross Sum) [YS03], Slitherlink [Tak00], Numberlink
[KT10], Hashiwokakero [And09], Hitori [HD09], Nurikabe [HKK04], Heyawake
[HR07], Fillomino [Yat03], Shikaku and Ripple Effect [Tak+13], Yajilin
[ISI12], Masyu (Pearl) [Fri02], Akari (Light Up) [McP05], Satogaeri [KT15],
Shakashaka [Adl+15, Dem+14], Norinori [BS17], Suraromu [KT15], Yosenabe
[Iwa14], Sto-Stone [AW18, Add+18], and Pencils [Add+18].

We can observe that the Nikoli gap has a decreasing trend that can be
justified by the rise in popularity of Nikoli puzzles with customers as well
as an increase in focus within the theoretical computer science community.
This has been supported by continued acceptance of papers regarding puzzles’
computational properties on conferences such as FUN [Alg22].

In this thesis, we are studying the computational properties of the Double
Choco (Double Chocolate) puzzle [Nik20], which was first published on January
15, 2020 in [Nik20a], gaining huge popularity in a relatively short period of
time. Double Choco is a Nikoli pencil-and-paper game consisting of an $m\times
n$ grid board of unit squares, of white or gray color, separated by dotted
lines. Some squares may contain an integer between $1$ and $\frac{mn}{2}$. The
solution to this puzzle is a set of blocks such that:

  * •

The blocks are disjointed.

  * •

The blocks, together, cover all cells of the puzzle.

  * •

Each block has the same number of white and gray cells.

  * •

The white and gray areas of any block are connected (both separately and with
each other) and they have the same size and shape, with respect to rotation or
mirroring.

  * •

If any cell inside a block contains a number, then the white and gray area of
that block must have that number of cells.

  * •

A block can contain any number of cells with numbers.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 2: A step by step solution of the Double Choco puzzle from The Guardian
article [Lim20].

We create the puzzles using Double Choco editor [Hap86]. The editor has shown
to be a very useful tool for constructing and solving the puzzles as it is
capable of automatically checking the solution.

In Figure 2, we present the puzzle instance with the step-by-step solution. In
each step, one block is chosen, so the number of steps is bounded by the
number of cells (more precisely by its half), so the problem is in NP (see
section 2.1). In this thesis, we prove that it is in fact NP-complete.

We start by introducing the necessary tools used in our study in chapter 2. We
first explain what NP-completeness is, followed by the introduction of the
Planar Rectilinear Monotone 3SAT problem that we use to prove the hardness of
our result. Finally, we conclude the chapter with the properties our
reductions should satisfy.

The first important result of this thesis is presented in chapter 3 where we
prove that the arbitrarily shaped Double Choco is NP-complete.

Finally, in chapter 4, by using the result from the previous chapter, we prove
that Double Choco is NP-complete, hence establishing the Nikoli gap of more
than 2 years.

##  Chapter 2 Preliminaries

###  2.1 NP-completeness

This section is mainly taken from [ĐG21]. The complexity class NP
(Nondeterministic Polynomial time) represents a set of decision problems,
i.e., problems with yes-or-no answers, such that each solution has a
polynomial length with respect to input size. Moreover, there exists a program
that can check the validity of such a solution (witness) in polynomial time.

More formally:

######  Definition 1 (NP).

NP is the class of problems $A$ of the form:
$x$ is a yes-instance of $A$ if, and only if, there exists a $w$ such that
$(x,w)$ is a yes-instance of B, where B is a decision problem in P regarding
pairs $(x,w)$, and $|w|=poly(|x|)$ [MM11].

Reduction is a procedure for transforming an instance of one problem into an
instance of the another problem. If a problem $A$ is reducible to problem $B$,
and if there exists an efficient algorithm for solving problem $B$, then we
can use it to solve $A$ efficiently as well, i.e., the problem $B$ is at least
as hard as problem $A$. It this thesis we will only use mapping reduction:

######  Definition 2 (Mapping reduction).

A function f: $\\{0,1\\}^{*}\ \rightarrow\\{0,1\\}^{*}$ is called mapping
reduction from $A$ to $B$ if, and only if,:

  1. 1.

For any $w\ \in\textSigma_{1}*$, $w\in A$ if, and only if, $f(w)\in B$.

  2. 2.

f is a computable function, and can be performed in polynomial time.

Or less formally, mapping reduction from $A$ to $B$ says that we can transform
any instance of $A$ into an instance of $B$, such that the answer to $B$ is
the answer to $A$.

######  Definition 3 (NP-hard).

A problem is NP-hard if every problem in NP can be reduced to it using at most
polynomial time reduction.

A problem that is both NP and NP-hard is NP-complete, i.e., if there exists an
algorithm that solves any of NP-complete problems in polynomial time, we can
easily solve all of them in polynomial time. In that case, it will hold that
$P=NP$, but it is highly unlikely, so we believe that $P\neq NP$, i.e., we
believe that P and NP are two essentially different complexity classes.

###  2.2 Rectilinear Planar Monotone 3SAT

A Boolean variable $x_{i}$ can have a value of true or false. The variable or
its negation are collectively called literal. A Boolean formula $\phi$
consists of the Boolean variables $x_{1}$, $x_{2}$, …, $x_{n}$ and the logical
operators AND ($\wedge$), OR ($\vee$), and NOT ($\neg$), e.g.
$\phi=(x_{1}\wedge x_{2})\vee(\neg x_{2}\vee x_{3})$. A formula $\phi$ is
satisfiable if there exists assignment of the variables $x_{1}$, $x_{2}$, …,
$x_{n}$ such that $\phi(x_{1},...,x_{n})=true$, otherwise, it is unsatisfiable
[AB09].

A Boolean formula is in the Conjunctive Normal Form (CNF) if it consists of
groups of OR’s of literals (clauses), with AND’s between clauses. A CNF
formula having at most $3$ literals in each clause is known as an 3CNF
formula.

The Boolean satisfiability problem (SAT) is the problem of deciding whether a
given CNF formula has a satisfying assignment. Similarly, for the 3CNF formula
is the 3SAT. The fundamental result of the complexity theory known as the
Cook-Levin Theorem says that the SAT (3SAT) is NP-complete [Coo71, Lev73].

Here, we will focus on the restricted version of 3SAT known as the Rectilinear
Planar Monotone 3SAT (RPM-3SAT) (2.3(a)). A formula is planar if the incidence
graph of variables and clauses, where a variable is connected to a clause
containing it, can be drawn on the plane in a such a way that none of its
edges intersect (i.e. they can be embedded in the plane). Rectilinear property
ensures that planar embedding satisfies:

  * •

Variables are horizontal rectangles of the same height.

  * •

Clauses are horizontal rectangles of the same height.

  * •

Variables are connected to clauses with the vertical lines (wires).

  * •

There exists a variable line \- on which all variables lie.

Monotonicity implies that each clause is either positive or negative, meaning
they contain only the variables without negations or with negations
respectively. Hence, adding two properties:

  * •

Positive clauses are above the variable line.

  * •

Negative clauses are below the variable line.

(a) Rectilinear embedding.

(b) Bent rectilinear embedding.

Figure 3: Embeddings of the instance of RPM-3SAT. They represent the CNF
formula: $(x_{1}\vee x_{4}\vee x_{5})\wedge(x_{2}\vee x_{3}\vee
x_{4})\wedge(\neg x_{1}\vee\neg x_{2}\vee\neg x_{4})\wedge(\neg x_{2}\vee\neg
x_{3}\vee\neg x_{4})\wedge(\neg x_{4}\vee\neg x_{5}\vee\neg x_{6})$. Source:
[AW18]

######  Theorem 1.

Rectilinear Planar Monotone 3SAT is NP-complete.

###### Proof.

Look at [DK12]. ∎

In order to simplify our reduction, we introduce Bent RPM-3SAT by making a
small adjustment to planar embedding as shown in 2.3(b) (inspired by [AW18]):

  * •

Each clause is shrunk by moving the left and right boundary toward the clause
center, in such a way that all clauses have the same width and that the middle
wire is equally distanced between the left and the right end of clause.

  * •

Each left and right wire of every clause is extended vertically from the
bottom to middle of the clause, redirected by
$90$\mathrm{\SIUnitSymbolDegree}$$ in clause direction, and extended
horizontally until it touches the clause border.

Since the RPM-3SAT is drawn on a plane (continuous domain), each of its
clauses can be shrunk and wires can be modified, as explained, without
changing any other part of the embedding. Hence, the Bent RPM-3SAT will
preserve the computational properties of RPM-3SAT.

###  2.3 Solution framework

For the purpose of our reduction, we will define building blocks for the
puzzle, called gadgets, inspired by Gadget Area Hardness Framework [Adl+20].
The puzzle will consist of gadgets and external areas.

A gadget is a subpuzzle, a connected subset of cells, consisting of mandatory
and one or more optional areas. Each optional area is the place where two
adjacent gadgets overlap, and cannot be adjacent to any other gadget. Any area
assigned to a gadget must satisfy the following:

  1. 1.

It covers the gadget’s mandatory area.

  2. 2.

It is a subset of the gadget’s entire area.

  3. 3.

It either fully covers or fully uncovers any optional area.

A gadget’s solution is a local solution to a subpuzzle with an assigned area
that satisfies the above mentioned properties, as well as the Double Choco
properties from chapter 1.

A gadget’s profile table is the list of its solutions. A profile table is
complete if it contains all of a gadget’s solutions.

An external area is a subpuzzle consisting only of a mandatory area. Each
external area should not interact with any gadget, and the external area must
be solvable locally (only using its own cells). Hence, the external areas do
not effect the solution to our puzzle and their only utilization is to cover
the holes in the grid structure of the puzzle in chapter 4.

Given a puzzle consisting of gadgets and external areas, a puzzle profile
assignment defines an area assigned to each gadget such that each area is
disjointed from all the others, and a union of the solutions covers entire
area of all gadgets. A profile assignment is valid if all assigned gadgets’
areas represent the solution of respective gadgets, i.e., the assigned area
appears in the gadgets’ profile table. Observe that if $G_{1}$ and $G_{2}$ are
adjacent gadgets overlapping on optional area $A_{1}$, in any valid profile
assignment, if an area assigned to $G_{1}$ covers (uncovers) $A_{1}$, than
$G_{2}$ uncovers (covers) $A_{1}$.

##  Chapter 3 Arbitrarily shaped Double Choco is NP-complete

An arbitrarily shaped Double Choco is a relaxed version of the original puzzle
in which the board can have arbitrary shaped holes in its grid structure, but
its cells still need to be connected. In this chapter we prove it to be NP-
complete by reduction from the Bent RPM-3SAT.

With this relaxation, our puzzle can consist only of connected gadgets,
without external areas. We will describe the wire, variable, and clause
gadgets used to make our reduction in section 3.1, section 3.2, and section
3.3, respectively, as well as a various supporting gadgets such as the
rotation and wire boundary gadgets.

When arranging our gadgets we will follow 2.3(b) and scale it up in some
cases. Each wire starts from the wire boundary gadget that determines its
value. The wire is used to transfer the value and is then connected to a
variable gadget. The variable gadget connects the neighbouring wires so that
all upward wires have the same value, all downward wires have the same value,
while the upward and downward wires have the opposite value. After exiting the
variable gadget, unused wires will be terminated in another wire boundary
gadget, while the used wires will transfer their value to the clause gadget,
potentially going through a rotation gadget which will rotate them
$90$\mathrm{\SIUnitSymbolDegree}$$ in the direction of the clause.

The wire boundary gadget has only one optional area which will either be fully
covered or fully uncovered by its solution. When starting the wire, if the
optional area is covered by the wire boundary gadget solution, it will assign
the value true to the wire, otherwise, if it is uncovered, it will assign
false. While all the other gadgets, except the clause gadget, will have paired
optional areas of the same size, on one area they will receive the truth value
while on the other they will output it. Exactly one of the paired areas will
be covered by the gadget solution, in that way transferring the truth value.
The clause gadget will have three optional areas, representing inputs which
receives the truth values from incoming wires. It will enforce that at least
one wire communicates true because it can be solved only in that case.

When a puzzle is created in the way described above, it will have each
optional area covered completely by exactly one gadget. Hence, the gadget
solutions that partially cover the optional area will never happen in any
solution of the puzzle, even if the gadget is solvable in that case. Thus, we
will not present them in the gadget’s profile table. We will call the profile
table that contains all the solutions except those the sufficient profile
table. Consequently, we have relaxed the third property of the gadget assigned
area without changing the puzzle profile assignment.

(a) An unsolved wire gadget. Optional areas are inside the blue rectangles,
while the area outside them is mandatory.

(b) Wire communicating false.

(c) Wire communicating true.

Figure 4: Wire gadget with the profile table. In figures (b) and (c) green
area is not covered by the gadget solution. It is covered by an adjacent
gadget, which determines the value of the wire.

###  3.1 Wire gadget and supporting gadgets

In Figure 4 we present the wire gadget consisting of the odd number of rows,
in this case three, and two columns, with an integer $\bm{2}$ in each cell,
while cells in left and right column are colored differently. When determining
the value in the subfigures (b) and (c), we assumed that the lower optional
area receives the truth value while the upper optional area outputs it. In the
opposite case, the values will be opposite.

######  Lemma 1.

The bottom optional area of the wire gadget is covered by the gadget assigned
area if, and only if, the top optional area is not covered.

###### Proof.

By using the puzzle properties, if the bottom optional area is covered, it
must be in the same block as the mandatory area. Since the top optional area
has cells with an integer of $\bm{2}$, it therefore must be in a block of four
cells. Thus, the top optional area cannot be covered by that gadget solution.
Similarly, if the top optional area is covered, the bottom optional area
remains uncovered. ∎

######  Lemma 2.

The wire gadget’s profile table in Figure 4 is sufficient.

###### Proof.

As a consequence of Lemma 1, regardless of whether the bottom optional area is
entirely uncovered or entirely covered by the solution, the solution should
tile exactly four cells. Since those four cells contain integer $\bm{2}$, in
both cases, there is exactly one solution, shown in 3.4(b) and 3.4(c), taking
all the cells into one block. ∎

The wire can be extended to an arbitrary height by appending wire gadgets on
top of each other, since the extended gadget will preserve its properties.
Each appended wire gadget will extend the wire height by two. Observe in
Figure 4, if we negate the colors, i.e. the cells in the left column are gray
while the cells in the right column are white, the gadget will preserve its
properties. Furthermore, the gadget is invariable with respect to rotation and
mirroring. All gadgets in this study will satisfy these properties, since they
directly follow from the puzzle properties. Therefore, in the rest of the
thesis, we will use them without explicitly addressing them.

(a) An unsolved wire boundary gadget. The optional area is in the blue
rectangles, while the area outside it is mandatory.

(b) Starting wire communicating true, or terminating wire communicating false.

(c) Starting wire communicating false, or terminating wire communicating true.

Figure 5: Wire boundary gadget with the profile table. The green area is not
covered by the gadget solution.

In Figure 5 we present the wire boundary gadget. This gadget will be used to
start the new wires and to terminate unused ones. Observe that its value will
be interpreted differently depending on whether it is used to start or
terminate the wire.

######  Lemma 3.

The wire boundary gadget does not enforce wire value.

###### Proof.

Solutions for the both possible wire values are shown in 3.5(b) and 3.5(c). ∎

######  Theorem 2.

The profile table of the wire boundary gadget is complete.

###### Proof.

There are three possible cases in which solution, not shown in 3.5(a), may
exist. We will argue each case separately:

  1. 1.

There exists another solution that covers the whole gadget and it is different
than the one in 3.5(b). Since our gadget has six cells, four of which have an
integer $\bm{2}$, all four of them must be in the same block. This forces the
two cells on the top of the gadget to be tiled together. Hence, we reached the
contradiction, because that solution is already shown in the figure.

  2. 2.

There exists another solution that covers the mandatory area, but it does not
cover an optional area and it is different than the one in 3.5(c). That
solution should tile four cells, while having cells with an integer $\bm{2}$.
The only way to tile them is with all four cells inside the one block. Again,
we reach the contradiction since that solution is already shown.

  3. 3.

There exists a solution that covers the mandatory area and the one cell of the
optional area. That solution should cover an odd number of cells, thus
violating the property of the puzzle that white and gray areas should have the
same size in each block. Hence, such a solution is impossible.

∎

Together we proved that the wire boundary gadget allows both possible wire
values, and it does not allow for any other solution. When it starts the wire,
it will determine its value. When it terminates the wire, it will do so
irrespective of its value.

(a) An unsolved right rotation gadget. Paired optional areas are in blue
rectangles, area outside them is mandatory.

(b) Redirecting wire communicating false on the right.

(c) Redirecting wire communicating true on the right.

(d) An unsolved left rotation gadget. Paired optional areas are in blue
rectangles, area outside them is mandatory.

(e) Redirecting wire communicating false on the left.

(f) Redirecting wire communicating true on the left.

Figure 6: Rotation gadgets with their profile table. Green areas are not
covered by the gadget solution.

We have presented the right and the left rotation gadgets in Figure 6. The
values shown apply in the case when the lower optional area receives the truth
value while the other optional area outputs it. In the opposite case, the
values will be opposite. Observe that they are the same gadget, because we can
get the left rotation gadget from the right rotation gadget after applying
vertical mirroring and color inversion. Hence, it is sufficient to discuss
only the right rotation gadget.

######  Lemma 4.

The right optional area of the right rotation gadget is covered if, and only
if, the bottom optional area is uncovered.

###### Proof.

If the bottom optional area is covered by the gadget solution, then it must be
in the same block as adjacent cells in the mandatory area, in order to have a
connected gray and white area. After that, the top two cells of the mandatory
area are forced to be in the same block, leaving the right optional area
uncovered. If the right optional area is covered by the gadget solution, then,
by similar argument, the bottom optional area remains uncovered. ∎

######  Lemma 5.

The right rotation gadget’s profile table is sufficient.

###### Proof.

We have already proven this statement in the proof of Lemma 4, by arguing that
there exists exactly one solution in which the bottom area is covered and one
in which it is uncovered, which are shown in 3.6(b) and 3.6(c), respectively.
∎

The rotation gadgets will be used at most once per wire, and when the left and
the right wires of the clause need to rotate toward the clause, as shown in
2.3(b).

Figure 7: The variable gadget. Optional areas are in the blue rectangles and
they represent the places where the wires enter and exit gadget.
Figure 8: Equalizer

###  3.2 The variable gadget

In Figure 7 we have presented the variable gadget. It consists of a sequence
of equalizers and two vertical segments. Equalizers connect neighbouring wires
while vertical segments are used to transfer the value of two wires with only
one neighbour, i.e. the furthest left and furthest right wires.

The first gadget the wire enters after starting in the wire boundary gadget
will be the variable gadget. Therefore, we know that optional areas where the
wires enter the gadget will either be fully covered of full uncovered. We will
prove all claims in this section under the constraint that optional areas are
never partially taken at the place the wire enters the gadget.

Observe that optional areas are paired in such a way that for each bottom
optional area there is a top optional area in the same column, and they
represent places where wires enter and exit the gadget. Wires can enter on
either side, depending on whether we need upward or downward wire. In the case
we need upward wire, the wire will enter the gadget on the bottom side and
will exit on the top optional area above it.

The equalizer connects the neighbouring wires so that either both upper
optional areas or both lower optional areas are forced to be covered by the
gadget’s solution. Because the wires are connected to those optional areas, if
the wires are going in the same direction, they will have the same value. If
one is going upward and other is going downward, they will have the opposite
values. The equalizer consists of:

  * •

Two columns, each comprising of four cells, are collectively called a
rectangle. Cells of the rectangle have an integer 2. A rectangle acts as an
equality constraint.

  * •

Four L shaped regions which will enforce the tiling of the optional areas
based on the tiling of the rectangle.

######  Lemma 6.

Equalizer has only two valid ways to cover its rectangle.

###### Proof.

Let’s order the rows of the equalizer’s rectangle from top to bottom, i.e. the
top row is row 1 and the bottom row is row 4. The second row can be tiled
together either with the first or with the third row.

If the second row is in the same block as the third row (see 3.9(b)), then the
top left cell of the rectangle is forced to be tiled with the top left L
shaped segment. A similar pattern applies on the top right, bottom left, and
bottom right cells.

Otherwise, if the second row is in the same block as the first row (see
3.9(a)), then the third row must be in the same block as the forth row. Thus,
forcing four cells adjacent to the rectangle to be tiled with their only
uncovered neighbours. This leaves the two the furthest left and furthest right
cells of the equalizer uncovered, which later must be tiled with the rest of
the gadget cells. ∎

(a) Value false.

(b) Value true.

Figure 9: The variable gadget with its profile table profile table.

######  Claim 1.

Each vertical segment has exactly two valid coverings.

###### Proof.

Coverings are shown in 3.9(a) and 3.9(b). It is easily observable that those
are the only two coverings. ∎

######  Theorem 3.

The variable gadget has a valid solution if, and only if, all top optional
areas have the same tiling, all the bottom optional areas have the same
tiling, and top and bottom optional areas have opposite tiling.

###### Proof.

We will split the proof of this theorem into the next two lemmas. ∎

######  Lemma 7.

The bottom optional area is covered by the gadget solution if, and only if,
its corresponding top optional area is not covered by that solution.

###### Proof.

Suppose the wire enters the gadget through one of the bottom optional areas.
If the wire communicates a true value, it will force its adjacent equalizers
to be tiled as shown in 3.9(b). If that wire is in between one of the two
equalizers, the two cells of the mandatory area above that optional area will
be forced to tile with the top optional area. The same argument follows if the
wire is connected to the equalizer and the vertical segment, since the
vertical segment will be forced to tile in a size four block.

Otherwise, if that wire communicates false, the bottom optional area must be
in the same block with its only two adjacent cells. This will force its
adjacent equalizers, or, if the wire is located on the far left or the far
right, the equalizer and the vertical segment, to be tiled as shown in 3.9(a).
Thus, forcing the four cells of the mandatory area, above the bottom optional
area, to be tiled together, leaving the top optional area uncovered.

Observe that with color inversion and without the top optional areas, our
gadget is symmetric about the horizontal line passing through the middle of
the equalizers. Also, observe that the top optional area can be tiled only
with the two adjacent cells of the mandatory area. Hence, when the wire enters
the gadget through one of the top optional areas, a similar argument as in the
previous case will apply, with inverted cases. That is, when the wire enters
on top optional area with the value true, we will argue in a similar way as
when the wire enters on the bottom with the false value, and conversely. ∎

######  Lemma 8.

The bottom optional area of the gadget is covered by the gadget solution, if,
and only if, the bottom optional area next to it is covered as well and
likewise for the top optional areas.

###### Proof.

As a direct consequence of the previous lemma, it is enough to prove this
statement only for the bottom optional area.

Suppose a wire enters the gadget through one of the bottom optional areas with
the value false, and the wire next to it enters the gadget through the bottom
with the value true, or equivalently on the top with the value false as
consequence of Lemma 7. The former wire will force the equalizer to be tiled
as in 3.9(a), leaving the cell next to the bottom optional area of the latter
wire uncovered, and unable to be tiled.

For the other direction, suppose the wire enters the gadget through one of the
bottom optional areas with the value true, and the wire next to it enters the
gadget through the top optional area with the value true, or equivalently on
the bottom with the value false. The former wire will force the equalizer to
be tiled as in 3.9(b). The bottom optional area of the latter wire must be in
the same block as the two cells adjacent to it, but that can be done since one
of them is already covered by the tiling of the equalizer. ∎

By proving Theorem 3 we have confirmed that the variable gadget will have the
desired properties, i.e. that all the upward wires will have the same value,
all the downward wires will have the same value, and upward and downward wires
will have the opposite value. Observe that the variable gadget can be extended
from either side to fit an arbitrary number of wires, by adding more
equalizers (see Figure 10).

######  Lemma 9.

The profile table of the variable gadget is sufficient.

###### Proof.

The statement directly follows from Theorem 3, Lemma 6, and Claim 1. ∎

The variable gadget is the first gadget into which the wire enters after
starting in the wire boundary gadget. Therefore, we will assume that each wire
will start from the boundary wire gadget which is directly connected to the
variable gadget. The wire will come out on the other side, if that wire is
used, or there will be another wire boundary gadget to terminate unused wire.
That we create the complete variable gadget (see Figure 10).

######  Theorem 4.

Every upward wire of the complete variable gadget will communicate the same
value, every downward wire will communicate the same value, and upward and
downward wires will communicate the opposite values.

###### Proof.

The proof follows from the construction of the complete variable gadget and
Theorem 3. ∎

In Figure 10, we show the construction of the complete variable gadget, with
the two upward wires (the leftmost and the rightmost wires), two downward
wires (the second and the third wire), and one terminated wire. Upward wires
communicate the false value, while the downward wires communicate the true
value, which is as expected since the complete variable gadget has a false
value.

Figure 10: The complete variable gadget with the false value. Intersections of
optional areas are in blue rectangles, optional areas covered by the solution
of the gadget are in yellow rectangles, while optional areas not covered by
the solution are in red rectangles.

###  3.3 Clause gadget

(a) Unsolved gadget.

(b) (true, false, false)

(c) (false, true, false)

(d) (false, false, true)

(e) (true, true, false)

(f) (true, false, true)

(g) (false, true, true)

(h) (true, true, true)

Figure 11: The OR subgadget with the profile table. In the first figure,
optional areas are in the blue rectangles. The other figures show possible
solutions when at least one optional area is covered by an adjacent gadget.
Solutions are shown as (left, middle, right) based on whether the
corresponding optional area is fully covered or fully uncovered by an adjacent
gadget.

In this section we will present the last required piece for our reduction, the
clause gadget. It should receive the value from the three wires, and enforce
that at least one of the incoming wires communicates the true value. However,
as it turns out, the gadget is not as simple as it looks at first glance,
hence we will construct it step by step, through the introduction of
subgadgets, which will eventually combine into the clause gadget.

After the wire exits the variable gadget, it either directly enters the clause
gadget or goes through the rotation gadget. Hence, its optional areas are
either fully covered or fully uncovered and we will assume so, and not argue
the case when the optional areas are partially covered.

In Figure 11, the OR subgadget is shown. It consists of three optional areas
separated by mandatory areas.

######  Lemma 10.

The OR subgadget is solvable if, and only if, at least one optional area is
covered by its adjacent gadget.

###### Proof.

For the latter direction, the proof is shown in Figure 11 (b) - (h), where we
show one gadget solution for each combination. Observe that there exists one
more solution for the cases shown in (g) and (h), in which the segment of the
cells with an integer 4 are in the same block as the two cells on their left,
while the cells on their right are in a size two block.

On the other hand, suppose that there exists a solution to the OR subgadget,
which covers all three optional areas. The left optional area must be in the
same square block as its two adjacent cells, forcing the middle optional area
to be in the same square block as the two cells on its right. The right
optional area can be tiled only with the cells on its left. Hence, leaving the
six cells with an integer 4 to be uncovered. Since they are the only uncovered
cells, they cannot be tiled. ∎

Even though the OR subgadget has the desired property of the clause gadget, it
cannot be the clause gadget since it has a problem. The problem which arises
is that the middle wire cannot be connected to the OR subgadget without
overlapping of their mandatory areas, which is not allowed. So we come up with
an idea to resolve it:

Figure 12: Idea for the solution of the OR subgadget problem.

In Figure 12, we presented the idea for the solution to the above mentioned
problem by introducing another element represented by
$\mathrel{\raisebox{-1.0pt}{\framebox(1.0,1.0)[]{$\scriptstyle\rotatebox[origin={c}]{45.0}{+}$}}}$
, which we will call the crossover subgadget. We first split the middle wire
by columns into its left and the right part. We then connected the right part
of the middle wire with the lower cell of the middle optional area of the OR
subgadget. The left part of the middle wire is navigated to the bottom of the
crossover subgadget. Meanwhile, the left wire enters the crossover subgadget
on its left side. The crossover subgadget should convey the value of the left
wire on its right side, from where the wire will be connected to the left
optional area of the OR subgadget. The left part of the middle wire should
exit on the top of the crossover subgadget, from where it will go toward the
OR subgadget and will be connected to the upper cell of the middle optional
area.

(a) An unsolved crossover subgadget.

(b) (false, false)

(c) (false, true)

(d) (true, false)

(e) (true, true)

Figure 13: The crossover subgadget with its profile table. The paired optional
areas are in the rectangle of the same color. Cells not covered by the
subgadget solution are filled with green. In the subfigures (b) - (e), the
solutions are shown as (value of left wire, value of the middle (its left
part) wire).

The crossover subgadget is shown in Figure 13. The left wire will enter the
subgadget on its left optional area, and it will exit it on the opposite side.
The left part of the middle wire will be connected to the gadget on its bottom
optional area, while exiting it on its top optional area.

######  Lemma 11.

The optional area of the crossover subgadget is fully covered by the gadget
solution if, and only if, its pair is fully uncovered.

###### Proof.

In Figure 13 (b) - (d), we show the solutions for each combination of the of
the optional area coverings. It is straightforward to check that any other
tiling of the subgadget is not prohibited. ∎

######  Lemma 12.

The profile table of the crossover subgadget is sufficient.

###### Proof.

By the same argument as in Lemma 11. ∎

Thus, we have proven that the crossover subgadget will convey the value of the
incomming wires on the opposite sides from the ones they enter, as we wanted.

We can now present the clause gadget, constructed as the combination of the
previous subgadgets, in Figure 16. In the figure we can observe that the
crossover subgadget is on the left side, and its right optional area is glued
together with the left optional area of the OR subgadget. However, there is
still one part of the gadget we did not discuss: the part that connects the
middle optional area of the clause gadget with the middle optional area of the
OR subgadget. We will call it the middle wire split subgadget (see Figure 14).
We will first discuss its properties then return to the clause gadget.

(a) An unsolved middle wire split subgadget. The black is the mandatory area
of the crossover subgadget. The areas in blue, red, and yellow rectangles are
the optional areas with the middle wire, the crossover, and the OR subgadgets
respectively.

(b) The split middle wire communicating false.

(c) The split middle wire communicating true.

Figure 14: The middle wire split subgadget with solutions for the different
values of the middle wire. The green ares are covered by adjacent gadgets.

In Figure 14, we can see that the subgadget shares two optional areas with the
crossover subgadget, while the right optional area represents the connection
with the OR subgadget. The middle wire split subgadget will transfer the value
of the middle wire from the blue optional area to the middle optional area of
the OR subgadget (yellow optional area).

######  Lemma 13.

The middle optional area of the OR subgadget is covered by the solution of the
middle wire split subgadget if, and only if, the middle wire communicates
true.

###### Proof.

If the middle wire has the value false, then the blue optional area must be in
the same block as the cells on its left and right. Hence, the lower red
optional area will be in the same block as the cell on its right. Therefore,
by Lemma 11, the upper optional area is not covered by this solution. On the
way inducing the solution shown in 3.14(b).

If the middle wire communicates the true value, then the cell on the left of
the blue optional area in the above figure must be in the same block as its
only uncovered neighbour. Thus, leaving the lower red optional area uncovered
by the gadget solution. Hence, by Lemma 11, the upper red optional area must
be covered by the solution of the middle wire split subgadget, forcing the
solution shown in 3.14(c). ∎

With this in mind, we can prove that our clause gadget works as it should.

######  Theorem 5.

The clause gadget is solvable if, and only if, at least one incoming wire
communicates the true value.

###### Proof.

By Lemma 11, the left optional area of the OR subgadget is covered by the
crossover subgadget if, and only if, the left wire has the true value. Lemma
13 implies that the middle optional area of the OR subgadget is covered by the
solution of the middle wire split subgadget if, and only if, the middle wire
communicates true. That combined with Lemma 10 proves the statement. ∎

Figure 15: The clause gadget. The optional areas are in the blue rectangles,
representing the places where the clause receives the value from the wires.

(a) An unsolved color inversion gadget.

(b) Inverting the color of the wire communicating communicating true.

(c) The first solution of inverting the color of the wire communicating false.

(d) The second solution of inverting the color of the wire communicating
false.

Figure 16: The color inversion gadget with the profile table. Paired optional
areas are in blue rectangles. It receives the value on the lower optional
area, while it outputs it on the upper one.

Even though our clause gadget has desired characteristics, there is one
problem that still may occur. Some wires incident to the gadget may have the
opposite coloring of the one in the optional areas. Although the clause gadget
is invariant on the color inversion, the color inversion will change coloring
of all the optional areas, which may shift the problem to other optional
areas. Hence, we need a different solution.

The solution to this problem is the color inversion gadget, presented in
Figure 16. This gadget will receive the truth value from the wire on its lower
optional area, and the color inverted wire of the same value will then exit on
its upper optional area.

######  Lemma 14.

The profile table of the color inversion gadget in Figure 16 is sufficient.

###### Proof.

It is easy to check that the only solutions where the optional areas are
either covered or uncovered are shown in Figure 16 (b) - (d). ∎

######  Lemma 15.

The lower optional area is the covered by the solution of the color inversion
gadget if, and only if, the upper one is not covered.

###### Proof.

The proof immediately follows from Figure 16 and Lemma 14. ∎

The color inversion gadget will be required only when the wire arrives to the
clause gadget, thus we can make the color inversion gadget the integral part
of the clause gadget. We will call such gadget the complete clause gadget (see
Figure 17). Since the clause gadget is invariant with respect to color change,
we can let the middle wire determine the coloring of the gadget. Depending on
the coloring of the left and right wire, we will either use or not use the
color inversion gadgets.

If the color of the wire should be changed, we will append the color inversion
gadget surrounded from both sides with the wire gadgets, otherwise we will
append the longer wire gadget. Observe that this is not necessary, but we will
do it in order to ensure the width of the clause gadget remains unchanged.
Newly adopted parts of the gadget will only transfer the value of the wire
with the possible inversion of the wire’s color.

Figure 17: The complete clause gadget. The places where the wires are
connected to the gadget are in blue rectangles. The optional areas shared
between the color inversion gadgets and additional wire gadgets are shown in
yellow rectangles. Area in the purple rectangles is the area where the newly
added parts of the gadget are connected with the gadget from Figure 16. We can
observe that color of the left wire is inverted while the color of the other
wires remains unchanged. The two smaller segments not connected to the rest of
the gadget are not the part of the gadget. They serve as possible replacements
for the parts below them in the case that the left or the right wire have
different coloring than the optional areas of the gadget.

######  Lemma 16.

The complete clause gadget is solvable if, and only if, at least one incoming
wire communicates the true value.

###### Proof.

The proof is an immediate consequence of the construction of the complete
clause gadget, and Theorem 5, Lemma 1, and Lemma 15. ∎

Observe that the place where the left and the right wires enter the gadget are
equally distanced from the middle optional area, in a way that emulates
2.3(b).

###  3.4 Connecting the dots

We will construct the puzzle starting from the instance of Bent RPM-3SAT (see
2.3(b)), and convert each of its parts to the equivalent gadget.

First, we start from the variable line. We will place all the complete
variable gadgets on the same row of the puzzle, with enough space (even number
of cells) between their closest cells, so that even the wires of the adjacent
variables can be connected to the same clause. Next, we place the complete
clause gadgets according to the figure, either above or below the variable
line, depending on whether the clause is positive or negative. The middle
optional area of the complete clause gadgets must be in the same columns as
the optional area of the complete variable gadgets, where their middle wires
will exit. We widen the space between the clauses more than in the figure, to
ensure that there will be an empty space between them, as well as with the
wires. Finally, we draw the wires, starting from the complete variable
gadgets, using the wire gadgets to connect it to the complete clause gadgets.
The middle wire can be directly connected to the clause. We will draw the left
and the right wires of the clause until the wire’s optional area is in the row
below or above, for positive and negative clauses respectively, the optional
area where it should enter the gadget. Then, we append the desired rotation
gadgets on top of the wire gadgets, and from there extend the wires enough to
connect it with the complete clause gadgets.

######  Lemma 17.

All three wires of every complete clause gadget can be connected to it.

###### Proof.

In order to connect the middle wire of the clause with the complete clause
gadget, the optional area where the wire exits the complete variable gadget
must be an odd number of rows away from the optional area where it enters the
complete clause gadget. Hence, we will space them accordingly when
constructing the puzzle. If we append the rotation gadget directly on the left
or the right optional area of the complete clause gadget, and we put the wire
gadget with the three rows of the mandatory area on the other side of the
rotation gadget, the bottom optional area of the wire gadget will be in the
same row as the middle optional area of the complete clause gadget while there
will be 12 columns in between them. That distance can only be extended for an
even number of columns, by adding another wire gadget in between the rotation
and the complete clause gadgets.

Because any two complete variable gadgets have even distance between them,
which we choose, and the horizontal distance between each wire until the end
of its complete variable gadgets is even, the distance between any two wires
in the puzzle is even.

Hence, we can position the complete variable gadgets so that all three wires
of all of the complete clause gadgets can be connected to them. ∎

Since our construction follows the planar drawing, there would be no
intersections of the gadgets. Because we created additional space between the
gadgets, we forbid unwanted interference between non connected gadgets.

######  Lemma 18.

The arbitrary shaped Double Choco is in the NP.

###### Proof.

Given the certificate (the set of blocks) to the puzzle instance, we can
validate it in the polynomial time by checking if the set of the blocks
satisfies the Double Choco properties from chapter 1. ∎

######  Lemma 19.

If the Bent RPM-3SAT has n variable and m clauses, then our reduction (puzzle)
has the size polynomial in $n+m$ and it can be performed in polynomial time.

###### Proof.

The construction of the puzzle follows the Bent RPM-3SAT embedding, hence the
height of the puzzle is $O(m)$. Meanwhile, its width is $O(w)$, where $w$
represents the number of wires of the Bent RPM-3SAT. Since the number of edges
in the planar graph is at most linear in the number of the vertices, we have
that the width of our puzzle is $O(n+m)$. Hence, the size of our puzzle is
polynomial in $n+m$. Translation of each element of the Bent RPM-3SAT
(variable, wire or clause) to the homologous gadget and its inserting to the
puzzle, takes the most polynomial time. Thus, our reduction is performed in
the time polynomial in $n+m$. ∎

######  Lemma 20.

The Bent RPM-3SAT is solvable if, and only if, the puzzle is solvable.

###### Proof.

Given the solution to the Bent RPM-3SAT instance, we can configure the
complete variable gadgets to have the same value as their respective variables
in the original problem. The wire and the rotation gadgets will transfer that
value to the complete clause gadgets. Since, in the original problem, each
clause is connected to at least one literal with true value, the complete
clause gadgets will be solvable because at least one of its adjacent wire
gadgets communicates true.

If the puzzle is solvable, then by the property of the complete variable
gadget, each wire gadget carries either the true or the false value. That
value is propagated to the complete clause gadgets which are all solvable.
Hence, the assigning of the variable’s value of the original problem,
according the to value of the respective complete variable gadgets, provides
at least one true literal per the clause of the Bent RPM-3SAT. ∎

######  Theorem 6.

The arbitrary shaped Double Choco is NP-complete.

###### Proof.

Immediately from the previous three statements. ∎

##  Chapter 4 Double Choco is NP-complete

In this chapter we come back to our original problem. We will prove that the
Double Choco with the rectangular $m\times n$ board is NP-complete, by using
the results from chapter 3 and slightly modifying the gadgets, while leaving
their properties unchanged, and filling the empty areas in the board.

Our gadgets will be surrounded by a thin layer, called a shield, which
satisfies the following:

  * •

The shield can be tiled by using solely its own cells.

  * •

None of the shield’s cells can be in the same block as any of the internal
gadget cells in any puzzle solution.

These properties will ensure that any puzzle solution has a valid profile
assignment. If the puzzle was not solvable prior to shielding, the shield will
not make it solvable.

By shielding the gadgets, we prohibit undesired interference between the non
connected gadgets, as well as interference between the external areas with the
gadgets. We will present the shielded gadgets in section 4.1, section 4.2, and
section 4.3.

Even now, it can happen that we have holes in our puzzle, between the shields
of the different gadgets, thus, we need to fill them. That will be done by
using fillers. In section 4.4, we will argue that all the holes in our puzzle
have the specific shape that will allow us to cover them whenever the puzzle
is created according to the described procedure. Both the shields and the
fillers are external areas (see section 2.3), meaning that they consist only
of mandatory areas.

Because each optional area belongs to the two gadgets, it must be shielded by
only one of them, to avoid the shields overlapping. Hence, we decide to
surround the optional areas with the shield of the gadget that receives the
value through it, while the optional areas will not be shielded on the gadgets
which outputs the value on it.

All the shielded gadgets in this chapter can be extended in a similar way as
in chapter 3 and additionally following the described shielding pattern.

(a) Wire gadget with the shield.

(b) Right rotation gadget with the shield.

(c) Left rotation gadget with the shield.

Figure 18: The wire and rotation gadgets with the shield. Shield is
represented as the covered area. Optional areas are in the blue rectangles.

###  4.1 Shielding the wire and rotation gadgets

In Figure 18, we have presented the shielded version of the wire and rotation
gadgets. The shield is represented with the areas containing an integer 1,
surrounding the gadgets everywhere except on the optional areas. The wire
gadget stays unmodified, and, on the other hand, our rotation gadgets from
Figure 6 are extended with the wire gadgets appended to both of their optional
areas, in order to shield them easier. Every gadget in the above figure has
one optional area surrounded by the shield and one not. We will call them the
input and output optional area respectively.

######  Claim 2.

The shields of the gadgets in Figure 18 can be tiled by solely using its own
cells.

###### Proof.

The solution is shown in the figure. ∎

######  Lemma 21.

None of the shield’s cells in the above figure, can be in the same block as
the any of the gadget’s cells.

###### Proof.

Any of the shield’s cells are either filled with a different integer than its
adjacent gadget’s cells, or it has the same color as the adjacent gadget’s
cells, while having an integer 1 in it. Thus, by the Double Choco properties,
they cannot be in the same block. ∎

######  Claim 3.

The properties of shielded gadgets stay the same as in the ones in section
3.1.

###### Proof.

The statement follows from their construction and Lemma 21. ∎

Figure 19: The complete variable gadget with the shield. The shield is
represented by the covered area. Optional areas are in the blue rectangles.

###  4.2 Shielding the complete variable gadget

We present the shielded complete variable gadget in Figure 19 with the three
wires, two going upwards and one going downward. The gadget stays mainly
unmodified, except where we added additional wire gadgets on the lower side,
in between the optional area of the variable gadget (see Figure 7) and the
wire boundary gadgets, or the wire gadgets, depending on the case. Observe,
that the all optional areas are the output ones.

Holes between the equalizers and the vertical lines, as well as the ones
between the two equalizers are filled with the areas of the 5 and 10 integers
respectively. Even though there cannot be any interference between the
neighbouring gadgets, if we filled them arbitrarily we risk the ill behaviour
of our gadget.

######  Claim 4.

The shield of the gadgets in Figure 19 can be tiled by solely using its own
cells.

###### Proof.

The solution is shown in the figure. ∎

######  Lemma 22.

None of the shield’s cells in the above figure can be in the same block as the
any of the gadget’s cells.

###### Proof.

Every shield’s cell with the integer 1 in it, if directly adjacent to the
gadget, has the neighbour inside the gadget of the same color, thus, they
cannot be in the same block. It is easy to check that any cell with the
integers 4, 5 or 10 cannot be in any other block different from the ones shown
in Figure 19. ∎

######  Claim 5.

The properties of the shielded gadget stays the same as its counterpart in
section 3.2.

###### Proof.

The statement follows from the construction and Lemma 22. ∎

Figure 20: The complete clause gadget with the shield. The gadget is separated
from the shield by the black border. Shield is represented as the covered
area. The optional areas are in the blue rectangles. Areas in the red are
those that depend on the color of the wire. Therefore, on both of those areas
we can use either one of them.

###  4.3 Shielding the complete clause gadget

In Figure 20, we present the complete clause gadget with the shield. As
expected, the gadget has the only input optional areas. The only modified part
of the gadget in Figure 17, is the middle optional area where we extend the
gadget by appending an additional wire gadget on its optional area. The gadget
with the shield misses the four rectangular areas in order to have rectangular
shape. We omitted presenting those rectangles in the figure in order to
simplify it. We will prove in the next claim that they can be filled to
satisfy the shield’s properties. Hence, from now on, we will assume that the
complete clause gadget with the shield has rectangular shape.

######  Claim 6.

The shields of the complete clause gadget can be tiled solely using its own
cells.

###### Proof.

Part of the solution is shown in Figure 20. For the four rectangular areas not
shown in the figure, observe that the width of all four of them is even, hence
by Lemma 24, they can be filled with $2\times 1$ disjointed rectangles. We can
make each rectangle have one white and one gray cell with the integer 1 in
them, and they will satisfy the properties of the shield. ∎

######  Lemma 23.

If the gadget and the shield in the above figure has a solution, than none of
the shield’s cells can be in the same block as any of the gadget’s cells in
any solution of the puzzle.

###### Proof.

Any shield’s cell, except some in the yellow and the purple rectangle, have
the integer 1 in it, and if they it is directly adjacent to the gadget, all
its neighbours inside the gadget have the same color or different integer in
it, thus, they cannot be in the same block.

The white cells of the upper yellow area can be tiled only with gray cells of
the same area. Furthermore, the gray cells in the lower yellow area must be in
the same block as its corresponding white cells.

The upper purple area is surrounded with cells with the integer 1 on all sides
except for the interior of the gadget. Because the the gray cells of the area
must be in the same block as the lower white cell, the whole area will be in
the same block. Otherwise, the upper white cell will remain uncovered and it
cannot be tiled on the any other way. The same argument applies for the lower
purple area.

We are left to prove that the middle yellow area must be locally solved.
Observe that its cells in the second row must be covered with the cells above
them, also the right cells in the third row must be in the same block as the
cell below it. Hence, we have to prove that the left cells in the third and
the fourth row must be in the same block, and we will do so by contradiction.
Assume that they are not in the same block, then the left cell in the third
row is tiled with the cell on its left, while the cell in the fourth row is in
the same block as the cell below it. But, then, the white area left of the
bottom row of this area cannot be tiled. Hence, we have reached the
contradiction. ∎

######  Claim 7.

The properties of shielded gadget stays the same as its counterpart in section
3.3.

###### Proof.

The statement follows from the construction and Lemma 23. ∎

###  4.4 Connecting the dots

We will follow the same construction as in section 3.4, and increase the space
between the gadgets to make room for the shields. Let us assume that the
leftmost column of the leftmost complete variable gadget is the first column
of our puzzle, while the rightmost column of the rightmost complete variable
gadget is the last column of the puzzle. Observe that, because those gadgets
have even width, and they are evenly spaced, our puzzle also has even width.

Now we will prove that the remaining holes in our puzzle can be filled by the
filler areas.

######  Lemma 24.

Every rectangle with an even number of cells in at least one dimension can be
represented as the union of the disjointed $2\times 1$ rectangles.

###### Proof.

Let’s suppose that the rectangle’s have an even number of columns, a similar
argument applies when the number of rows is even. Take one row, it has an even
number of cells, so we can split it into $2\times 1$ rectangles. Doing the
same for the each row, we get a desired set of rectangles. ∎

######  Theorem 7.

Every empty area of our puzzle can be separated into the union of the
disjointed rectangles with the even width.

###### Proof.

We will argue that the space between any of the gadgets in our construction
has even width. First observe that every shielded gadget has even width. Since
our construction follows 2.3(b), we can observe that horizontally adjacent
elements of the graph can be:

  1. 1.

Variable with another variable - by our construction every two shielded
complete variable gadgets are distanced horizontally by an even number of
cells.

  2. 2.

Wire with another wire - By the previous item, any two complete variable
gadgets are evenly spaced. Additionally, any wire gadget is the even number of
columns away of the vertical borders of its complete variable gadget (see
Figure 19). Thus, any two wire gadgets are distanced horizontally by an even
number of cells.

  3. 3.

Clause with another clause - by the construction the middle wire gadget will
be connected directly to the complete clause gadget. By the previous item, the
middle wires of the different clauses are evenly spaced. Furthermore, the
middle optional area of the complete clause gadget is an even number of cells
horizontally away from both the left and right edges of the shielded complete
clause gadget (see Figure 20). Thus, the horizontal distance between any
shielded wire and complete clause gadget is even.

  4. 4.

Wire with the clause - the wire gadget has an even distance to the middle wire
of the corresponding complete shielded clause gadget, hence its distance to
the complete shielded clause gadget is even as well.

In the previous enumeration we exclude rotation gadgets because they can have
the horizontal empty area only on the one side, opposite of the rotation, but
on that side, it has the same horizontal coordinates as its input wire gadget.
Hence, we looked at it as the part of the wire gadget.

Because the puzzle is bounded it has two more types of empty areas: from the
vertical edge of the puzzle to the the shielded wire gadget, or the complete
shielded clause gadget. But those cases are similar to the second and the
fourth item in the previous enumeration, since each border is touching the
shielded complete variable gadget, which has even width and even horizontal
distance to all shielded wire and complete shielded clause gadgets. Thus,
those horizontal distances are even as well. ∎

######  Lemma 25.

Empty areas of our puzzles can be filled with the filler areas.

###### Proof.

Combining Theorem 7 with Lemma 24, we get that the empty areas of the puzzle
can be represented as the union of disjointed $2\times 1$ rectangles. Let each
rectangle have one white and one gray cell, while both of them are labeled by
the integer 1. Then, each rectangle can be tiled using solely its own cells. ∎

######  Theorem 8.

Double Choco in NP-complete.

###### Proof.

Since the shielded gadgets satisfied all the properties of the matching
gadgets in chapter 3, all the statements from section 3.4 holds here as well.
And by Lemma 25 we can fill all the holes in the puzzle. Hence, we conclude
the proof. ∎

’It’s not about the destination, it’s about the journey.’

R. W. E.

## References

  * [Add+18] Allen Addison, Daniel Packer, Sophia White and Aaron Williams  “Pencils and Sto-Stone are NP-complete [paper in review]” Last accessed 18 January 2022, 2018  URL: https://www.researchgate.net/profile/Aaron-Williams/project/Computational-Complexity-of-Video-Games-and-Puzzles/attachment/5aa7c402b53d2f0bba57bfb9/AS:603697591619584@1520944130196/download/PencilsStoStone_InReview.pdf?context=ProjectUpdatesLog/
  * [Adl+15] Aviv Adler, Michael Biro, Erik D Demaine, Mikhail Rudoy and Christiane Schmidt  “Computational complexity of numberless Shakashaka.”  In _CCCG_ , 2015
  * [Adl+20] Aviv Adler, Jeffrey Bosboom, Erik D Demaine, Martin L Demaine, Quanquan C Liu and Jayson Lynch  “Tatamibari is NP-complete”  In _arXiv preprint arXiv:2003.08331_ , 2020
  * [Alg22] Fun Algorithms  “FUN 2022” Last accessed 19 January 2022, 2022  URL: https://sites.google.com/view/fun2022/home
  * [AW18] Addison Allen and Aaron Williams  “Sto-Stone is NP-Complete.”  In _CCCG_ , 2018, pp. 28–34
  * [And09] Daniel Andersson  “Hashiwokakero is NP-complete”  In _Information Processing Letters_ 109.19 Elsevier Science, 2009, pp. 1145–1146
  * [AB09] Sanjeev Arora and Boaz Barak  “Computational complexity: a modern approach”  Cambridge University Press, 2009
  * [BS17] Michael Biro and Christiane Schmidt  “Computational complexity and bounds for Norinori and LITS”  In _Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), Malmö, Sweden_ , 2017, pp. 29–32
  * [Coo71] Stephen A Cook  “The complexity of theorem-proving procedures”  In _Proceedings of the third annual ACM symposium on Theory of computing_ , 1971, pp. 151–158
  * [DK12] Mark De Berg and Amirali Khosravi  “Optimal binary space partitions for segments in the plane”  In _International Journal of Computational Geometry & Applications_ 22.03 World Scientific, 2012, pp. 187–205
  * [Dem+14] Erik D Demaine, Yoshio Okamoto, Ryuhei Uehara and Yushi Uno  “Computational complexity and an integer programming model of Shakashaka”  In _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ 97.6 The Institute of Electronics, InformationCommunication Engineers, 2014, pp. 1213–1219
  * [ĐG21] Dragoljub Đuric and Mika Göös  “Filament Constellation problem is NP-complete [Unpublished semester project at École polytechnique fédérale de Lausanne]”, 2021
  * [Fri02] Erich Friedman  “Pearl puzzles are NP-complete” Last accessed 23 January 2022  In _Unpublished manuscript, August_ Citeseer, 2002  URL: https://hobbydocbox.com/Board_Games_and_Puzzles/68074679-Pearl-puzzles-are-np-complete.html
  * [Hap86] Happa  “Double Choco editor” Last accessed 18 January 2022, 1986  URL: https://puzz.link/p?dbchoco/
  * [HD09] Robert A Hearn and Erik D Demaine  “Games, puzzles, and computation”  A K Peters, 2009
  * [HKK04] Markus Holzer, Andreas Klein and Martin Kutrib  “On the NP-completeness of the nurikabe pencil puzzle and variants thereof”  In _Proceedings of the 3rd International Conference on FUN with Algorithms_ , 2004, pp. 77–89  Citeseer
  * [HR07] Markus Holzer and Oliver Ruepp  “The troubles of interior design–a complexity analysis of the game Heyawake”  In _International Conference on Fun with Algorithms_ , 2007, pp. 198–212  Springer
  * [ISI12] Ayaka Ishibashi, Yuichi Sato and Shigeki Iwata  “NP-completeness of two pencil puzzles: Yajilin and Country Road”  In _Utilitas Mathematica_ 88 UTIL MATH PUBL INC UNIV MANITOBA PO BOX 7 UNIV CENT, WINNIPEG, MANITOBA R3T …, 2012, pp. 237–246
  * [Iwa14] Chuzo Iwamoto  “Yosenabe is NP-complete”  In _Journal of Information Processing_ 22.1 Information Processing Society of Japan, 2014, pp. 40–43
  * [KT15] Shohei Kanehiro and Yasuhiko Takenaga  “Satogaeri, Hebi, and Suraromu Are NP-Complete”  In _2015 3rd International Conference on Applied Computing and Information Technology/2nd International Conference on Computational Science and Intelligence_ , 2015, pp. 46–51  IEEE
  * [KT10] Kouichi Kotsuma and Yasuhiko Takenaga  “NP-completeness and enumeration of number link puzzle”  In _IEICE Technical Report COMP2009–49, IEICE_ , 2010
  * [Lev73] Leonid Anatolevich Levin  “Universal sequential search problems”  In _Problemy peredachi informatsii_ 9.3 Russian Academy of Sciences, Branch of Informatics, Computer Equipment and …, 1973, pp. 115–116
  * [Lim20] Guardian News & Media Limited  “Can you solve it? Double chocolate!” Last accessed 29 January 2022, 2020  URL: https://www.theguardian.com/science/2020/apr/06/can-you-solve-it-double-chocolate
  * [McP05] Brandon McPhail  “Light Up is NP-complete” Last accessed 23 January 2022  In _Unpublished manuscript_ , 2005  URL: http://www.mountainvistasoft.com/docs/lightup-is-np-complete.pdf
  * [MM11] Cristopher Moore and Stephan Mertens  “The nature of computation”  OUP Oxford, 2011
  * [Nik20] Nikoli  “Double Choco” Last accessed 17 January 2022, 2020  URL: https://www.nikoli.co.jp/en/puzzles/double_choco/
  * [Nik22] Nikoli  “Nikoli puzzles” Last accessed 17 January 2022, 2022  URL: https://www.nikoli.co.jp/en/puzzles/
  * [Nik20a] Nikoli  “Puzzle the Giants Vol.33” Last accessed 29 January 2022, 2020  URL: https://nikolibookshop.stores.jp/items/5f06d38cfe00f04d4303b2c2
  * [Nik86] Nikoli  “Sudoku” Last accessed 18 January 2022, 1986  URL: https://www.nikoli.co.jp/en/puzzles/sudoku/
  * [Tak00] Yato Takayuki  “On the NP-completeness of the Slither Link puzzle (in Japanese)”  In _IPSJ SIGNotes ALgorithms_ , 2000
  * [Tak+13] Yasuhiko Takenaga, Shintaro Aoyagi, Shigeki Iwata and Takumi Kasai  “Shikaku and Ripple Effect are NP-complete”  In _Congressus Numerantium_ 216, 2013, pp. 119–127
  * [Yat03] Takayuki Yato  “Complexity and completeness of finding another solution and its application to puzzless. Master’s thesis, University of Tokyo, Tokyo, Japan.” Last accessed 23 January 2022, 2003  URL: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.6324&rep=rep1&type=pdf
  * [YS03] Takayuki Yato and Takahiro Seta  “Complexity and completeness of finding another solution and its application to puzzles”  In _IEICE transactions on fundamentals of electronics, communications and computer sciences_ 86.5 The Institute of Electronics, InformationCommunication Engineers, 2003, pp. 1052–1060