How to validate Battleship field?

Question

I am trying to validate battleship field with these rules:

• Ships don't touch with sides or corners;
• Ships are straight;
• There are 1×4-deck ship, 2×3-deck, 3×2-deck, 4×1-deck ships.

The field is represented as byte[10][10] array. What algorithm could I use to accomplish this? The language I use is Java, but any language is good.

Answer 1

A quick check for validity: 1×4-deck ship, 2×3-deck, 3×2-deck, 4×1-deck ships must occupy exactly 1*4 + 2*3 + 3*2 + 4*1 = 20 cells. So if your field does not contain 20 cells, it is invalid (either ships overlap, or there aren't enough ships)

Now, you need to verify that you have exactly the correct number of each type of ship, and that ships do not touch. You can do this through connected component analysis. The simple two-pass algorithm will do here (there's pseudo-code and examples for you in the link). This will give you the size, location and shape of each "blob" in your field.

From there, you just need to iterate over each blob and check that it's either a vertical or horizontal line. That's simple -- just count the blob's width (difference between maximum and minimum column values) and height (difference between maximum and minimum row values). One of these must be equal to 1. If not, then two ships were touching, and the field is invalid.

Finally, check that you have the correct number of each ship type. If you don't, then the field is invalid. If you do, the field is valid, and you're done.

EDIT

Ships can also touch end-to-end, but this will reduce the overall number of ships (increase the number of ships of a certain type) and thus fail the last test.

EDIT 2

Corrected to use the correct ship specifications.

Answer 2

Simple algorithm. Main idea: every "full" field must be assigned to some ship.

1. for every possible ship shape construct small matrix which holds its pattern and note its width and height. Every ship should be bordered with margin of width 1 of empty fields to ensure no adjacency.
2. for every possible ship shape, go through the battlefield and check the underlying pattern - check if the ship is there.
3. if the pattern matches, i.e. the ship is there, then just mark all underlying squares as belonging to this ship. Empty margin of width of 1 field ensures that no other ships / battlefield margin touches this ship.
4. repeat steps 2 and 3 for all possible ship patterns
5. go through the battlefield and check whether each square is marked as belonging to some ship. If yes, then the field is correct. If no, then the battlefield is not correct.