• Arts
• Business
• Computers
• Games
• Health
• Home
• Kids and Teens
• News
• Recreation
• Reference
• Regional
• Science
• Shopping
• Society
• Sports

Uncrossed Knight Paths is NP-complete

Message-Id: Subject: Twixt_Proof_Draft To: [email protected] 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

Contact Information