This paper http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf says that the decision problem, "Given a particular puzzle, is there a solution?" is NP-Complete. I don't understand why this can't be done in polynomial time. Given constraints that no two ships can be orthogonally or diagonally adjacent, why not just create a grid where there are 2 times as many columns as "bins" with enough rows to put a "separator" run in between every ship. I've seen the reduction demonstrated this way and it seems like it could be done in polynomial time.

  • $\begingroup$ Please explain what the "battleship puzzle" is and what it's relation to "bins" and "separators" is. People shouldn't have to follow a link to find out what you're even asking about. Also, please clarify how this question is different from all the other battleships questions that have been posted in the past couple of days. $\endgroup$ – David Richerby May 2 '16 at 21:18
  • $\begingroup$ Also, it seems that you're misunderstanding NP-completeness. You seem to be arguing that the reduction can be performed in polynomial time: if so, that's a requirement, not a problem. If that is what you're asking about, I suggest you check out our reference question on NP-completeness and related topics. $\endgroup$ – David Richerby May 2 '16 at 21:21
  • 2
    $\begingroup$ It seems to me that the grid size is a part of the input. You cannot choose any grid you want. $\endgroup$ – Andreas T May 2 '16 at 21:21

As Andreas T mentions, what you're missing is that the grid is part of the instance.
The instance specifies both the grid and the ships.

Why can't the Battleship puzzle be solved in polynomial time? This is the one million dollar question (literally). But since the paper you mention proves that Battleship is NP-complete, the widely believed conjecture P≠NP implies that Battleship cannot be solved in polynomial time.

The paper goes on to prove that Battleship cannot be solved in polynomial time even when the solution is unique, unless NP=RP, which is also considered unlikely. This is a more realistic version of the problem, since in practice Battleship problems have a unique solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.