The big line with 'kron' (near the bottom of the un-golfed code) is my favorite part of this. It writes a '1' to all locations in the map that neighbor a given position. Can you see how it works? It uses the kronecker tensor product, matrix multiplication, and indexes the map as linear array...

Matlab - 633 chars

I represented the map with an (n+2)x(n+2) matrix; the extra space around the outside means I don't have to use bound-checking when marking neighbors. A '0' represents free space. A '1' represents a missed shot. A '2' represents part of a ship.

The pl function takes a map (m), a ship size (s), and a flag (t). It returns a cell-array of all possible maps with the desired ship added, and with all neighboring elements to the ship marked as additional missed hits (so further ships won't be placed next to an existing ship). If the t flag is set, each of these maps is transposed before being added to the cell-array; this avoids having redundant code for horizontal and vertical placements.

The pp function takes a map (m) and a vector of ship sizes (ss) and tries to find a map that includes all of the ships. It uses simple recursion.

The bs function takes a map size (n), a list of shots (sh), and a list of ships in the format described in the challenge (st). It expands the list of ships to the format used internally (list of ship sizes). It builds the initial map (stored in the m variable), uses the pp function to solve the challenge, producing a new map q which might be empty if there is no solution) and formats the output.

There's a lot of code reduction that could be done, but I think the algorithm is pretty small. The code would be much smaller, maybe half this, if the input and output format restrictions were looser.

function bs(n,sh,sp) ss=[]; for i=1:length(sp) ss(end+1:end+sp(i))=i; end for h=sh' m(h(2)-'/',h(1)-'?')=1; end m(n+2,n+2)=0; q=pp(m,ss); if isempty(q) ':(' else   m(find(q==2))=2;   num2str(m(2:n+1,2:n+1),'%d') end end function q = pp(m,ss) if sum(ss) s=ss(end); mm=[pl(m,s,0),pl(m',s,1)]; for n=1:length(mm) q=pp(mm{n},ss(1:end-1)); if ~isempty(q) return;end  end q=[];  else q=m; end end function mm=pl(m,s,t) mm={}; for i=2:length(m)-1 b=zeros(1,s); for j=strfind(m(i,2:end-1),b) n=m; z=size(n); [c1{1:2}]=ndgrid(1:3); c2(1:2)={2}; for l=1+j:j+s n(sub2ind(z,i,l)+sub2ind(z,c1{:})-sub2ind(z,c2{:}))=1; end n(i,1+j:j+s)=2; if t n=n';end mm{end+1}=n;   end end end 

function b(n,sh,sp) ss=[]; for i=1:length(sp)ss(end+1:end+sp(i))=i;end for h=sh'm(h(2)-'/',h(1)-'?')=1;end m(n+2,n+2)=0;q=pp(m,ss); if isempty(q) ':(' else m(find(q==2))=2;num2str(m(2:n+1,2:n+1),'%d') end end function q = pp(m,ss) if sum(ss)s=ss(end);mm=[pl(m,s,0),pl(m',s,1)];for n=1:length(mm)q=pp(mm{n},ss(1:end-1));if ~isempty(q) return;end end q=[];else q=m;end end function mm=pl(m,s,t) mm={};for i=2:length(m)-1 b=zeros(1,s);for j=strfind(m(i,2:end-1),b)n=m;z=size(n);[c1{1:2}]=ndgrid(1:3);c2(1:2)={2};for l=1+j:j+s n(sub2ind(z,i,l)+sub2ind(z,c1{:})-sub2ind(z,c2{:}))=1;end n(i,1+j:j+s)=2;if t n=n';end mm{end+1}=n;end end end 

Matlab - 536 chars

Updated: Added commented version, reduced golfed version by ~100 chars

