I still haven't been able to solve this one. But, I am making a little progress with the IP version.....

So we can let or where 0 denotes a water square and 1 denoting a battleship of some kind for all where .

is our decision variable.

Let A[n] be the number of ship parts in row n.

Let B[n] be the number of ship parts in column n.

Subject to constraints:

(1) (see picture)

(2) (see picture)

(3) i.e. for each row, the sum of all values in each row must equal the number of ship parts in row i.

(4) i.e. Same as above but for columns.

Now I can solve this model, but I still need to model two more things:

(a) I need to somehow include the ship types and ensure the right number of ship types are included in the solution and;

(b) Ensure that no battleship touches any other battleship, even diagonally.

Can anyone please help me add these into the model?