Solving tiling problem in battleships game

Question

I have a small pet project. It is a simple game but there are some interesting engineering challenges in it. One of them is to find out if the ships combination makes sense.

So, as you can see players may sat various game board dimension and ships combination (custom game type on Create game page). What I want is to notify them if their choose doesn't make sense which means for the given board dimension (Rows x Cols) it is impossible to place selected ships according to following rules:

1. Grid dimension is R x C (R,C > 0)
2. Ships are one-dimensional (straight lines) and have size property (size >= 2), which shows how many cells the ship consists of
3. Ships must be located within the grid; there should be at least one cell between each of them

To answer the question I perform two assessments:

1. Dumb assessment

   • check if the biggest ship size less or equal the biggest board side

   • check if all ships cells count + 1 cell between each ship (the simplest case when grid has 1xN dimension and all ships oriented the same way with only one cell gap between) less or equal to grid cells amount

2. Placement assessment

   • Try to place ships within the grid (the silliest part due to we are trying to place ships in order to find out if it is possible)

For the second assessment I apply dynamic programming approach which is extremely slow especially when there isn't solution (we have to loop through all combinations). It is implemented in placeShips method:

    static placeShips(col: number, row: number, placedShips: Ship[], shipsToPlace: ShipTypeAbstract[]): Ship[]|null {
        Grid.iter++
        if (shipsToPlace.length === 0) {
            return placedShips
        }
        const grid = Grid.initGrid(col, row)
        placedShips.forEach((ship: Ship) => {
            grid.placeShipWithSurrounding(ship)
        })

        const types = [...shipsToPlace]
        const shipType = types.pop()
        const orientations = Math.random() > 0.5
            ? [Ship.SHIP_ORIENTATION_VERTICAL, Ship.SHIP_ORIENTATION_HORIZONTAL]
            : [Ship.SHIP_ORIENTATION_HORIZONTAL, Ship.SHIP_ORIENTATION_VERTICAL]
        for (const orientation of orientations) {
            const maxCol = orientation === Ship.SHIP_ORIENTATION_HORIZONTAL ? grid.cols - shipType.getSize() : grid.cols
            const maxRow = orientation === Ship.SHIP_ORIENTATION_HORIZONTAL ? grid.rows : grid.rows - shipType.getSize()
            const randomRowOffset = Math.floor(Math.random() * maxRow)
            for (var r = 0; r < maxRow; r++) {
                var rr = r + randomRowOffset
                if (rr >= maxRow) {
                    rr -= maxRow
                }
                const randomColOffset = Math.floor(Math.random() * maxCol)
                for (var c = 0; c < maxCol; c++) {
                    if (Grid.iter > row * col * 50) {
                        throw new Error(`In ${Grid.iter} iteration we weren't able to fit all ships`)
                    }

                    var cc = c + randomColOffset
                    if (cc >= maxCol) {
                        cc -= maxCol
                    }
                    const ship = new Ship(new Position(cc, rr), orientation, shipType)

                    if (grid.canPlaceShip(ship) === true) {
                        const pl = [...placedShips]
                        pl.push(ship)
                        const res = Grid.placeShips(col, row, pl, [...types])
                        if (res !== null) {
                            return res
                        }
                    }
                }
            }
        }

        return null
    }

This method returns random combination (this is why there are randomColOffset and randomRowOffset variables). You can see In ${Grid.iter} iteration we weren't able to fit all ships error which was added intentionally in sake of performance - there is probably zero combinations if we can't find a random one in col x row x 50 loops. Also I tried memorization but it didn't help much.

If there more performant way to find out whether the given combination makes sense or not?