How to check the battlefield?

Question

I am trying to check the battleship field with these rules:

• Ships do not touch sides or corners;
• Ships are straight
• There are 1 × 4-deck ships, 2 × 3-deck, 3 × 2-deck, 4 × 1-deck ships.

The field is represented as an array of byte[10][10] . What algorithm can I use for this? The language I use is Java, but any language is good.

Answer 1

Quick validation: 1 × 4-deck vessel, 2 × 3-deck, 3 × 2-deck, 4 × 1-deck vessels should occupy exactly 1 * 4 + 2 * 3 + 3 * 2 + 4 * 1 = 20 cells. Therefore, if your field does not contain 20 cells, it is invalid (both ships overlap, or there are not enough ships)

Now you need to make sure that you have exactly the exact number of ships of each type and the ships are not touching. You can do this through component analysis of components . A simple two-pass algorithm will be used here (there is pseudocode 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 verify that it is either a vertical or horizontal line. It's simple - just count the blob width (the difference between the maximum and minimum values ​​of the column) and the height (the difference between the maximum and minimum values ​​of the rows). One of them should be equal to 1. If not, then two ships touched, and the field is invalid.

Lastly, make sure you have the right amount of each type of ship. If you do not, the field is invalid. If you do, the field will be valid and everything will be ready.

EDIT

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

EDIT 2

Corrected to use the correct vessel specifications.

Answer 2

A simple algorithm. The main idea: each "full" field should be tied to a certain ship.

• for each possible design, the shape of the structure is a small matrix that holds its pattern and takes into account its width and height. Each vessel should be bounded by an edge of width 1 of empty fields to ensure no contiguity.
• for each possible shape of the ship, go through the battlefield and check the basic template - check if there is a ship.
• if the pattern matches, i.e. ship, and then just mark all the squares below them as belonging to that ship. An empty field of width 1 of the field ensures that no other ships / battlefield will touch this ship.
• repeat steps 2 and 3 for all possible ship models
• go through the battlefield and check if each square is marked as belonging to some ship. If yes, then the field is correct. If not, the battlefield is incorrect.

Answer 3

I don’t understand what you need: But I think that the ship in the game “Battleship” should have the basic structure:

 Ship{ //x, y: top, left of ship 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 an array, for example: Ship[SHIP_NUMBER]: arrShip

There are several ways to verify that ships are overlapping.

I can show you one of them:

• If you think each ship is a rectangle, you can check if there are two ships intersecting.
• If you believe that each vessel is installed on the map, it will hold the position of the map, for example: 2-deck ship-horizontal : shipmap[0][0] = 1 , map[0][1] = 1 . Thus, you cannot establish that the vessel is being held in cells.

And check that the ship is missing on the map

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

Answer 4

pseudo code:

 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 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 5

I think that the best data structure for representing the position on the board will greatly simplify the project. You determine the type of Ship , which contains three fields: the length of the vessel, the orientation of the vessel and (depending on the orientation) its top or left square. You store all the ships you need in the list (he will have 10 entries). You check your position by moving through the list, marking all the squares of the ship as occupied, and all adjacent squares as forbidden. If, when placing a ship, you must place the ship in an area that is occupied or prohibited, you know that you have an invalid position. On the other hand, if you can place all the ships without conflict, you know that the position of the board is correct in design.

This gives an additional advantage, allowing you to simultaneously place one ship and immediately report an incorrect configuration, that is, it is practically not necessary to work with the user interface for the player to place your ships.

Answer 6

Since you have 10 max max and your data structure is a byte array, why not just imagine water fields using a value of 0 and ship fields using values ​​from 1 to 10.

Then you can iterate over the fields and check the surrounding (you can optimize based on iteration, so as not to check the same combination twice).

If you encounter a value of 0, continue.

If you get a value> 0, then check if the surrounding fields contain values ​​other than 0 and the field value (detection of moving ships).

In addition, if the surrounding fields contain the same value, but touch the corners, you have detected an illegal setting. L-shaped ships must also violate the off-diagonal rule.

The last thing to check is whether the ship can contain holes. In this case, just save the range of fields found on each ship, and check if the new field is near this range. This will also give you the number of ships, since you can request the length of each range of ships at the end.

Consider the following partial board:

  ABCDEFGHIJ _____________________ 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 the surrounding B2 fields (which has a value of 1), you will find a value of 2, which is an error.

If you check E2, you will find the field F3 diagonal, although with the same value 3 → error

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

In principle, these rules can be formulated as follows (as applied to non-empty cells, with ships):

• each cell diagonal of the cell must be empty (value 0)
• each cell of a cell must either have a value of 0 or the same value as the cell
• If the cell value is already indicated in the list, it must have at least one direct neighbor having the same value

These 3 rules should find any positional irregularities, if you keep the range of each vessel in the list specified for rule 3, you can also check the limit on the number of ships.