Avoiding dead-ends in Battleships random placement algorithm

Question

I need some advice about building an algorithm for placing a number of ships on a board according to the rules that ships cannot overlap or touch (even diagonally). In what way could I ensure I still have enough space for the rest of the ships, after picking up a random position?

For example, I want to fit 5 ships on 6x6 board (a 2D array). The ships' sizes are : 5, 4, 3, 1, 1. There are several ways to arrange them, one such is shown below:

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

Random algorithm would look like this:

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) 

But if I use it, I may very well end like this (EDIT: changed to reflect sorting ships by size in step 0):

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

meaning no place for the 1 cell-sized ship. How could I avoid such problem? How would I implement a function verifyRestShipsWillFit() to place in 3b?

Answer 1

Sort the ships using some heuristic, e.g. largest first. Then start make the placement recursive by starting with an empty board and a full list of ships. It is essentially a tree search:

Remember that it is always easier to use recursion if you have immutable classes. Placing a ship on a board creates a new board, without changing the board.

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;
}

Answer 2

For tiny problems like this it's easiest to do

1. Get next ship
2. Get random cell and orientation
3. Try to fit ship (find any conflicts)
    3a. If ship doesn't fit there, **delete all ships and start over**
    3b. If ship fits, get another ship (goto 1) 

If you're paranoid about termination, set a (high) iteration limit and fall back to a deterministic configuration.