From: Dominic Mazzoni Message-Id: <199710101731.TAA15971@turan.cs.elte.hu> Subject: Twixt_Proof_Draft To: sillke@lh-systems.de Date: Fri, 10 Oct 1997 19:31:42 +0200 (MET DST) Content-Type: text/plain; charset=US-ASCII Uncrossed Knight Paths is NP-complete Dominic Mazzoni Kevin Watkins Problem: Given a set of $n$ vertices, $v_1$ through $v_n$, each with integer coordinates $(x_{i},y_{i})$, with $1 \leq i \leq n$, let two vertices $v_i$ and $v_j$ be connected by an edge iff either $|x_{i}-x_{j}|=1 \wedge |y_{i}-y_{j}|=2$, or $|x_{i}-x_{j}|=2 \wedge |y_{i}-y_{j}|=1$. Thus two vertices are connected if they are a Knight's move apart. Two edges are said to cross iff the straight line drawn between its two vertices intersects the straight line between the two vertices of any other edge in the graph. Because all edges are the same length, it can be easily verified that each edge can cross at most nine other edges. The question: does there exist an uncrossed path from $v_1$ to $v_n$? This problem is shown to be NP-complete by reduction from 3-SAT. Introduction: The game of Twixt is usually played on a square board of about 19x19 holes. Two players are given pieces: the first player receives red pegs and red bridges, and the second player receives black pegs and black bridges. The red player's goal is to join the left and right sides of the board with a continuous path of red pegs connected by red bridges. The black player's goal is to use black pieces to connect the top and bottom sides of the board in a similar fashion. The players alternate turns, where a turn consists of the following three steps: 1. The player may remove any of his/her own color bridges from the board 2. The player must place a new peg in a hole on the board 3. The player may connect any pair of pegs of his/her own color with a bridge, when the pegs are a Knight's move apart, and when the bridge does not overlap any other bridge on the board. A player may place as many bridges as are possible on a single turn. A player has won when he/she has completed a connected path from the player's two extremes of the board. Because players are allowed to remove their own bridges and reposition them, drawn games are rare but not impossible. Consider the case where the red player is trying to determine whether two red pegs can be connected to one another. Call the two pegs in question peg $s$ and peg $t$. It may be that there exists an arrangement of the bridges such that there is an uncrossed path from $s$ to $t$, or it may be that no arrangement of bridges will create a path from $s$ to $t$ without some of the bridges crossing each other. For example, in Figure 1 part (a), the red player is trying to determine if $s$ and $t$ can be connected. In part (b), it can be seen that not any arrangement of bridges will work. In particular, this arrangement shows what would happen if the player attempted a Breadth-First Search (BFS) starting at $s$. Finally, in part (c), an arrangement of bridges is shown which does connect $s$ to $t$. . x . x . x . -x . x . x - / / \ . s . . . s- . / . . / s \ . . / / / / \ t . x . t / . x . t / . -x . / / - x . . . x . . . x- . . . (a) (b) (c) ************************ FIGURE 1 ************************ The single-color uncrossed knight path problem is as follows: Given a set of pegs belonging to a single color, and identifying two pegs as $s$ and $t$, we would like to know if there exists an uncrossed path between them. Note that in the game of Twixt, there is the added complication of the pegs and bridges belonging to the other player, which limits the possible locations for bridges to be placed. Let us call the two-color uncrossed path problem the question of whether $s$ and $t$ are connected, using only pegs and bridges of the same color as $s$ and $t$, in the presence of pegs and bridges of a different color. Note that if an algorithm was found for the two-color uncrossed path problem, it would immediately imply an algorithm for the single-color variation, though the reverse is not true. Therefore it will suffice to show that the single-color uncrossed path problem is NP-complete, and this implies the NP-completeness of the two-color problem as well. We model the single-color uncrossed knight path problem using a graph. Let the pegs of the Twixt board be vertices with integer coordinates, and let the bridges between the pegs be edges between the vertices in the graph. To show that the uncrossed path problem is NP-complete, we will reduce it from 3-SAT. In other words, we will show how any instance of the 3-SAT problem can be reduced in polynomial time to a corresponding uncrossed knight path problem such that a solution to the latter would immediately imply a solution to the former. 3-Satisfiability (3-SAT) is the following problem: We are given a set of boolean variables $v_{1} \dots v_{k}$, and a set of clauses $c_{1} \dots c_{n}$, with each clause being a boolean expression of the form ([not] v_{a} or [not] v_{b} or [not] v_{c}). Each clause must contain exactly three variables chosen from $v_{1} \dots v_{k}$, and use only or and not operators on them. Is there some assignment of true and false values to the variables such that every clause evaluates to true? This problem was shown to be NP-complete (Stephen Cook, 1971). The reduction from 3-SAT to uncrossed knight paths will be made by placing a number of gadgets on a very large grid. Some variable gadgets will be placed along the left side of the grid corresponding to the variables in the 3-SAT problem, and some clause gadgets will be placed along the top side of the grid, corresponding to the clauses in the 3-SAT problem, as in Figure 2. There will also be crossing gadgets in the center of the grid to facilitate connections between the variables and the clauses. The vertices $s$ and $t$ will be at either end of the variable gadget chain such that the only path between them involves going through all of the variables exactly once. The gadgets will be constructed in such a way that there will be an uncrossed path from $s$ to $t$ if and only if there is an assignment of the variables which satisfies all of the clauses. --- --- --- --- --- --- --- s C C C ... C C C C | --- --- --- --- --- --- --- --- V --- | --- V --- (connections between | variables and clauses) . . . | --- V --- | t ************************ FIGURE 2 ************************ Variable gadget: There are exactly two paths through each variable gadget, one of which corresponds to assigning the variable a value of true, the other corresponding to false. Since the path through the variable goes from top to bottom, let us assume that the true path is the left branch and the false path is the right branch, as shown in schematic in Figure 3, part (a). In the schematic drawings, assume that when two paths cross, this is a mutually exclusive crossing which allows only one of the two paths to connect. In part (b), we can see one possible arrangement of vertices for the corresponding uncrossed knight path layout. Note that there is no uncrossed path beginning at the top vertex which uses both branches - any valid path must take one branch or the other. | . . x . . | / \ . . . . . / \ \ / . x . x . \ / X . x . x . / \ / \ . . . . . T | | F | | T x . . . x F . . . . . . . . . . . . x . x . (a) (b) ************************ FIGURE 3 ************************ After splitting into two branches, the variable gadget then "visits" each of the clauses that this variable appears in. A schematic of a visitation of one particular variable is shown in Figure 4. It is okay that the true branch crosses the false branch, since only one of the branches will actually be taken. It is easily verified that there exists an arrangement of vertices in the grid such that the valid uncrossed knight paths correspond to the paths shown in the schematic. . . . . (Clause gadget) | | | T | | F | T | | F | | | | | | | | | | \ | | | | | ---+----------/ / | | | / | | ---+------------- | | / | | | | \ | | | ------------------/ / | / | --------------------- | / | | . . . . ************************ FIGURE 4 ************************ Clause gadget: The purpose of the clause gadget is to ensure that there is no valid path through the clause if its boolean expression would not be satisfied by the assignment of variables given. Remember that each clause is visited once by each variable it contains, and that it is visited along a "true" path if the variable is assigned to true, or along a "false" path otherwise. The only way that a clause is not satisfied is if all three assignments of variables evaluate to false in the clause. So the clause gadget is constructed as follows: For each variable, the branch that corresponds to the one in the clause gets looped back to itself, and the branch that corresponds to its negation gets looped around the other two variables, as in Figure 5. The looping is constructed such that if all three variables are set such that they negate the clause, then the paths will cross each other, and thus not all of the paths cannot be completed. If at least one variable does not evaluate to false in the clause, then all of the paths can complete. >From now on, only schematic drawings will be shown since it is clear that an arrangement of vertices could be placed such that the only valid knight-move paths correspond to the paths shown in the schematic. Note that in this textual representation, a '+' or an 'X' represents a mutually exclusive crossing. --- --- / \ / \ | -+------ ------+- | | | | \ / | | | | -+---- \ / ----+- | | | \ X / | | | | \ / \ / | | | | | | | | . . . . . . . . . . . . ************************ FIGURE 5 ************************ Crossing gadget: In the schematics above, when two paths cross it is assumed that one path must be taken or the other, but not both. However, in order for all of the vertices to connect to all of the clauses in the appropriate places, it will be neccessary for many of the paths between vertices and clauses to pass through one another, allowing both paths to go through. To facilitate this, we use a crossing gadget, which takes the true/false pairs on the left and passes them to the right, and takes the true/false pairs from the bottom and passes them to the top, as in Figure 6. The actual details of the crossing gadget are shown later. | T | | F | --- --- T T --- --- --- --- F F --- --- | T | | F | ************************ FIGURE 6 ************************ Proof: We must now show that this is an actual reduction of 3-SAT into an uncrossed knight path problem. Let $P$ be a particular 3-SAT problem, and let $K$ be the corresponding uncrossed knight path problem, constructed according to the description above. We will now argue that a solution to $K$ corresponds exactly to a solution of $P$, and the converse. First, assume that there is a solution to $K$, i.e. there exists an uncrossed knight path from $s$ to $t$. Because of the construction, the path must go through each of the vertices, and at each one it must take either the true or false branch. Since the path safely passes through all of the clauses without crossing over itself, then clearly this assignment of truth values to the variables must not break any of the clauses - and so therefore this is a solution to $P$. Now assume that there is no solution to $K$. This must also imply that there is no solution to $P$ as well, for the following reason. Assume that there is a solution to $P$. Follow the path in $K$ which corresponds to the assignment of truth values in $P$, and because the clauses were satisfied in $P$, none of the paths will cross in the clause gadgets in $K$, and therefore there is a solution to $K$, which is a contradiction. Therefore we have shown that this is indeed a reduction from 3-SAT to uncrossed knight paths. We also must show that this reduction can be done in polynomial time, and this is not hard to argue. Let there be $v$ variables and $c$ clauses. The clause gadgets are all a constant size because they only contain three variables. The length of the variable gadgets are proportional to the number of clauses they appear in, so the height of each variable gadget is bounded by $k \mdot c$ for some constant $k$. Finally, the crossing gadgets are all some constant size. Thus, the size of the grid is polynomial in the number of clauses and variables, and because the algorithm for generating the grid from the 3-SAT problem is straightforward and deterministic, the reduction can be performed in polynomial time. ---------------------------------------------------------- Details of the crossing gadget: This is the most difficult part of the proof, and the only way to verify that this schematic actually works is to examine all of the possible cases. * Out * True False | | | | | | | | ----/ \--+--+---------+--+--+--+---- | | | | | | ----------+--+---------+--+--+--+---- True | | | | | | True ----------+--+---------+\ | | \---- | | | || | ----\ / + +---------+/ | | /---- | | | | | | | | | | | | /------+--+--/ | * In * | | | | | | | | * Out * | | | | | /---+--+--\ | | | | | | | | | | | ----+--+--+--+--+--+-\ | \--+--+---- | | | | \--/ | | | | ----+--+--+--+--\ /-/ | /--+--+---- False | | | | | | | | | | False ----+--+--/ \--+--+---+--+--+--+---- | | | | | | | | ----+--+--------+--+---+--+--+--+---- | | | | | | | | | /+-\ /-+\ | | | | | \-+/ | | \+-/ | | | | | | | | | | | | \ \ / / | | | | \ \/ / | | | | \ / | | | | \ / | | | | True False * Out * Note that there are two pairs of strands coming into, and out of, every label, except for the lower "True" label. For each of the ones with two pairs, the following gadget is needed to split a single pair into two pairs: In | | / \/ \ / /\ \ \ \/ / \ /\ / X X / \/ \ | X \ | | | | Out1 Out2 This gadget splits the path into two paths, only one of which may be taken.