Completing the Complexity Classification of 2-Solo Chess: Knights and Kings Are Hard

We first argue briefly that the variable gadgets are work as expected. Note that a VAR gadget never produces a $1$-signal on both the positive and the negative side. This also holds for 2VAR gadgets: if it produces a $1$-signal on the positive side, then both input values of the AND gadget are $1$. Thus, both VAR gadgets produce $0$-signals on the negative side. Moreover, if both a $0$- and a $1$-signal are produced on the side with two outputs, it is never worse to produce two $1$-signals instead by monotony (Observation 1). Thus, we may assume that the signals on this side are equal.

The wire gadget can be seen in Figure 5.

We show that the wire can propagate the input signal correctly. On the other hand, we show that there are no normalized capturing sequences with better output, which yields the following lemma.

Figure 5 shows a normalized capturing sequence that produces the correct output for each possible input. In both cases, the signal eats up the wire, and every two moves the number of columns with kings is reduced by $1$ while preserving the input signal.

On the other hand, we show that there is no normalized capturing sequence that outputs $1$ if the input is $0$. Let $k$ be the number of columns with two $2$-kings. Then, without the input square, the wire has $k+2$ columns and $2k+4$ kings in total. Each column of the wire except for the input and the output square forms a vertex cut in the capture graph. Thus, each of the $k+1$ columns contains one virtual $0$-king by Lemma 2. Moreover, the output king never captures in a normalized clearing sequence and is thus a virtual $0$-king as well. Thus, with input $i$, every normalized capturing sequence has at most $i+2\cdot (2k+4-(k+1)-1)=i+2k+4$ total virtual budget, and at most $i+2k+4$ kings can be cleared. Since the input is a $0$-king, which does not contribute additional budget, any clearing sequence results in a $0$-king. $◀$ Normalized capturing sequences for the corner gadget with expected outputs are also depicted in Figure 5. As the capture graph of a wire with corner is a subgraph of the capture graph of a straight wire, there is no normalized capturing sequence for input $0$ that outputs $1$, i.e., a wire with corners also computes the identity function.

The OR gadget can be seen in Figure 6 with normalized capturing sequences that produce the correct output for each possible input. It remains to show that there is no normalized capturing sequence with better output.

We show that if both inputs are $0$, it is impossible to output $1$. The capture graph of the OR gadget has three disjoint vertex cuts $\{C,D\},\{E,H\},\{I,J\}$. By Lemma 2, each vertex cut contains a virtual $0$-king. Moreover, the output king never captures in a normalized clearing sequence. As the gadget (including output but excluding input) has nine kings in total, every normalized capturing sequence has a total virtual budget of at most $2\cdot (9-4)=10$ (without the inputs). With this budget, at most ten kings can be cleared, which is exactly the number that needs to be captured. Since both inputs are $0$-kings, which do not contribute additional budget, every normalized clearing sequence results in a $0$-king. $◀$

We show that the AND gadget can output the expected signal, but there is no normalized capturing sequence with better output.

Figure 7 shows normalized capturing sequences with the desired output if both inputs are $0$ or if both inputs are $1$. In the other two cases, where one input is $0$ and the other is $1$, there are normalized capturing sequences that output $0$ by Observation 1.

It remains to show that if at least one input is $0$, then it is impossible to output $1$. We first argue in the following that the number of virtual $0$-kings is at least $7$ (without the inputs) for every normalized capturing sequence. In a normalized capturing sequence, the output square always is a virtual $0$-piece as it does not move. The gadget contains the vertex cuts $\{C,D\},\{I,M\},\{K,L\},\{N,O\}$ (see Figure 7), which contain at least one virtual $0$-king each by Lemma 2.2. Moreover, virtual $0$-kings are connected by Lemma 2.1. We observe that to connect the virtual $0$-kings in the four vertex cuts and the output king, at least seven virtual $0$-kings in total are needed. Without the inputs, this gives us a virtual budget of at most $16$, which is also the number of kings that need to be cleared. Thus, if at least one input is $0$, then no capturing sequence with more than seven virtual $0$-kings clears the gadget.

Consider a normalized capturing sequence $s$ with seven virtual $0$-kings. If both inputs are $0$, the output of $s$ cannot be $1$ since the virtual budget is not sufficient.

If one input is $1$, we argue that $s$ loses budget by showing that there is no placement of the virtual $0$-kings such that all needed properties from Lemma 3 are satisfied. We distinguish between cases based on whether king $L$ is a virtual $0$-king.

