How to make the random placing of ships not overlap any ships when placing in battleships

Question

Im making the game battleships on the computer and wonder how i can make the ships not overlap each other when randomly placing them. My code right now looks like this:

public class BattleshipSetup {

    public static class Boat {
        int size;
    }
    public static class AircraftCarrier extends Boat {
        public AircraftCarrier() {
            size = 5;
        }
    }
    public static class Battleship extends Boat {
        public Battleship() {
            size = 4;
        }
    }
    public static class Destroyer extends Boat {
        public Destroyer() {
            size = 3;
        }
    }
    public static class Submarine extends Boat {
        public Submarine() {
            size = 3;
        }
    }
    public static class PatrolShip extends Boat {
        public PatrolShip() {
            size = 2;
        }
    }
    public static class GridSetup {
        int[][] grid = {{0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}};
        public void setGrid() {
            Boat[] ship;
            ship = new Boat[5];
            ship[0] = new AircraftCarrier();
            ship[1] = new Battleship();
            ship[2] = new Destroyer();
            ship[3] = new Submarine();
            ship[4] = new PatrolShip();
            for (int i = 0; i < 5; i++) {
                int way = (int) (Math.random() * 2);
                if (way == 0) {
                    int x = (int) (Math.random() * 7);
                    int y = (int) (Math.random() * (7 - ship[i].size));
                    for (int j = 0; j < ship[i].size; j++) {
                        grid[x][y + j] = i + 1;
                    }
                }
                if (way == 1) {
                    int x = (int) (Math.random() * (7 - ship[i].size));
                    int y = (int) (Math.random() * 7);
                    for (int j = 0; j < ship[i].size; j++) {
                        grid[x + j][y] = i + 1;
                    }
                }
            }
        }
        public int[][] getGrid() {
            return grid;
        }
    }
}`

The thing now is that sometimes when it places ships it puts one ship partially over another one and that is not supossed to be possible.

Answer 1

I would use an algorithm like:

1. For each ship size, store a list of possible locations in the grid.
2. Pick a random location from this list.
3. Go through each list for each ship size, removing (or invalidating) overlaps.

This way, you are less likely to get your self stuck trying to get a valid location as your board gets more crowded.