An ASP-Completeness Framework for Dynasty Puzzles

Under certain conditions, TRVB is known to be ASP-complete.

A grid graph is a graph whose vertices are a subset of ${\mathbb{Z}}^2$ and whose edges connect pairs of vertices with Euclidean distance one. A grid graph is rectangular if its vertex set is $V=\{1,\mathrm{\dots },m\}\times \{1,\mathrm{\dots },n\}$ for some integers $m,n\ge 1$. We refer to the pair $(m,n)$ as the dimensions of the rectangular grid graph. Furthermore, when we consider a spanning subgraph $G$ of an $m\times n$ rectangular grid graph (i.e., $G$ contains all vertices of the grid), we also refer to $G$ as having dimensions $m\times n$.

A Hamiltonian cycle in a graph is a cycle that visits each vertex exactly once. The Hamiltonian Cycle Problem (HCP) asks whether a given graph contains a Hamiltonian cycle. Reference [3] establishes the complexity of HCP on grid graphs and their max-degree-3 subgraphs (i.e., subgraphs where every vertex has degree at most three). We focus on the following two theorems.

We sketch a direct reconstruction of the proofs for Theorem 4 based on [3, Theorem 4.6].

Figure 1 illustrates the core idea of the gadgets used in the reduction. This is a degree-4 breakable vertex gadget, with the yellow square in the center representing the vertex itself, and the blue tentacles representing edges. This gadget admits exactly two local configurations compatible with a Hamiltonian cycle: the yellow region is in the interior of the Hamiltonian cycle (Figure 2(a)), or in the exterior (Figure 2(b)). The former corresponds to not breaking the vertex, while the latter corresponds to breaking it. We can embed a planar TRVB instance into a grid graph by replacing each breakable vertex with such a gadget and connecting the tentacles according to the edges of the TRVB instance. By [3, Lemma 2.4], Hamiltonian cycles in the constructed graph correspond one-to-one with the solutions of the original TRVB instance.

The first step of this phase involves simulating grid graphs and Hamiltonian cycles within dynasty puzzles. Figures 6(a) and 6(b) illustrate this simulation.

In Figure 6(a), the red, blue, and yellow cells collectively form an embedding of a grid graph. Within this embedding, the red and blue cells are forced to be shaded (except for the top light-red cell); specifically, the red cells correspond to the vertices of the grid graph, while the blue cells correspond to its faces. Its edges are represented by yellow $2\times 2$ squares, each constrained to contain exactly two shaded cells. Each such square admits exactly two local solutions diagonally connecting either the red cells or the blue cells, corresponding to whether the edge is included in the Hamiltonian cycle or not (Figure 7).

This diagonal connectivity of the colored cells corresponds directly to the topological relationship between the vertices and the faces in the original grid graph: if the edge is in the cycle (Figure 7(a)), the two vertices are directly connected and the two faces are separated by that edge; otherwise (Figure 7(b)), the vertices are disconnected and the faces are connected (i.e., they are on the same side of the cycle).

Now we consider the local constraint that no diagonal chain of red cells terminates at a dead end, that is, no vertex has degree $1$. This constraint, in fact, under the rules of dynasty puzzles, is equivalent to the red cells forming a Hamiltonian cycle on the grid graph (since the light-red cell acts as a break, ensuring that a Hamiltonian cycle on the grid graph does not form a loop of shaded cells). While the forward implication is straightforward, the converse is more subtle. Let us now examine this in detail. Suppose, for the sake of contradiction, that the red cells do not form a Hamiltonian cycle. Given the premise that no chain terminates at a dead end, the configuration of red cells is disconnected or, if connected, branches at some point (i.e., has degree at least $3$ at some vertex). We consider these two cases separately: If the red cells were disconnected, we could choose a component that does not contain the light-red cell. Then, the blue cells surrounding this component would form a loop, violating the rule that all unshaded cells must form a connected region. Alternatively, if the connected red cells branched at some point, by elementary graph theory we could choose a loop that does not contain the light-red cell. Such a loop would partition the unshaded cells into interior and exterior regions, again violating the connectivity rules.

Figure 6(b) illustrates a configuration of local solutions that collectively form a Hamiltonian cycle. Here, the red cells constitute the resulting cycle, while the blue cells represent the connectivity of faces. As a result, the blocks of diagonally connected blue cells are partitioned by the red cycle into the interior and the exterior.

