From: Dominic Mazzoni
MessageId: <199710101731.TAA15971@turan.cs.elte.hu>
Subject: Twixt_Proof_Draft
To: sillke@lhsystems.de
Date: Fri, 10 Oct 1997 19:31:42 +0200 (MET DST)
ContentType: text/plain; charset=USASCII
Uncrossed Knight Paths is NPcomplete
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 NPcomplete by reduction from 3SAT.
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 BreadthFirst 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 singlecolor 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 twocolor 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
twocolor uncrossed path problem, it would immediately imply an algorithm for
the singlecolor variation, though the reverse is not true. Therefore it
will suffice to show that the singlecolor uncrossed path problem is
NPcomplete, and this implies the NPcompleteness of the twocolor problem
as well.
We model the singlecolor 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 NPcomplete, we will
reduce it from 3SAT. In other words, we will show how any instance of
the 3SAT 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.
3Satisfiability (3SAT) 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 NPcomplete (Stephen Cook, 1971).
The reduction from 3SAT 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 3SAT problem, and some clause gadgets will
be placed along the top side of the grid, corresponding to
the clauses in the 3SAT 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 knightmove 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 3SAT into an uncrossed knight path problem. Let $P$
be a particular 3SAT 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 3SAT 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 3SAT 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.