The rules of the game, as they were taught to me, disallowed immediately adjacent ships.

Another problem with placement is that you transpose unconditionally in the loop. E.g. the puzzle will always have size-three ships at right angles.

Thanks. In my haste to get regexing I didn't read the rules very closely.

Easily fixed, though:

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1170733

use strict;
use warnings;

my $sea = ((' ' x 10) . "\n") x 10;

sub transpose
  {
  local $_ = $sea;
  tr/<>^v/^v<>/;
  $sea = '';
  $sea .= "\n" while s/^(.)/ $sea .= $1; '' /gem;
  }

for my $ship ( 4,3,3,2,2,2,1,1,1,1 )
  {
  my @places;
  push @places, $-[0] while $sea =~ /(?= {$ship})/g;
  substr $sea, $places[rand @places], $ship,
    ('O', '<>', '<#>', '<##>' )[$ship - 1];
  for (0, 9, 11, 0, 9, 11)
    {
    $sea =~ s/(?<=[<>^v#O].{$_}) | (?=.{$_}[<>^v#O])/~/gs;
    transpose;
    }
  rand > 0.5 and transpose;
  }
tr/ /~/ for $sea;

print $sea;
my @chars = $sea =~ /./g;

use Tk; # for http://perlmonks.org/?node_id=1170638

my $mw = MainWindow->new( -title => "Battleship" );
for my $y (0..9)
  {
  for my $x (0..9)
    {
    my ($char, $b) = shift @chars;
    $b = $mw->Button( -font => 'courier 24', -text => ' ',
      -command => sub {$b->configure(-text => $char) },
      )->grid(-row => $y, -column => $x);
    }
  }

MainLoop;
[download]

Thanks for the code. The Tk code should be a good starting point for anyone who wants to build a GUI version. It looks like your code creates a solution (with all 10 ships completely placed in the grid), but it does not create a puzzle grid (with only ship segments shown, along with row and column counts of the hidden ships as clues).