The second step of this phase is to simulate the gadgets introduced in Section 2 using the framework described above. The color scheme in the gadgets discussed below is identical to that in Figure 6(a).

Figure 8(a) illustrates a configuration of a degree-4 breakable vertex gadget (originally shown in Figure 3) for dynasty puzzles. This gadget functions equivalently to the original, provided that the red cells form a Hamiltonian cycle. As discussed above, this condition is equivalent to the requirement that no diagonal chain of red cells terminates at a dead end. This requirement can be enforced locally; specifically, by constraining each pair of yellow $2\times 2$ squares incident to a common red cell (vertex). Consequently, the reduction operates correctly through such local constraints.

Figure 8(b) illustrates a configuration of a degree-6 breakable vertex gadget (originally shown in Figure 5) for dynasty puzzles. Like the degree-4 gadget, this gadget functions equivalently to the original under the constraints on the pairs of yellow $2\times 2$ squares discussed above. A key property of this configuration is that the squares in each constrained pair are orthogonally adjacent.

Guide Arrow is a type of dynasty puzzle originally designed by Naoki Inaba [6]. The standard rules of dynasty puzzles apply, together with the following additional rules [12]:

1. 1.

   Cells with symbols (a star and arrows) must be unshaded.

2. 2.

   The unshaded cells must form a single rooted tree.

3. 3.

   A star denotes the root of the tree, and an arrow indicates the direction toward its parent cell.

In particular, this means that unshaded cells cannot form any $2\times 2$ blocks, as such blocks would create cycles. An example of Guide Arrow is shown in Figure 9(a) and its (unique) solution is shown in Figure 9(b).³³3Playable at https://puzz.link/p?guidearrow/6/6/23nemegdjbhe.

We reduce from Planar $(\{4\},\{1\})$-TRVB, considering the case of directed grid graphs. Light-green cells in Figures 10, 11, 12, 13, 15, and 15 represent cells forced to be unshaded.

Before constructing the gadget, we explain how to represent the directions of the edges in the cycle. First, let us consider the structural constraints of the diagonal chains of shaded cells. As illustrated in Figure 10, there are three topologically distinct configurations of the chains of shaded cells, depending on the directions of unshaded cells on both sides of them (except for cases involving the star). Specifically, these are parallel (Figure 10(a)), clockwise (Figure 10(b)), and counterclockwise (Figure 10(c)). These correspond to the edges, the interior faces, and the exterior face of the framework, respectively. In particular, the directions of unshaded cells in the parallel case correspond to the directions of the edges.

We now present the actual configuration of gadgets. Figure 11 illustrates a concrete example of the configuration of tentacle gadgets. All cells in this gadget are determined unconditionally. Figure 12 illustrates the breakable vertex gadget. Let us show that the gadget admits exactly two local solutions. We first consider one of the chains of red cells in Figure 12, which is directed inward. By the rule governing the directions of unshaded cells, unshaded cells on both sides of the chain must not connect. Therefore, the chain must touch the border of the puzzle board. Since all four chains of red cells share this constraint, the chains do not connect to each other. Note that this constraint is independent of the global layout of the reduction. Under this constraint, it is guaranteed that the only valid solutions are the two depicted in Figure 13. These two solutions are topologically identical to the broken and unbroken states of the breakable vertex (such as Figure 2).

Finally, we construct the auxiliary structures. Figure 15 illustrates the filler pattern. This pattern has a recursive structure, allowing it to fill a region whose diagonal length of shaded cells is $2^k-1$. We can rotate this pattern as needed. By Remark 6, the side length of the embedded rectangular grid graph can be set to $2(2^{2l}-1)/3$ for a suitable integer $l$. It follows that the diagonal length of shaded cells in the triangular regions is $2^{2l+1}-1$. Thus, we can fill these regions completely with this pattern. Figure 15 illustrates the aperture structure. This ensures that the shaded cells of both the cycle and the interior can reach the border, preventing the unshaded cells from forming a cycle. The star is placed at the opposite endpoint of the chain corresponding to the cycle.

The constructed reduction is parsimonious. Thus, we obtain the following theorem.

Aquapelago is a type of dynasty puzzle originally designed by Walker Anderson. The standard rules of dynasty puzzles apply, together with the additional rule that unshaded cells must not form any $2\times 2$ block. A number in a shaded cell indicates the size of its diagonally connected group of shaded cells [10]. An example of Aquapelago is shown in Figure 16(a) and its (unique) solution is shown in Figure 16(b).⁴⁴4Playable at https://puzz.link/p?aquapelago/8/8/2q3zu8j2j.k.

