如何为动态规划实现的战舰布局算法应用分块异步优化？

我有一个个人项目，核心需求是为给定棋盘生成随机战舰布局。这个任务看似简单，但实际实现难度不小，目前采用递归回溯方式实现，计算耗时很长，尤其是无解场景下表现尤为明显。我已尝试添加记忆化、预排序船只数组、优化循环等手段，但性能提升有限，当前方案仍会阻塞Node.js主线程。

现有实现代码 #

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 ? [true, false] : [false, true]
    for (const isHorizontal of orientations) {
        const maxCol = isHorizontal ? grid.cols - shipType.getSize() : grid.cols
        const maxRow = isHorizontal ? 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), isHorizontal, shipType)

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

    return null
}

性能测试结果 #

$ wrk -t 10 -c50 -d10s --timeout 1m http://localhost:3000/shuffle/PdgFRR
Running 10s test @ http://localhost:3000/shuffle/PdgFRR
  10 threads and 50 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency     3.65s     1.54s    5.74s    70.41%
    Req/Sec     2.06      2.18    10.00     92.63%
  98 requests in 10.09s, 51.22KB read
Requests/sec:      9.71
Transfer/sec:      5.08KB

在复杂船只组合场景下，每秒仅能处理约10个请求，且完全阻塞Node.js主线程。

诉求与疑问 #

• 希望采用分块方案，将计算任务拆分为小任务块，通过setTimeout或setImmediate执行以避免阻塞主线程，但不知道如何拆分当前的递归回溯循环，恳请指点实现思路。
• 疑惑为何这类看似简单的战舰布局生成需要大量计算，毕竟许多复杂游戏（如国际象棋）每一步都能计算数千种走法，却能实时响应。

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