algorithm - 避免战舰随机放置算法中的死胡同

Question

我需要一些建议来构建一种算法，根据船舶不能重叠或接触(甚至是对角线)的规则在板上放置多艘船。在选择一个随机位置后，我如何确保我仍有足够的空间容纳其余的飞船？

例如，我想在 6x6 板(二维阵列)上放置 5 艘船。船的尺寸为:5、4、3、1、1。有几种排列方式，如下所示:

 -------------
| 1 1 1 1 1 . |
| . . . . . . |
| 2 2 2 2 . 4 |
| . . . . . . |
| 3 3 3 . . 5 |
| . . . . . . |
 -------------

随机算法看起来像这样:

1. Get next ship
2. Get random cell and orientation
3. Try to fit ship (find any conflicts)
    3a. If ship cannot fit, try different 
        cell and orientation, untill all cells 
        have been tried (function fails)
    3b. If ship fits, get another ship (goto 1) 

但如果我使用它，我很可能会像这样结束(编辑:更改以反射(reflect)在步骤 0 中按大小对船舶进行排序):

 -------------
| . 3 3 3 . 4 |   5
| . . . . . . |
| . 2 2 2 2 . |
| . . . . . . |
| 1 1 1 1 1 . |
| . . . . . . |
 ------------- 

这意味着 1 格大小的飞船没有位置。我怎样才能避免这样的问题？我将如何实现函数 verifyRestShipsWillFit() 以放置在 3b 中？

Answer 1

使用一些启发式方法对船只进行排序，例如最大的第一。然后通过从一个空板和完整的船舶列表开始，开始递归放置。它本质上是一个树搜索:

请记住，如果您有不可变类，使用递归总是更容易。将一艘船放在板上会创建一个新板，而无需更改板。

Board GetRandomBoard()
{
   List<Ship> ships = { .. }   // List of all ships.
   Board = Board.Empty();
   Board result = PlaceShips(ships, board);
   return result; // You could have a retry here as well if it fails.
}

private Board PlaceShips(IEnumerable<Ship> shipsRemaining, Board board)
{    
   Ship shipToPlace = shipsRemaining.FirstOrDefault();

   // If all ships were placed, we are done.
   if (shipToPlace == null)
      return board;

   int attempts = 0;       
   while (attempts++ < MaxAttempts)
   {
       // Get a position for the new ship that is OK with the current board.
       ShipPosition pos = GetRandomShipPosition(board, shipToPlace); 

       // If it isn't possible to find such a position, this branch is bad.
       if (pos == null)
          return null;

       // Create a new board, including the new ship.
       Board newBoard = new board.WithShip(shipToplace, pos);

       // Recurse by placing remaining ships on the new board.
       board nextBoard = PlaceShips(shipsRemaining.Skip(1).ToList(), newBoard);
       if (nextBoard != null)
          return nextBoard;
   }
   return null;
}