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

Since you have 10 ships at max and your data structure is a byte array, why not just represent the water fields using value 0 and the ship fields using the values 1 to 10.

Then you could iterate over the fields and check the surrounding ones (you can optimize based on the iteration direction, in order not to check the same combination twice).

If you encounter a 0 value, continue.

If you get a value > 0 then check whether the surrounding fields contain values other than 0 and the field's value (detect touching ships).

Additionally if the surrounding fields contain the same value but touch at the corners you've found an illegal setup. L-shaped ships should also violate the non-diagonal rule.

The last thing to check is whether the ship could contain holes. In that case just store a range of the fields you found per ship and check whether the newly checked field is next to that range. That would give you the number of ships as well, since you can query the length of each ship's range at the end.

Consider the following partial board:

    A B C D E F G H I J 
  _____________________
1 | 0 0 2 0 0 0 0 0 0 0
2 | 0 1 0 0 3 3 0 4 0 4
3 | 0 0 0 0 0 3 0 0 0 0

If you now check all surrounding fields of B2 (which has value 1), you find value 2, which is an error.

If you check E2, you'll find field F3 being diagonal although having the same value of 3 -> error

If you check H2, you get range H2-H2 (length 1), since H2 is surrounded by empty fields. If you later check J2 you'll see that the difference between H and J is 2 (1 would be ok), so you found a duplicate ship (or one with a hole) -> error

Basically, those rules could be stated as follows (applying to non-empty cells, those with ships):

• each cell's diagonal neighbors must be empty (value 0)
• each cell's straight neighbors must have either the value 0 or the same value as the cell
• if the value of the cell is on a list already, it must have at least one straight neighbor having the same value

Those 3 rules should find any positional violations, if you keep the range of each ship in the list mentioned for rule 3, you can also validate the ship numbers constraint.

Answer 3

Pseudocode:

initialise the ship map with pairs of (size, amount of ships) values

initialise your map[12][12]:
  for every place at row and column coordinate of 0 or 11 (the border)
    mark it as visited
  for every other place
     mark it as not visited
     fill it with either ship or ocean tile from your input

for each row from 1 to 10
  for each column from 1 to 10
    if that place has not been visited yet
      mark that place as visited
      if that place is a ship tile
        check the places to the "right" (bigger column numbers)
          ... and bottom (bigger "row" numbers)
          until you hit a visited or ocean tile
        the amount of ship tiles checked (including the first) is current ship's length
        decrease the amount of ships of that length in the ship map by one
        mark all ship tiles of the current ship as visited
        mark all tiles surrounding those ship tiles as visited

if the ship map includes any pairs with non-zero (including negative) amount of ships
  the map is invalid
else
  the map is valid

Answer 4

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.

Answer 5

I think a better data structure for representing the board position would simplify the project considerably. You define a Ship type, which contains three fields: the length of the ship, the orientation of the ship, and (depending on orientation) its upmost or leftmost square. You store all the ships you want in a list (it will have 10 entries). You validate your position by moving down the list, marking all the squares of the ship as occupied, and all the adjacent squares as forbidden. If, when you place a ship, you have to place the ship in a square that's occupied or forbidden, you know you have an invalid position. On the other hand, if you are able to place all the ships without conflicts, you know the board position is correct by construction.

This has the added advantage of allowing you to place one ship at a time, and report an invalid configuration immediately, meaning it requires virtually no change to work with the user interface for a player to place their ships.

Answer 6

I don't understand indeep what do you need: But I think a ship in Battleship game should have basic struct:

Ship{
    //x, y: top, left of ship's position
    int: x;
    int: y;
    int: size;//[1,2,3,4]
    boolean: isHorizontal;//It means a ship is vertical or horizontal on the map.
}

All your ships, if you declare in array, for example: Ship[SHIP_NUMBER]: arrShip

There are some ways to check the ships are overlapped

I can show you one of them:

1. If you consider each ship is a rectangle you can check if there is exist two ships are intersect.
2. If you consider each ship is set on the map, it will hold the position of the map, for instance: 2-deck ship-horizontal: shipmap[0][0] = 1, map[0][1] = 1. So you can not set the ship on the cells are hold.

And to check a ship is out of map

1. You can check if ship.x < 0 || ship.y < 0 || ship.x > 9 || ship.y > 9