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.