We reduce from Planar $(\{4\},\{1\})$-TRVB, considering the case of directed grid graphs. Light-green cells in Figures 17, 18, and 19 represent cells forced to be unshaded.

For the reduction, we prepare three distinct clue values, denoted by $A$, $B$, and $C$. These values correspond to the blocks of shaded cells in the exterior of the cycle, the cycle itself, and the interior of the cycle, respectively. We will show later that these values are well-defined.

Based on these clues, we construct the reduction. Figure 17 illustrates the breakable vertex gadget. Each undetermined $2\times 2$ area must contain exactly two shaded cells to avoid forming a $2\times 2$ block of unshaded cells, admitting exactly two local solutions. Moreover, assuming that $A$ and $C$ are distinct, the blocks of shaded cells with values $A$ and $C$ must not be connected, ensuring that no chain of shaded cells with value $B$ terminates at a dead end. This behavior matches exactly the condition required for the gadget described in Section 3.2. The tentacles can be constructed by simply placing clues with values corresponding to the components of the grid graph.

Figure 18 illustrates the filler patterns for the regions between the gadgets and the puzzle board border. We can rotate and reflect this pattern as needed. In light of Remark 6 and the configuration of the embedded grid, the diagonal chain of shaded cells has a period of length $6$. The pattern in Figure 18 matches this period, and thus we can fill these regions completely. Next, we illustrate the aperture structure in Figure 19. This structure aligns with the filler pattern.

Finally, we determine the values $A$, $B$, and $C$. Let $G$ be the spanning subgraph of a grid graph constructed from the embedding of the Planar $(\{4\},\{1\})$-TRVB instance, and let $2m$ and $2n$ be its dimensions. Every Hamiltonian cycle in $G$ clearly consists of $4mn$ vertices and $4mn$ edges. Since each vertex corresponds to one cell and each edge to two cells, it follows that $B=12mn-1$ (accounting for the aperture).

The core of the argument for $A$ and $C$ relies on the following well-known proposition.

In particular, since the interior faces induce a tree in the dual graph, the number of edges lying strictly inside the cycle is $mn/2-2$. For completeness, we provide the proof in Appendix A.

Applying Proposition 8, it follows immediately that $C=6mn-5$. To determine $A$, we first consider the area outside the cycle. The total area of the entire grid graph is $(2m-1)(2n-1)$ and the area inside the cycle is $2mn-1$; thus, the area outside the cycle is $2(m-1)(n-1)$. Since the regions outside the cycle connect with each other through the exterior of the grid and form a single tree (in the dual graph), the number of edges completely outside the cycle is $2(m-1)(n-1)$. These two facts imply that the number of cells corresponding to these faces and edges is $6(m-1)(n-1)$. Next, we consider the boundary of the embedded grid and the filler patterns. In Figure 18, for each side of the embedded grid with length $2l$, the length of the diagonal chain of the shaded cells is $6l+1$, and the chain is connected to $3l$ shaded cells in the filler. Since the entire grid graph is of size $2m\times 2n$, the total number of such cells is $18(m+n)-5$ (accounting for the aperture). Summing these two values, we obtain $A=6mn+12m+12n+1$. This satisfies the assumption that $A$, $B$, and $C$ are distinct.

The constructed reduction is parsimonious. Thus, we obtain the following theorem.

Heyawake is a type of dynasty puzzle originally introduced in Puzzle Communication Nikoli Vol. 39. The board is divided into rectangular regions called rooms. The standard rules of dynasty puzzles apply, together with additional rules concerning the rooms. Specifically, a number in a room indicates the number of shaded cells in that room. Also, a straight line of unshaded cells must not span across three rooms (hereinafter referred to as the three-room constraint) [13]. An example of Heyawake is shown in Figure 20(a) and its (unique) solution is shown in Figure 20(b).⁵⁵5Playable at https://puzz.link/p?heyawake/8/8/b28i4gq6llc0733g1vo0s07g2g12h1h03i.

We reduce from Planar $(\{6\},\mathrm{\varnothing })$-TRVB via the grid graph embedding. Light-green cells in Figures 21, 22, 23, 25, and 25 represent cells forced to be unshaded.

