Abstract
We define the well-known puzzle of Battleships as a decision problem and prove it to be NP-complete, by means of a parsimonious reduction. By applying Valiant and Vazirani’s (1986) result we immediately obtain that the variant of this problem, viz. promising that there is a unique solution, is NP-complete as well, under randomized reductions. As this finding is in sheer contrast with the general experience of Battleship puzzles being well playable (i.e., effectively solvable), we arrive at a hypothetical explanation for this state of affairs.