Lazy battleship placement Imagine the following scenario: you are playing battleships with a friend but decide to cheat. Rather than moving a ship after he shoots where your ship used to be, you decide not to place any ships at all. You tell him all his shots are misses, until it is impossible to place ships in such a way.
You have to write a function, or a full program, that somehow takes 3 arguments: the field size, a list of amounts of ship sizes, and a list of shots.
Battlefield
One of the given parameters is the board size. The battlefield is a square of cells, and the given parameter is simply one side of the square.
For example, the following is a board of size 5.

Coordinates on the field are specified as a 2-component string: a letter followed by a number. You can rely on the letters being in some particular case.
Letter specifies the column, number specifies the row of the cell (1-indexed). For example in the above picture, the highlighted cell is denoted by &quot;D2&quot;.
Since there are only 26 letters, the field can't be larger than 26x26.
Ships
The ships are straight lines of 1 or more blocks. The amount of ships is specified in a list, where the first element is the amount of 1-cell ships, second - of 2-cell ships and so on.
For instance, the list [4,1,2,0,1] would create the following shipset:

When placed on the battlefield, ships cannot intersect, or even touch each other. Not even with corners. They can however touch the edges of the field.
Below you can see an example of valid ship placement:

You can assume that for a given shipset, there always exists a placement on an empty board of given size.
Output
If such placements of ships exist, you have to output any of them.
The program has to output a newline-separated matrix of ascii characters of either of 3 types - one to denote blank cell, one - a ship piece, and one - a cell marked as &quot;missed&quot;. No other characters should be output.
For example,
ZZ@Z
\@@Z
@\\Z
\Z\\

(In this example, I defined @ to be blank cell, \ to be a &quot;missed&quot; cell, and Z to be ship piece)
If no such placement exists, the program/function should return without outputting anything.
Input
If you decide to make a fullblown program, it's up to specify you how the lists are input, some might go via arguments, some via stdin.
This is code-golf, lowest amount of characters wins.
An example non-golfed optimized solution can be found here
Compile with -std=c99, first argument is the size of the board, the other arguments are ship sizes. A newline-separated list of shots is given on stdin. Example:
./a 4 1 1 1 &lt;&lt;&lt; $'A2\nA4\nB3\nC3\nC4\D4'
SWI-Prolog, 536 4411 bytes

1 UNIX line ending, final new line not counted

The version with all optimizations removed (441 bytes):

:-[library(clpfd)].
m(G,L):-maplist(G,L).
l(L,A):-length(A,L).
y(A,E,(X,Y)):-nth1(X,A,R),nth1(Y,R,F),var(F),F=E.
a(A,S):-l(L,A),X#&gt;0,X#=&lt;L,Y#&gt;0,Y#=&lt;L,h(S,(X,Y),A).
h(0,_,_).
h(L,(X,Y),A):-(B=A;transpose(A,T),B=T),y(B,s,(X,Y)),M#=L-1,Z#=Y+1,h(M,(X,Z),B).
e([],_,[]).
e([H|R],I,O):-J#=I+1,e(R,J,P),l(H,Q),Q ins I,append(P,Q,O).
r(R):-m(c,R),nl.
c(E):-var(E)-&gt;put(@);put(E).
g(L,H,S):-l(L,A),m(l(L),A),m(y(A,\),S),e(H,1,G),!,m(a(A),G),!,m(r,A).


Since the code is changed to minimize the number of bytes, it will no longer accept a list of shots that have duplicates.



The version with basic optimization, fully golfed (536 → 506 bytes)

:-[library(clpfd)].
m(G,L):-maplist(G,L).
l(L,A):-length(A,L).
x(A,I,E):-X=..[a|A],arg(I,X,E).
y(A,E,(X,Y)):-x(A,X,R),x(R,Y,E).
a(A,S):-l(L,A),X#&gt;0,X#=&lt;L,Y#&gt;0,Y#=&lt;L,(B=A;transpose(A,T),B=T),h(S,(X,Y),B).
h(0,_,_).
h(L,(X,Y),A):-y(A,E,(X,Y)),var(E),E=s,M#=L-1,Z#=Y+1,h(M,(X,Z),A).
e([],_,[]).
e([H|R],I,O):-J#=I+1,e(R,J,P),l(H,Q),Q ins I,append(P,Q,O).
r(R):-m(c,R),nl.
c(E):-var(E)-&gt;put(@);put(E).
g(L,H,S):-l(L,A),m(l(L),A),sort(S,T),m(y(A,\),T),e(H,1,G),!,l(E,T),sumlist(G,D),L*L-E&gt;=D,m(a(A),G),!,m(r,A).


I implement some basic checks (count number of ship blocks necessary) to make the code exits faster for clearly impossible cases. The code is also immune to duplicate in the list of shots so far.



Below is the (somewhat) readable version, with detailed comments:

:-[library(clpfd)].

% Shorthand for maplist, which works like map in high order function
m(G,L):-maplist(G,L).

% Creating a square matrix A which is L x L
board(L,A):-l(L,A),m(l(L),A).

% Shorthand for length, with order of parameters reversed
l(L,A):-length(A,L).

% Unification A[I] = E
x(A,I,E):-X=..[a|A],arg(I,X,E).

% Unification A[X][Y]=E
idx2(A,E,(X,Y)):-x(A,X,R),x(R,Y,E).

% Mark positions that have been shot
markshot(A,S):-m(idx2(A,\),S).

% Place all ships on the board
placeships(H,A):-m(placeship(A),H).

% Place a length S ship horizontal/vertical forward on the board
placeship(A,S):-
    l(L,A), % Get length
    X#&gt;0,X#=&lt;L,Y#&gt;0,Y#=&lt;L, % Constraint X and Y coordinates
    transpose(A,T), % Transpose to work on columns
    (placeship_h(S,(X,Y),A) ; placeship_h(S,(Y,X),T)).

% Place ship horizontal, forward at (X,Y)
placeship_h(0,_,_).
placeship_h(L,(X,Y),A):-
    idx2(A,E,(X,Y)),var(E),E=s, % Make sure position is unassigned, then mark
    L2#=L-1,Y2#=Y+1, % Do this for all blocks of the ship
    placeship_h(L2,(X,Y2),A).

% Expand the list of ships
% e.g. [2,3,1] --&gt; [3,2,2,2,1,1]
shipexpand(S,O):-shipexpand(S,1,O).

shipexpand([],_,[]).
shipexpand([H|R],I,O):-
    I2#=I+1,shipexpand(R,I2,O2), % process the rest
    l(H,O1),O1 ins I, % duplicate current ship size H times
    append(O2,O1,O). % larger ship size goes in front

% Print the result
pboard(A):-m(prow,A).
prow(R):-m(pcell,R),print('\n').
pcell(E):-var(E)-&gt;print(@);print(E).

game(L,H,S):-
    board(L,A), % create board
    sort(S,SS), % remove duplicates
    markshot(A,SS), % mark positions that have been shot
    shipexpand(H,HH),!, % make a list of ships
    l(SC,SS),sumlist(HH,BC),L*L-SC&gt;=BC, % check to speed-up, can be removed
    placeships(HH,A),!, % place ships
    pboard(A). % print result


Query format:

game(Board_Size, Ships_List, Shots_List).


Sample query (using the sample in the question):

?- game(4,[1,1,1],[(2,1),(3,2),(3,3),(4,1),(4,3),(4,4)]).
ssss
\ss@
@\\@
\@\\
true.

?- game(4,[2,2,0,1],[(2,1),(3,2),(3,3),(4,1),(4,3),(4,4)]).
ssss
\sss
s\\s
\s\\
true.