First, we describe the fixed structures used in the embedded grid graph. Figure 21 illustrates the fixed structures of the descending (top-left to bottom-right) orientation. There are two types of structures: vertical and horizontal. Each $1\times 1$ room at the four corners of the structures corresponds to a vertex of the grid graph, and the (vertical or horizontal) $2\times 4$ region consisting of six rooms corresponds to an edge of the grid graph. The structures of the ascending (bottom-left to top-right) orientation can be obtained by reflection. The entire embedding can be tiled by arranging these two types of structures alternately according to parity.

Based on these structures, we construct the embedding of the grid graph. Figure 22 illustrates the breakable vertex gadget. The validity of this gadget is verified as follows. Let us consider a $2\times 2$ undetermined block structure shown in Figure 23(a). In each row, the two undetermined cells are flanked by unshaded cells across the room boundaries. Due to the three-room constraint, exactly one of the two undetermined cells in each row must be shaded. Consequently, the $2\times 2$ block admits exactly two local diagonal configurations: either descending or ascending (Figure 23(b)). Furthermore, for any pair of adjacent blocks, their diagonal orientations must be consistent, as illustrated in Figure 23(c). This synchronization is again enforced by the three-room constraint; a mismatch would result in a line of unshaded cells spanning three rooms. This behavior matches exactly the condition required for the gadget described in Section 3.2.

The tentacles are constructed by simply placing fixed structures with the corresponding diagonal orientations (descending or ascending).

The filler pattern and the aperture structure are illustrated in Figures 25 and 25. The red $1\times 1$ room in Figure 25 is inserted exclusively at the right corner of the embedded grid graph. The filler pattern admits a unique solution unconditionally, while the aperture admits a unique solution consistent with the solution of the remainder of the instance.

The constructed reduction is parsimonious, and uses only clues of value 1. Thus, we obtain the following theorem.

Furthermore, we observe that the solution structure is preserved even if we assign 0 to all rooms forced to be completely unshaded and remove all clues of 1. This leads to the following corollary.

These results strengthen the ASP-completeness of Heyawake shown in [5].

Ayeheya is a variant of Heyawake. The standard Heyawake rules apply, together with the additional rule that the shaded cells within each room must be point-symmetric with respect to the room’s center [11]. An example of Ayeheya is shown in Figure 26(a) and its (unique) solution is shown in Figure 26(b).⁶⁶6Playable at https://puzz.link/p?ayeheya/8/8/ikl6a2gk5180007nu07000fg23h1l.

While we can apply most gadgets in Section 4.3 directly to Ayeheya, we need to modify the breakable vertex gadget (Figure 22) to ensure the point symmetry condition. We replace each corner of the chain of the $2\times 2$ blocks of undetermined cells in the gadget with the configuration shown in Figure 27. Specifically, we use the configuration in Figure 27(a) for the top-left corner, a 180-degree rotated version for the bottom-right corner, the configuration in Figure 27(b) for the top-right corner, and a 180-degree rotated version for the bottom-left corner.

With this modification, the breakable vertex gadget satisfies the point symmetry condition and remains parsimonious. Thus, we obtain the following theorem.

Akichiwake is a type of dynasty puzzle. The rules are identical to those of Heyawake, except that a number in a room indicates the maximum size of orthogonally connected blocks of unshaded cells in that room (without crossing the boundaries) [9]. An example of Akichiwake is shown in Figure 28(a) and its (unique) solution is shown in Figure 28(b).⁷⁷7Playable at https://puzz.link/p?akichi/8/8/jcr5h8a2gk00007f600c03vg23g1g6047g4.

We derive the reduction for Akichiwake from that of Heyawake by replacing every clue $1$ with $0$. Since all clues of value $1$ in the Heyawake construction are placed within $1\times 1$ rooms, this modification preserves the validity of the reduction. Specifically, both a $1\times 1$ room with a clue $1$ in Heyawake and a $1\times 1$ room with a clue $0$ in Akichiwake must be shaded. Hence, we obtain the following theorem.

Hitori is a type of dynasty puzzle first introduced in Puzzle Communication Nikoli Vol. 29. The standard rules of dynasty puzzles apply. Each cell contains a number, and the goal is to shade some cells such that no number appears more than once in each row and column [14]. An example of Hitori is shown in Figure 29(a) and its (unique) solution is shown in Figure 29(b).⁸⁸8Playable at https://puzz.link/p?hitori/6/6/416253643251333162142365151421522634.

