We show that, in John Conway's board game Phutball (or Philosopher's Football),
it is NP-complete to determine whether the current player has a move that
immediately wins the game. In contrast, the similar problems of determining
whether there is an immediately winning move in checkers, or a move that kings
a man, are both solvable in polynomial time.