# Why is determining if there is a solution to a Battleship puzzle NP-Complete?

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.

• 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. – David Richerby May 2 '16 at 21:18
• 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. – David Richerby May 2 '16 at 21:21
• It seems to me that the grid size is a part of the input. You cannot choose any grid you want. – Andreas T May 2 '16 at 21:21