If king $L$ is a virtual $0$-king, then the only way to connect the four vertex cuts using seven virtual $0$-kings is to choose $\{L,G,C,E,I,N\}$ and the output king. Any other way uses more than seven $0$-virtual kings. But then, $\{H,K,P\}$ are three virtual $2$-kings that only have two virtual $0$-kings in their neighborhood, which is a contradiction to Lemma 3.

If king $L$ is not a virtual $0$-king, then king $K$ is a virtual $0$-king. We further distinguish the cases which kings in $\{F,G,H\}$ are virtual $0$-kings. If none of them or only king $F$ is a virtual $0$-king, then $\{H,L,P\}$ are virtual $2$-kings that only have two $0$-kings in their neighborhood. If at least two of $\{F,G,H\}$ are virtual $0$-kings, then there are at least eight virtual $0$-kings and the budget is not sufficient to clear the gadget.

Otherwise, either king $G$ or king $H$ is a virtual $0$-king. Then, king $D$ is, too: This holds for king $G$ since otherwise, $\{H,L,P\}$ does not have enough virtual $0$-kings in its neighborhood. For king $H$, this holds since otherwise, the regions cannot be connected using seven virtual $0$-kings. Moreover, the kings $C$, $E$ and $P$ are not virtual $0$-kings since otherwise, the regions cannot be connected using seven virtual $0$-kings. With the same argument, king $O$ is a virtual $0$-king. Now, we know that $D$, $K$, $O$, $Q$ and either $G$ or $H$ are virtual $0$-kings, while $C$, $E$, $F$, $L$, $P$ and either $G$ or $H$ are not. If input $a$ is $1$, then $\{C,G,H,L,P\}$ contains four virtual $2$-kings, but is only connected to at most three virtual $0$-kings ($D$, $K$, and either $G$ or $H$). If input $b$ is $1$, then $\{P,L,H,G,F,E,I,M\}$ contains six virtual $2$-kings (since $I$ and $M$ cannot both be chosen). However, they are all not connected to input $a$, to king $O$ and the output king. Thus, they have at most five virtual $0$-kings in their neighborhood.

Thus, by Lemma 3, $s$ loses budget, and the output cannot be $1$. $◀$

The crossing gadget takes two inputs $a$ and $b$ and outputs two signals $\tilde{a}$ and $\tilde{b}$. It contains a 2VAR gadget that feeds $\neg \tilde{b}$ into the X* gadget and outputs $\tilde{b}$. The idea of the crossing gadget is that there is a normalized capturing sequence if and only if $\tilde{b}\le b$. Moreover, in this case, the gadget should output $\tilde{a}\le a$. These conditions ensure that an incoming $0$-signal never becomes a $1$-signal. The first table in Table 1 shows the desired outputs for the X* gadget for the three inputs $a$, $b$ and $\neg \tilde{b}$.

There are three additional gadgets IN-A, IN-B and OUT that check the inputs (see Figure 8), which are concatenated by a modified wire. Other than the usual gadgets, the output of IN-A and IN-B as well as the input of IN-B and OUT is not a single square, but a combination of two squares. Moreover, the wire between IN-A and IN-B as well between IN-B and OUT does not end with a wire connector. As a consequence, we can input and output more types of signals. The $0$-signal and the $1$-signal is the same as before: one square has a $0$- or a $1$-king, respectively, and the other square is empty. Additionally, there is a $2$-signal where one square has a $2$-king and the other square has a $1$-king. Note that a $2$-signal can be trivially transformed into a $1$-signal. Moreover, the modified wire can output a $2$-signal if the input is a $2$-signal, see Figure 9. Conversely, we note that $0$- and $1$-inputs can never become $2$-signals. This means that monotony from Observation 1 also applies to $0$-, $1$-, and $2$-signals.

Table 1 shows the functions for IN-A, IN-B, and OUT. We note that concatenating the three functions as shown in Figure 8 yields the desired function X*. We have a gadget for the IN-B-function and the OUT-function, for the IN-A-function, we can use the same gadget as for IN-B by swapping the inputs.

Assuming the correctness of each gadget, the correctness of the $X$ gadget directly follows. Figure 9 shows the IN-B gadget and the OUT gadget. In the IN-B gadget, the upper input of the IN-B gadget corresponds to the output of the IN-A gadget while the left input is signal $b$. In the OUT gadget, the left input corresponds to the output of the IN-B gadget while the upper input is signal $\neg \tilde{b}$. The following lemmas prove that the gadgets work as expected; see the full paper for the proofs.

