Avoiding dead-ends in Battleships random placement algorithm -

i need advice building algorithm placing number of ships on board according rules ships cannot overlap or touch (even diagonally). in way ensure still have enough space rest of ships, after picking random position?

for example, want fit 5 ships on 6x6 board (a 2d array). ships' sizes : 5, 4, 3, 1, 1. there several ways arrange them, 1 such shown below:

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

random algorithm this:

1. next ship 2. random cell , orientation 3. try fit ship (find conflicts)     3a. if ship cannot fit, try different          cell , orientation, untill cells          have been tried (function fails)     3b. if ship fits, ship (goto 1)  

but if use it, may end (edit: changed reflect sorting ships size in step 0):

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

meaning no place 1 cell-sized ship. how avoid such problem? how implement function verifyrestshipswillfit() place in 3b?

sort ships using heuristic, e.g. largest first. start make placement recursive starting empty board , full list of ships. tree search:

remember easier use recursion if have immutable classes. placing ship on board creates new board, without changing board.

board getrandomboard() {    list<ship> ships = { .. }   // list of ships.    board = board.empty();    board result = placeships(ships, board);    return result; // have retry here if fails. }  private board placeships(ienumerable<ship> shipsremaining, board board) {        ship shiptoplace = shipsremaining.firstordefault();     // if ships placed, done.    if (shiptoplace == null)       return board;     int attempts = 0;           while (attempts++ < maxattempts)    {        // position new ship ok current board.        shipposition pos = getrandomshipposition(board, shiptoplace);          // if isn't possible find such position, branch bad.        if (pos == null)           return null;         // create new board, including new ship.        board newboard = new board.withship(shiptoplace, pos);         // recurse placing remaining ships on new board.        board nextboard = placeships(shipsremaining.skip(1).tolist(), newboard);        if (nextboard != null)           return nextboard;    }    return null; }