We reduce from Planar $(\{6\},\mathrm{\varnothing })$-TRVB via the grid graph embedding. Light-green cells in Figures 30, 32, 32, 33, 35, and 35 represent cells forced to be unshaded.

To begin with, to enforce the configuration of shaded cells in the gadgets, we construct the two-cell-wide perimeter strip shown in Figure 30. On the outer region of the strip, shaded cells are placed in every other cell, while the inner region is entirely unshaded. In particular, the second row from the top is entirely unshaded, forcing this row to consist of distinct numbers. This forces any cell in the subsequent rows containing the same number as the second row (in the same column) to be shaded. We denote these fixed shaded cells by $B$, and assign a distinct number to each remaining fixed unshaded cell.

Next, we construct the reduction. Figure 32 illustrates the breakable vertex gadget. The validity of this gadget is verified as follows. Let us examine the two patterns illustrated in Figures 32 and 33. The former corresponds to the partial pattern appearing in the horizontal chain of $2\times 2$ undetermined blocks, while the latter corresponds to that in the vertical chain.

We first explain the horizontal case illustrated in Figure 32(a). In this row, each number appears twice. Considering the rules of Hitori, unshaded numbers must be unique in each row; thus, at least one of these two instances must be shaded. On the other hand, due to the adjacency constraint of shaded cells, each of the left and right components can contain at most one shaded cell. Consequently, the pattern admits exactly two local configurations, as shown in Figures 32(b) and 32(c). Next, we explain the vertical case illustrated in Figure 33(a). Similarly, in each of the two columns, a number appears twice, necessitating that at least one instance is shaded. Combined with the adjacency constraint of shaded cells, it follows that the pattern admits exactly two local configurations, as shown in Figures 33(b) and 33(c).

Applying this result to each pair of adjacent undetermined blocks in the breakable vertex gadget, we verify that each block admits exactly two diagonal orientations of shaded cells (descending or ascending) and that these orientations must be consistent throughout the gadget. This behavior precisely matches the required condition. Since both global configurations are legal, the breakable vertex gadget is valid.

The tentacles are constructed by simply placing the fixed shaded cells $B$. Figures 35 and 35 illustrates the filler pattern and the aperture structure. Since these structures touch the unshaded cells of the perimeter strip on the side illustrated by dotted grid lines, these structures admit a unique solution.

The values of the clues are bounded by $O(mn)$, where $m,n$ are the dimensions of the embedded grid; thus, these configurations can be constructed in polynomial time. Thus, we obtain the following theorem.

Kurodoko is a type of dynasty puzzle first introduced in Puzzle Communication Nikoli Vol. 34. The standard rules of dynasty puzzles apply. A number indicates the total number of unshaded cells visible from that cell in (up to) four directions, including the cell itself [15]. An example of Kurodoko is shown in Figure 36(a) and its (unique) solution is shown in Figure 36(b).⁹⁹9Playable at https://puzz.link/p?kurodoko/8/8/j52y33p33y68j.

We reduce from Planar $(\{6\},\mathrm{\varnothing })$-TRVB via the grid graph embedding. Black dots in Figures 37, 38, 40, and 40 represent cells forced to be unshaded.

The breakable vertex gadget is illustrated in Figure 37. The validity of this gadget is verified as follows: let us consider the local pattern illustrated in Figure 38(a). If either the cell above or below the two vertically aligned clues with value 3 were to remain unshaded, both right and left cells of the two 3s must be shaded to satisfy the clues. Now two shaded cells are adjacent vertically, which contradicts the rules. Thus, both the cells above and below the 3s must be shaded. Consequently, one unshaded cell extends either to the right or left direction from each 3. If these unshaded cells both extended in the same direction, again two shaded cells would be adjacent vertically. Therefore, this pattern admits exactly two configurations: Figure 38(b) and its reflection. Applying this logic to all $2\times 2$ undetermined blocks in the gadget, we can see that the gadget functions as intended.

The tentacles are constructed by placing clues in all forced unshaded cells, except for those where the clue value would be 4. It can be verified that these clues indeed fix the structure. Figures 40 and 40 illustrates the filler pattern and the aperture structure. These structures admit a unique solution when combined with the tentacles.

Since the reduction uses no clues greater than $3$, we obtain the following theorem.