Each column of the wire forms a cut, containing one inner knight and one outer knight. By Lemma 2.2, at least one of of these is a virtual $0$-knight. Thus, it suffices to show that no outer knight is a virtual $0$-knight. Assume for contradiction that there is an outer knight that is a virtual $0$-knight, say $E$. By Lemma 2.3, at least one neighbor of $E$, without loss of generality $G$, is a virtual $2$-knight. Then, $F$, $H$ and $J$ are the virtual $0$-knights of the cuts $\{F,G\}$, $\{G,H\}$ and $\{G,J\}$ respectively. As a result, both neighbors of virtual $0$-knight $H$ are virtual $0$-knights themselves, a contradiction to Lemma 2.3. The claim follows. $◀$

By the previous lemma, the inner knight of the column does not capture the outer knight to its right. If it captures to the left, the outer knight in its column becomes a cut vertex and virtual $0$-knight, again violating the previous lemma. $◀$ Using these properties, we define an ordered way to clear the wire: For each column, all captures from or to its left happen strictly before all captures from or to its right. Any capturing sequence clearing the wire can be brought into this form by repeatedly swapping consecutive moves that are ordered incorrectly. If the two moves do not share a square, they can safely be swapped. Otherwise, for a move from the right and a move from the left to interfere, they must share their destination square, namely the inner knight of the middle column. By Corollary 16, the move from the right is by an outer knight. Then, performing the left move followed by the right move results in a knight with budget 1, which is no less than without the swap. Thus, the resulting configuration is greater or equal than without the swap, and by monotony, the capturing sequence remains valid.

Using ordered clearing sequences, we define possible signal values. Observe that due to the knight’s parity constraints, wire columns alternate between dark-squared and light-squared columns. We define how to read off the value of a signal on a dark-squared wire column. This is done right after the final move from the column to its left. At this point, each column to the left is cleared while each column to the right is untouched. Our signal then consists of two binary components, so possible signal values are $(0,0),(0,1),(1,0)$ and $(1,1)$. The first component depends on the outer knight of the signal column. Since no outer knight is captured, the two options are for it to be present as a 2-knight, or to not be present at all. In the first case the component has value $1$, in the second case it has value $0$. The second component depends on the inner knight of the column. Being a virtual $0$-knight, it is not present as a $2$-knight, only with budget $0$ or $1$ (the latter occurs if it was captured by the outer knight to its left). We define the second signal component as the budget of this inner knight. Figure 11 shows two possible signal values and how to propagate them through the wire.

The $(1,0)$- and $(0,1)$-signals are unusual in that they are dual to each other. A $(1,0)$-signal reads off a dark-squared column the same as a $(0,1)$-signal would on a light-squared column. Nevertheless, for parity reasons a $(1,0)$-signal is never converted into a $(0,1)$-signal and vice versa. We see this in the proof of Lemma 14.

Figure 11 sketches how to obtain capturing sequences for each of the four signal values. In particular, for a second component of $0$ or $1$, the sequence starts with captures $(D\to B\to C)$ or $(B\to C)$ respectively. For a first component of $0$ or $1$ it continues with $(E\to C\to F)$ or $(A\to C\to F)$. Finally, for a second component of $1$, a final move $(D\to F)$ is appended.

To see that signal values never increase, we again consider the difference between the total virtual budget and the number of pieces of the wire. For the extreme case of just one column, this difference is precisely one lower than the number of $1$’s in the signal, i.e., for signal $(0,0)$ it is -1, for signal $(1,1)$ it is 1 and for signals $(0,1)$ and $(1,0)$ it is 0. Each additional wire column contributes two units of virtual budget and two pieces. Thus, the difference never increases. It follows that signal values propagated through the wire do not increase.

Finally, we show that a $(1,0)$-signal indeed is never converted into a $(0,1)$-signal and vice versa. By the non-increasing difference above, any capturing sequence converting one into the other does not lose budget. Consider the configuration of a $(1,0)$-signal, as seen in Figure 11. The signal-column $0$-knight leaves its square eventually by a double capture from an adjacent $2$-knight, $(D\to B\to C)$. As this move does not interfere with any other moves, we may assume that it is the first pair of moves in the capturing sequence. In the resulting configuration, knight $C$ has two neighbors with a budget of $2$, $A$ and $E$. If it is captured by $E$, the eventual capture of $A$ to its only neighbor loses budget. Otherwise, $A$ captures $C$ and $F$, restoring a $(1,0)$-signal. The reverse case is analogous. $◀$

To align wires and gadgets on the board, we give a number of placements of the wire on the chess board. We note that each of these correspond to the same capture graph, thus, the wire functions identically in each of the placements. Figure 12(a) shows a wire turning a corner, while Figure 12(b) has a wire turning into a thick wire.

