战舰游戏中舰船布局可行性校验的高效方案探讨

我有一个小型个人练手项目battleships，是一款简单的战舰游戏，其中一个核心工程挑战是判断玩家自定义的舰船组合是否能合理放置在棋盘上。

问题规则 #

给定R×C的棋盘（R,C>0），舰船需满足以下放置规则：

• 舰船为一维直线型，size属性≥2，代表占据的单元格数
• 舰船必须完全置于棋盘内
• 舰船之间至少间隔一个单元格

当前校验方案 #

我目前通过两步校验判断合理性：

1. 基础校验
   • 检查最大舰船尺寸不超过棋盘的最大边长
   • 检查所有舰船总单元格数 + 舰船间至少各留1个间隔的总单元格数（对应1×N棋盘、舰船同向且仅留1格间隔的极端紧凑情况）不超过棋盘总单元格数
2. 布局校验
   • 尝试在棋盘内实际放置所有舰船，这部分是难点，我采用了递归回溯的方式实现，核心逻辑在placeShips方法中：

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
}

这个方法会返回随机布局组合（因此加入了randomColOffset和randomRowOffset变量）。为了避免无限遍历，我设置了循环次数阈值：若在col × row × 50次循环内未找到可行布局，则判定不存在可行组合。我也曾尝试记忆化优化，但效果不佳。

求助方向 #

请问是否存在更高效的方法，能快速判断给定舰船组合是否可以按照规则放置在棋盘上？

内容的提问来源于stack exchange，提问作者GHopper