Uncrossing Knight Tours: An NP question

Knight graph K(n) = (V,E) with
  V : n*n grid
  E : two points are connected, iff there is knight's move between them.

uncrossed connectivity problem:
  Given a subgraph H of K(n) and two vertices s and t of H.
  Question: is there a uncrossed path in H connecting s and t.

Show that the above problem is NP-complete.

This problem appeares in the game Twixt (The now official tournament
rules.) to decide if one player has won.

Torsten Sillke
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
A related non-crossing problem:

non-crossing maximum-weight matching problem:
  Given 2n points in general position in the plane, find a non-crossing
  maximum-weight matching. (weight = distance)
  No polynomial time algorithm is known up to now.

Ref: 
- Alon, Rajagopalan, Suri;
  Long non-crossing configurations in the plane,
  Proc. 9th Annual ACM Sympos. Comput. Geometry, (1993), 257-263
----------------------------------------------------------------------------
It follows a short description of Twixt of N. Bowers and J. Welton posted in
rec.games.abstract.
----------------------------------------------------------------------------

Twixt is a game that was released as a board game by Avalon Hill in the 60s.
You start with a board of some reasonably large size, the larger the board,
the longer the game, that is a square grid of holes, try 20 x 20 for a good
game.
Below is a diagram of a 10 x 10 board.  The two players are RED and BLACK.


    		         B L A C K
    
           +   +   +   +   +   +   +   +   +   +
              -------------------------------
           + | +   +   +   +   +   +   +   + | +
             |                               |
           R | +   +   +   +   +   +   +   + | +
             |                               |
           + | +   R   +   +   +   R   +   + | +
             |                               |
           + | +   +   +   R   +   +   +   + | +
   R E D     |                               |     R E D
           + | +   +   +   +   +   +   R   + | +
             |                               |
           + | +   +   +   +   +   +   +   + | R
             |                               |
           + | +   +   +   +   +   +   +   + | +
             |                               |
           + | +   +   +   +   +   +   +   + | +
              -------------------------------
           +   +   +   +   +   +   +   +   +   +

		         B L A C K


Each player must create a boundary that connects the opposing sides of the
board of his color.

Play alternates.  There are two types of pieces, pegs and connectors.  On
your move, you place one peg (holes are marked '+').  Then, as a second part
of your move, you may place connectors between any of your pieces that are
a knight's move (from chess) away from each other.  Thus, the selection of
R's above would all be connected in a position indicating a win for red.
--
Neil Bowers
--
From: jonboy@nadia.stgt.sub.org (Jonathan Welton)
Subject: Twixt - rule correction
Date: Sun, 15 Nov 1992 22:08:14 GMT

The descriptions of Twixt posted so far have all been incomplete.
A move consists of 3 parts -
 1. Place a peg in any free hole,
 2. Remove any of your own bridges,
 3. Place bridges between any two of your own pegs which are a knights
    move apart.
In parts 2 and 3 you may remove (add) any number of bridges.

Part 2 is the rule that is most often forgotten. Even in the rule books
accompanying some productions of the game it was incorrectly ommitted.
It is an important rule, since it often resolves otherwise drawn
positions. A good example is the mini situation already posted

>       . . O .    If X is connecting right to      . . O .
>       X ./. .    left, he can play at x,          X ./. .
>       .\O X .    remove his leftmost bridge,      . O X .
>       . X O\.    and make a winning connection.   x X O\.
>       . ./. X                                     . ./. X
>       . O . .                                     . O . .

In fact, with the help of this bridge removal rule, drawn games are
extremely rare in Twixt.

Twixt was invented by Alex Randolph, a prolific inventor of games
(see Sid Sackson's "Gamut of Games"), who introduced it to a group
of artist freinds who used to frequent a Vienese cafe. It has been
produced by several manufacturers, all of whom are required to credit
the inventor (what a good practice).

Twixt is, quite rightly, very highly regarded, and is rated as one of
the best modern board games around.

If you think that the concept of non-intersecting knight moves is simple,
try programming Twixt. Or try to find a non-intersecting knight tour
of 17 moves on a 6x6 board (with no square visited twice). The unique
solution can be found in Martin Gardner's "Mathematical Circus".

Alternatively, try the following little game. The first player marks a
square on an 8x8 board. The second player draws a line from this square
to one a knights move away. The first player then draws a line from this
square to another a knights move away and so on, each player extending a
knights tour, which must be non-intersecting, and no square may be
visited more than once. The last player able to move is the winner.
This is an entertaining little game, and one capable of being played
with a high degree of skill. I would be interested to hear of anyone
who manages to program this one.

-- 
   Jonathan Welton             
--

Longest nocrossed knight tours:
- D. E. Knuth
  http://www-cs-faculty.stanford.edu/~knuth/papers/lg.tex.gz