###GolfScript, 236 characters###

n%([~](:N):M;[.,,]zip{~[)]*~}%-1%:S;{(65-\~(M*+}%:H;{{M*+}+N,/}N,%H-S[]]]{(~\.{(:L;{{M*+{+}+L,%}+N)L-,/}N,%{.{.M/\M%M*+}%}%{3$&,L=},{:K[{..M+\M-}%{..)\(}%3$\- 1$3$K+]}%\;\;\;\+.}{;:R;;;0}if}do{{{M*+.H?)'!'*\R?)'#'*'.'++1<}+N,/n}N,%}R!!* 

The input is given on STDIN. First line contains size and number of ships, each following line coordinates of a single shot.

Example:

4 1 1 1 A2 A4 B3 C3 C4 D4 ##.# !..# #!!# !.!! 

I thought that also this challenge should have at least one GolfScript answer. In the end it became very ungolfscriptish due to the used algorithm which favours performance over shortness.

Annotated code:

n% # Split the input into lines ([~] # The first line is evaluated to an array [N S1 S2 S3 ...] (:N # This happy smiley removes the first item and assigns it to variable N ):M; # While this sad smiley increases N by one and assigns it to M [.,,]zip # For the rest of numbers in the first line create the array [[0 S1] [1 S2] [2 S3] ...] {~[)]*~}% # Each element [i Si] is converted into the list (i+1 i+1 ... i+1) with Si items. -1%:S; # Reverse (i.e. largest ship first) and assign the list to variable S. # The result is a list of ship lengths, e.g. for input 3 0 2 we have S = [3 3 1 1 1]. { # On the stack remains a list of coordinates (65- # Convert the letter from A,B,... into numeric value 0,1,... \~( # The number value is decreased by one M*+ # Both are combined to a single index (M*row+col) }%:H; # The list of shots is then assigned to variable H # The algorithm is recursive backtracking implemented using a stack of tuples [A S R] where # - A is the list of open squares # - S is a list of ships to be placed # - R is the list of positions where ships were placed {{ # initial A is the full space of possible coordinates M*+ # combine row and column values into a single index }+N,/}N,% # do the N*N loop H- # minus all places where a shot was done already S # initial S is the original list [] # initial R is the empty list (no ships placed yet) ] ] # The starting point is pushed on the stack { # Start of the loop running on the stack (~\ # Pop from the stack and extract items in order A R S .{ # If S is non-empty (:L; # Take first item in S (longest ship) and asign its length to L {{M*+{+}+L,%}+N)L-,/}N,%{.{.M/\M%M*+}%}% # This lengthy expression just calculates all possible ship placements on a single board # (could be shortened by 3 chars if we don't respect board size but I find it clearer this way) {3$&,L=}, # This step is just a filter on those placements. The overlap (&) with the list of open squares (3$) # must be of size L, i.e. all coordinates must be free # Now we have possible placements. For each one generate the appropriate tuple (A* S* R*) for recursion { :K # Assign the possible new ship placement to temporary variable K [ {..M+\M-}% {..)\(}% # For each coordinate add the square one row above and below (first loop) # and afterwards for the resulting list also all squares left and right (second loop) 3$\- # Remove all these squares from the list of available squares A in order to get the new A* 1$ # Reduced list of ships S* (note that the first item of S was already remove above) 3$K+ # Last item in tuple is R* = R + K, i.e. the ship's placements are added to the result ] }% \;\;\; # Discard the original values A R S \+ # Push the newly generated tuples on the stack . # Loop until the stack is empty }{ # else ;:R;;; # Assign the solution to the variable R and remove all the rest from the stack. 0 # Push a zero in order to break the loop }if # End if }do # End of the loop { # The output block starts here {{ M*+ .H?) # Is the current square in the list of shots? '!'* # then take a number of '!' otherwise an empty string \R?) # Is the current square in the list of ships? '#'* # then take a number of '#' otherwise an empty string '.'++ # Join both strings and append a '.' 1< # Take the first item of the resulting string, i.e. altogether this is a simple if-else-structure }+N,/n}N,% # Do a N*N loop } R!!* # Run this block only if R was assigned something during the backtracking. # (!! is double-negation which converts any non-zero R into a one) # Note: since the empty list from the algorithm is still on the stack if R wasn't assigned # anything the operator !! works on the code block (which yields 1) which is then multiplied # with the empty list.