Combining these enables the wire crossing, seen in Figure 12(c), without the need for a dedicated wire crossing gadget.

While the king wire can have any length, the knight wire only repeats every four columns. In Figure 12(e), we give an additional placement to shift the wire (diagonally) by a single square to be able to align wires correctly for their gadgets. Note that due to parity, dark-squared columns are always mapped to dark-squared columns, so it is impossible to shift the wire by a single non-diagonal square. However, as inputs to gadgets are of a fixed color, they can still always be aligned correctly. Finally, after passing a series of corners and gadgets, a wire may be oriented so as to have the dark-squared column be aligned towards the top or towards the bottom. To switch between those two modes, we give a rotation placement, seen in Figure 12(d).

For input $(1,0)$, knight $A$ is present with a budget of 2. Then the sequence $(D\to B\to C),(A\to C\to E),(G\to F\to E)$ reduces the gadget to a single piece, as claimed.

For input $(0,0)$, knight $A$ is not present. By Lemma 4, any clearing sequence $s$ (with final square $E$) can be assumed to start with captures $(G\to F\to E)$. Since knight $B$ is the only neighbor of $D$, it is captured by $D$ at some point. Its only path to final square $E$ is via $C$, so $s$ contains the capture $(B\to C)$. As knight $B$ has a budget of at most 1 before this capture, it results in a 0-leaf on $C$, only adjacent to 0-leaf $E$. We conclude that no such clearing sequence $s$ exists. $◀$

Consider knight $G$, highlighted in blue. Observe that, by Observation 5, no clearing sequence contains the capture $(H\to G)$. Instead, knight $G$ can be captured via $(F\to G)$ which after resolving captures $(G\to H),(E\to D)$ yields a $(1,1)$-signal on the left and a $(0,0)$-signal on the right wire, the first of the three possible outcomes.

The remaining options are those where the blue knight is not captured and instead makes a capture itself: If it captures to the left through $(G\to F\to E),(C\to E\to D)$, this creates a $(0,0)$-signal on the left and (after captures $(H\to J\to L),(I\to L)$) a $(1,1)$-signal on the right wire. If instead it captures to the right through $(G\to H)$, this creates a $(0,1)$-signal on the right. Then, after a captures $(F\to E\to D)$, the left wire receives a $(1,0)$-signal. This covers all possible cases for the blue knight and the capture sequence as a whole, and yields the claimed three possible outcomes. $◀$

We first consider the case where the first input component is 0, i.e., knight $A$ is not present. Then both neighbors $B$ and $E$ of virtual $0$-knight $C$ are themselves virtual $0$-knights, so by Lemma 2.3, the gadget cannot be fully cleared.

Next consider the case where the first input component is 1, i.e., knight $A$ is present. Propagating the signal as usual in a wire yields the claimed output. We show that no better output is possible: The first output component is 0 by the fact that the would-be outer knight of the column of $E$ already is not present. Furthermore, a virtual budget argument shows that any signal is decreased by at least 1. As a result, $(1,0)$ is mapped to (at most) $(0,0)$ and $(1,1)$ is mapped to (at most) $(0,1)$. $◀$ In the following subsections we utilize the counterpart of the Decrement gadget, namely the Increment gadget.

The first-component Increment (or $+(1,0)$) gadget increments the first component of a signal, as shown in Figure 15.

Figure 15 shows that the $(1,0)$-gadget allows a capturing sequence that sets the first component of a signal to 1. To see that no larger (or incomparable) output is possible, it suffices to show that if the second component of the output is 1, then so was the second component of the input. For this, consider an output of $(x,1)$, read off in the column containing knights $F$ and $G$, i.e., knight $G$ having a budget of 1 and all knights to its right being untouched. We now trace back how the knight got there. It was captured by a 2-knight, which was knight $D$, as $C$ is a virtual 0-knight and $I$ has not yet moved. Then $D$ did not capture $B$ and, thus, to leave its square towards $C$, knight $B$ was a 1-knight, meaning the input had a second component of 1.

The $+(0,1)$ gadget has a leaf adjacent to a dark-squared inner knight and functions identically. $◀$ This concludes our discussion of the VAR gadget. We remark that as in the king’s case, we can combine two VAR gadgets and an AND gadget to create the 2VAR gadget (see Figure 3).

Start by reducing the 2-antenna $(U,S,R)$ to a $0$-knight $R$ via captures $(U\to S\to R)$.

