Is it NP-hard to play international draughts correctly? Is the following problem NP-hard?


  Given a board configuration for $n\times n$ international draughts, find a single legal move.


The corresponding problem for $n\times n$ American checkers (aka English draughts) is trivially solvable in polynomial time.  There are three major differences between these two games.

The first and most significant difference is the “flying king” rule.  In checkers, a king may jump over an adjacent opponent's piece into an empty square two steps away in any diagonal direction.  In international draughts, a king may jump over an opponent's piece an arbitrary distance away by moving an arbitrary distance along a diagonal.

As in checkers, the same piece can be used to capture a series of pieces in a single turn.  However, unlike checkers, captured pieces in international draughts are not removed until the entire sequence is over.  The capturing piece may jump over or land in the same empty square multiple times, but it may not jump over an opponent's piece more than once.

Finally, both checkers and international draughts have a forced capture rule: If you can capture an opponent's piece, you must.  However, the rules rules disagree when there are several options for multiple.  In checkers, you may choose any maximal sequence of captures; in other words, you can choose any capture sequence that ends when the capturing piece cannot capture any more.  In international draughts, you must choose the longest sequence of captures.  Thus, my problem is equivalent to the following:


  Given a board configuration for $n\times n$ international draughts, find a move that captures the maximum number of opposing pieces.


It would suffice to prove that the following problem is NP-complete.  (It's obviously in NP.)


  Given a board configuration for $n\times n$ international draughts involving only kings, can (and therefore must) one player capture all her opponent's pieces in a single turn?


The corresponding checkers problem can be answered in polynomial time; this is an entertaining homework exercise.  The problem looks more similar to Demaine, Demaine, and Eppstein's analysis of Phutball endgames; a solution to the entertaining homework exercise appears at the end of their paper.  A solution also appears in the FOCS 1978 paper by Frankel et al. that proves that playing checkers optimally is PSPACE-hard; see also Robson's 1984 proof that checkers is actually EXPTIME-complete.
OK, here's the reduction. Turns out you don't need planarity after all. Also, for "find a legal move", I take the decision question as "is move X legal?".

First, let's work instead with a game where pieces move orthogonally instead of diagonally. This game is equivalent (just look at the draughts board rotated 45 degrees) except for edge properties, which we will not use. We use two gadgets: merge / split and crossover. See http://www.hearn.to/draughts.pdf. We assume there is a single White king on the board to move. (No other piece will be able to capture any significant number of pieces.) It will move through the indicated corridors, capturing black pieces along the way.

First, merge: if the king enters on any of the N paths A (via capturing a black piece, not shown), it can exit at B. Likewise, if we reverse the gadget and it enters at B, capturing the shown piece, it can exit along any path A (again, capturing an external black piece). This is a single-use gadget (because the exit black piece can be captured only once).

Second, crossover. If the king enters via A (C), it can exit at B (D). It can't stop in the middle and change routes, because that would be a non-capturing move segment.

Now, given a directed graph, construct a corresponding game configuration as follows. For each vertex, construct a merge which feeds into a split. Route the split outputs to the merge inputs of the vertex gadgets (merge + split) corresponding to the vertices the exiting edges connect to, using crossovers as necessary. Start the king on an extra input to any vertex (with a black piece to capture to let it enter the vertex).

Finally, equalize all of the "edge lengths" by adding extra black pieces along the output / input pathways as needed. If there are V vertices, and k black pieces along each edge, then the king can capture 2V + kV + 1 pieces if and only if there  is a Hamiltonian circuit of the corresponding graph. If the king has an alternative move available, capturing a simple chain of 2V + kV pieces, then determining whether that alternative move is legal is NP-complete.