% Battleship puzzle solver. % % n: size of the map (ex. 4 -> 4x4) % sh: list of shots (ex. ['A2';'C4']) % sp: ships of each size (ex. [2,0,1] -> 2x1 and 1x3) % function bs(n,sh,sp)   % sp holds a vector of ship counts, where the index of each element is % the size of the ship. s will hold a vector of ship sizes, with order % not mattering. This is easier to work with using recursion, because % we can remove elements with Matlab's array subselection syntax, rather % than decrement elements and check if they're zero. % % Tricks: % Since sp never contains a -1, find(1+sp) is the same as 1:length(sp) % but is three characters shorter. % s=[]; for i=find(1+sp) s(end+1:end+sp(i))=i; end   % m will hold the map. It will be +2 in each direction, so that later we % can find neighbors of edge-spaces without checking bounds. For now,  % each element is either '0' or '1' for a space or missed shot, % respectively. We convert the shots as provided by the user (ex. 'A2') % to marks on the map. % % Tricks: % It takes one shorter character to subtract 47 than 'A' to determine % the indices into the map. % m=zeros(n+2); for h=sh' m(h(2)-47,h(1)-63)=1; end  % Solve the puzzle. q will either be the empty array or a solution map.  % q=pp(m,s);     % If a solution was found, output it, showing the original shots and the % ship placement. If no solution was found, print a sad face. % % Tricks: % q is 0 on failure, which is treated like 'false'. q is a matrix on % success which is NOT treated like 'true', so we have to check for % failure first, then handle success in the 'else' block. % % q contains the "fake shots" that surround each placed ship (see the % pl function). We don't want to output those, so we just copy the ship % markings into the original map. % if ~q ':(' else m(find(q==2))=2; num2str(m(2:n+1,2:n+1),'%d') end  % Depth-first search for a solution. % % m: map (see main code above) % s: vector of ship sizes to place in the map % % Returns q: square matrix of integers, updated with all requested ship % sizes, or 0 if no solution is possible. % function q = pp(m,s)   % If we have no ships to process, we're all done recursing and the % current map is a valid solution. Rather than handle this in an 'else' % block, we can assume it's the case and overwrite q if not, saving 4 % characters. % q=m; % If we have any ships to place... % % Tricks: % Since we are only interested in positive values in s, we can use % sum(s) in place of isempty(s), saving 4 characters. %  if sum(s)   % Try to place the first ship in the list into the map, both vertically % (first call to p) and vertically (second call to p). We can process % any ship in the list, but the first can be removed from the list % with the fewest characters. r will hold a cell-array of options for % this ship. % r=[p(m,s(1),0),p(m',s(1),1)];    % Recurse for each option until we find a solution. % % Tricks: % Start with q, our return variable, set to 0 (indicating no solution % was found. On each loop we'll only bother to recurse if q is still % 0. This relieves the need for if/else to check whether to continue % the loop, or any final q=0 if the loop exits without success. % % Sadly, there's no way around the length(r) call. Matlab doesn't % provide syntax for iterating over cell-arrays. %  q=0; for i=1:length(r) if ~q q=pp(r{i},s(2:end));end end  end % Place a single ship into a map. % % m: map (see main code above) % s: ship size to place % t: if the map has been transposed prior to this call % % Returns r: cell-array of possible maps including this ship % function r=p(m,s,t) % Start with an empty cell-array and pre-compute the size of the map, % which we'll need to use a few times. % r={}; z=size(m);    % For each row (omitting the first and last 'buffer' rows)... % for i=2:z(2)-1    % For each starting column in this row where enough consecutive 0s % appear to fit this ship... % for j=strfind(m(i,2:end-1),(1:s)*0)   % Copy the map so we can modify it without overwriting the variable % for the next loop. % n=m;    % For each location on the map that is part of this optional   % placement...  for l=0:s-1 % Let's leave this is an exercise for the reader ;) %  v=-1:1; n([(l+j)*z(1)+i,z(1),1]*[ones(1,9);kron(v,[1 1 1]);[v v v]])=1; end    % Mark each location that is part of this optional placement with % a '2'. % n(i,1+j:j+s)=2;     % Since our results are going into a cell-array it won't be % convenient for the caller to undo any transpositions they might % have done. If the t flag is set, transpose this map back before % adding it to the cell-array. %  if t n=n';end r{end+1}=n; end end 

function bs(n,sh,sp) s=[];for i=find(1+sp) s(end+1:end+sp(i))=i;end m=zeros(n+2);for h=sh' m(h(2)-47,h(1)-63)=1;end q=pp(m,s);if ~q ':(' else  m(find(q==2))=2;num2str(m(2:n+1,2:n+1),'%d') end function q = pp(m,s) q=m;if sum(s) r=[p(m,s(1),0),p(m',s(1),1)];q=0;for i=1:length(r)if ~q q=pp(r{i},s(2:end));end end end function r=p(m,s,t) r={};z=size(m);for i=2:z(2)-1 for j=strfind(m(i,2:end-1),(1:s)*0)n=m;for l=0:s-1 v=-1:1;n([(l+j)*z(1)+i,z(1),1]*[ones(1,9);kron(v,[1 1 1]);[v v v]])=1;end n(i,1+j:j+s)=2;if t n=n';end r{end+1}=n;end end 

Matlab - 657 chars

function bs(n,sh,sp) ss=[]; for i=1:length(sp)  ss(end+1:end+sp(i))=i; end for h=sh' m(h(2)-'/',h(1)-'?')=1; end m(n+2,n+2)=0; q=pp(m,ss); if isempty(q) ':(' else  m(find(q==2))=2; num2str(m(2:n+1,2:n+1),'%d') end end function q = pp(m,ss) if sum(ss)  s=ss(end); mm=[pl(m,s,0),pl(m',s,1)]; for n=1:length(mm)  q=pp(mm{n},ss(1:end-1)); if ~isempty(q) return;end end q=[]; else q=m; end end function mm=pl(m,s,t) mm={}; for i=2:length(m)-1 b=zeros(1,s); for j=strfind(m(i,2:end-1),b) n=m; z=size(n); [c1{1:2}]=ndgrid(1:3); c2(1:2)={2}; for l=1+j:j+s n(sub2ind(z,i,l)+sub2ind(z,c1{:})-sub2ind(z,c2{:}))=1; end n(i,1+j:j+s)=2; if t n=n';end mm{end+1}=n; end end end 

Matlab - 633 chars

function b(n,sh,sp) ss=[]; for i=1:length(sp)ss(end+1:end+sp(i))=i;end for h=sh'm(h(2)-'/',h(1)-'?')=1;end m(n+2,n+2)=0;q=pp(m,ss); if isempty(q) ':(' else m(find(q==2))=2;num2str(m(2:n+1,2:n+1),'%d') end end function q = pp(m,ss) if sum(ss)s=ss(end);mm=[pl(m,s,0),pl(m',s,1)];for n=1:length(mm)q=pp(mm{n},ss(1:end-1));if ~isempty(q) return;end end q=[];else q=m;end end function mm=pl(m,s,t) mm={};for i=2:length(m)-1 b=zeros(1,s);for j=strfind(m(i,2:end-1),b)n=m;z=size(n);[c1{1:2}]=ndgrid(1:3);c2(1:2)={2};for l=1+j:j+s n(sub2ind(z,i,l)+sub2ind(z,c1{:})-sub2ind(z,c2{:}))=1;end n(i,1+j:j+s)=2;if t n=n';end mm{end+1}=n;end end end