Consider now the case of a blue $(0,0)$-signal, i.e., knight $M$ is absent, while $N$ has a budget of $0$. Then the capturing sequence $(P\to N\to O),(Q\to O\to C),(T\to R\to C)$ leaves behind just the yellow wire (with virtual $0$-knight $C$ having an actual budget of 0). Thus, under this capturing sequence the gadget yields the identity function on the yellow signal, as expected.

For a blue input of $(1,0)$, knight $M$ is present and the capturing sequence $(P\to N\to O),(M\to O\to C),(Q\to R\to C)$ leaves behind a first-component Increment for the yellow signal in the form of 2-knight $T$. Conversely, for a blue input of $(0,1)$, knight $N$ has a budget of 1 and the capturing sequence $(N\to O),(Q\to O\to C),(T\to R\to C)$ leaves behind a second-component Increment in the form of 2-knight $P$. Finally, for a blue input of $(1,1)$, combining the two approaches through captures $(N\to O),(M\to O\to C),(Q\to R\to C)$ leaves behind both a first- and a second-component Increment in 2-knights $T$ and $P$. $◀$

It remains to show that no larger outputs are possible. We give this proof in the full version. Here we state without proof:

Placed at the top right of the AND gadget lies the AVP gadget, another value production gadget. Recall that the VAR gadget combined a 3-VAL and a Decrement gadget to produce outputs $(1,0)\leftrightarrow (0,0)$ or $(0,0)\leftrightarrow (1,0)$. Similarly, the AVP gadget produces outputs $(1,1)\leftrightarrow (0,0)$ or $(0,0)\leftrightarrow (1,0)$, by combining a 3-VAL and a Zeroing gadget (see Figure 18).

This Zeroing gadget sets a component of a signal to 0 regardless of its previous value. Consisting of an Increment followed by a Decrement gadget, its correctness follows directly from the correctness of its parts.

To see the correctness of the AVP gadget, we consider the different possible outputs of its 3-VAL gadget. For 3-VAL outputs $(0,0)\leftrightarrow (1,1)$ the gadget produces an overall output of $(0,0)\leftrightarrow (1,0)$. For 3-VAL outputs $(1,1)\leftrightarrow (0,0)$ or $(1,0)\leftrightarrow (0,1)$ the overall outputs are $(1,1)\leftrightarrow (0,0)$ and $(1,0)\leftrightarrow (0,0)$ respectively. By monotony the second of these is not chosen. Thus, this gadget correctly implements the asymmetric value production.

An analogous version of the gadget swaps the components of the outputs: Placing a $\cdot (0,1)$ gadget to the left of the 3-VAL gadget yields outputs $(0,0)\leftrightarrow (1,1)$ or $(0,1)\leftrightarrow (0,0)$ instead.

The top left of the AND gadget houses the Flip gadget, which is unpacked in Figure 19.

The Flip gadget computes the function that maps $(x,0)\in \{(0,0),(1,0)\}$ to $(0,x)\in \{(0,0),(0,1)\}$. To show its correctness, we consider the different possible inputs. Observe that the Flip gadget contains a Decrement gadget, enforcing that the output of the MAX gadget to its left has its first component set to 1. Thus, for an input of $(0,0)$ to the Flip gadget, any clearing sequence evaluates the AVP gadget to $(1,1)\leftrightarrow (0,0)$. In this case the signal undergoes the following transformations: $(0,0)\stackrel{max}{\to }(1,1)\stackrel{-(1,0)}{\to }(0,1)\stackrel{\cdot (1,0)}{\to }(0,0)\stackrel{max}{\to }(0,0)$. If the input to the Flip gadget is $(1,0)$, the AVP gadget can evaluate to $(0,0)\leftrightarrow (0,1)$ leading to the following sequence: $(1,0)\stackrel{max}{\to }(1,0)\stackrel{-(1,0)}{\to }(0,0)\stackrel{\cdot (1,0)}{\to }(0,0)\stackrel{max}{\to }(0,1)$. Overall this leads to the desired outputs.

Having understood its parts, we now turn our attention to the AND gadget itself. Its workings can directly be read off Figure 17. Its inputs $(x,0)$ and $(y,0)$ are combined to $(x,y)$ using a Flip and a MAX gadget. The two Decrements lead to an error, unless the signal going into them is a $(1,1)$-signal, in which case they produce a $(0,0)$-signal. Thus, if $(x,y)\ne (1,1)$, the AVP gadget produces a $(1,1)$-signal to the left, yielding an overall AND gadget output of $(0,0)$. If $(x,y)=(1,1)$, the AVP instead produces a $(0,0)$-signal to the left, yielding an overall output of $(1,0)$. We have seen: