text:
Implement ROT-47... in ROT-47
Challenge: Implement ROT-47 in code that works as both itself and as the ROT-47 version of itself.
Scoring:
Your score is calculated as a percentage of used, ROT-47 eligible bytes in total of both versions of the program divided by total bytes (all characters) of both versions.
A used, ROT-47 eligible byte is any character that would be converted by the ROT-47 cipher that is not part of a comment or ignored by the compiler/interpreter. For example, any character in a brainfuck program that is not +-<>[],.  is not considered a used byte, and any character in a C program including and after // or inside /* */ is not considered a used byte. All special symbols in APL are not considered used, as are all characters in a Whitespace program (sorry).
Ties will be broken by the program with the most upvotes. If there is still a tie, then the shortest program wins.
Example scoring:
C: 62/64 = 96.875%
Notice there is a space in this program. Obviously also, this program is not a valid entry because it doesn't even compile, but I wanted to show how scoring works.
main(){printf("Hello World!");}

And what language does >2:?WXLAC:?E7WQw6==@ (@C=5PQXjN compile in?

@hosch250 lol, that was just a dumb example

By "ROT-47 eligible" do you mean "in the ASCII range 33 to 126"?  I.e. if my C program has spaces or newlines or tabs, do those count as ROT-47 eligible or not? What about the fact that some spaces are essential in order for a program to function in many languages - do those not count as used because they are not R47-eligible, even though the program would break without them?

@JonathanVanMatre The spaces or newlines or tabs don't count because I feel the scoring would be too complicated otherwise; and I don't want Whitespace to be able to score 100%, because that would defeat the purpose.

The score seems to be Turing-undecidable in the general case when using an interpreter, and dependent on undocumented properties of compilers when using a compiler.

To everyone who is objecting to my crazy scoring rules, please comment/answer here: http://meta.codegolf.stackexchange.com/questions/1167/change-scoring-type-after-the-fact

Ruby, 100% (74 characters)
Input on STDIN, output on STDOUT.
Vj=s=gets;puts(s.tr'!-~','P-~!-O');Vj;'lDl86EDjAFEDWD]ECVP\OV[V!\OP\~VXj;'

The second line is the first line ROT-47'd. Therefore, when ROT-47ing the whole program, it becomes:
';lDl86EDjAFEDWD]ECVP\OV[V!\OP\~VXj';jV=s=gets;puts(s.tr'!-~','P-~!-O');jV

My strategy here is based upon the fact that:

V is ' when ROT-47'd
j is ; when ROT-47'd
Therefore, Vj=...Vj; turns into ';l...';, which is essentially a no-op

Now you can create any arbitrary code that does anything normally and no-ops when ROT-47'd. This is because Vj=...Vj; can support running any code as you could do Vj=0;{INSERT ANY CODE};Vj;, and that will become '...'; when ROT-47'd. You just have to be careful not to use V in that code, since that will break it.

Similar logic can be used in reverse to produce the second half (jV instead of Vj)

okay you are correct I never specified that and I won't retroactively. However, spaces still do not count as eligible characters; this should be 136/140 I think.

@durron597 Fixed; no more spaces.

Dang ruby not requiring lines to end with a semicolon :)

C - 54.6%
Y;BW;XL;jNj;AW(){XL^Y;};main(int i,char**v){char*x=v[1];while(*x){if(*x>32&&*x<128)*x=(*x+15)%94+32;putchar(*x++);}}//Y^Nj>2:?W:?E :[492CYYGXL492CYIlG,`.jH9:=6WYIXL:7WYImbaUUYIk`agXYIlWYIZ`dXThcZbajAFE492CWYIZZXjNN

When ROT-47-translated, we get
*jq(j){j;};jp(WXL){/*jNj>2:?W:?E :[492CYYGXL492CYIlG,`.jH9:=6WYIXL:7WYImbaUUYIk`agXYIlWYIZ`dXThcZbajAFE492CWYIZZXjNN^^*/};main(int i,char**v){char*x=v[1];while(*x){if(*x>32&&*x<128)*x=(*x+15)%94+32;putchar(*x++);}}

Both programs compile, and ROT-47-translate the first argument:
$ ./a "hello world"
96==@ H@C=5

I had trouble getting this to work on ideone. I'm very impressed seeing a score above 50% though!

@durron597 It won't work on ideone as it accepts input via arguments, not stdin

Upvote for implementing ROT-47 for arguments, not just for self-translation. That should have been in the spec.

GolfScript, 120 / 120 bytes = 100%
{:&&32>&&+254<*{7+7+94%33+}*}%LiUUbamUUZadckYLfZfZhcTbbZNYNT

or, in ROT-47:
LiUUbamUUZadckYLfZfZhcTbbZNYNT{:&&32>&&+254<*{7+7+94%33+}*}%

No comments or string abuse.  The undefined command LiUUbamUUZadckYLfZfZhcTbbZNYNT (which equals the rest of the code in ROT-47) is a no-op, but it still gets executed by the interpreter, so I believe it counts as used.
This was actually a pretty easy challenge in GolfScript.  The main difficulty was in avoiding the digit 1, which is mapped by ROT-47 into the GolfScript command `.  The commands ., -, ,, \, [, /, ] and ^ also had to be avoided, but that was fairly easy in this case, since the task required no array building.
Bonus:
Here's a GolfScript period-2 quine (i.e. a program that prints a second program that prints the first program again) where the two programs are the ROT-47 transforms of each other:
{`'0$~'+.{7+7+94%33+}%@!{0$@@;}*}0$~L1V_SOVZ]LfZfZhcTbbZNToPL_SoojNYN_SO

This program outputs itself ROT-47 encoded, yielding another GolfScript program:
L1V_SOVZ]LfZfZhcTbbZNToPL_SoojNYN_SO{`'0$~'+.{7+7+94%33+}%@!{0$@@;}*}0$~

which, in turn, also outputs itself ROT-47 encoded, yielding the previous program again.  Thus, this program is also a rotating quine.

Your denominator is wrong: "divided by total bytes (all characters) of both versions". 60/120 = 50%

@JonathanVanMatre: All bytes in both versions are used (= executed by the interpreter), so that would be 120 / 120 = still 100%.

I'm unsure of the scoring because I don't know golfscript. I know that, for example, A in brainfuck would count in the numerator but not the denominator. Is this the same thing or different?

@durron597: LiUUbamUUZadckYLfZfZhcTbbZNYNT is a valid identifier in GolfScript, and will be executed as a command. However, it's not one of the built-in commands, nor is it assigned a meaning by the program, so by default it simply does nothing.

python, 96.1% (?)
According to your definition, strings count as used code?
V=input();print("".join([chr(33+(ord(V[i])+14)%94)for i in range(len(V))]));V
'l:?AFEWXjAC:?EWQQ];@:?W,49CWbbZW@C5WD,:.XZ`cXThcX7@C : :? C2?86W=6?WDXX.XXj'

In retrospect they shouldn't have, but it's far too late now


text:
Shortest program that displays a red 3D cube
Write the shortest program you can that displays a red 3D cube.
Rules:

The cube must be red, have 6 rendered sides, and be displayed in 3D.
Your program cannot load any textures.
More than 1 side must be visible.
The result does not need to be rotatable.

i think u need to add a condition that more than 1 side is visible.

Only few languages would do the job for "must use either Direct3D or OpenGL" and like have been said, include a sample and How many sides? Is there a degree?

What does "red, have 6 sides and be 3D" mean? Did you mean that there needs to be shading? That we have to actually draw 6 sides, but only 2 or 3 have to be visible? Did you mean that the displayed result has to rotatable?

@Quincunx sorry if what I said was unclear. The cube has to be a solid red colour and  6 sides must be rendered but only 2 or 3 sides must be visible. The result doesn't have to be rotatable.

What do you mean by 'cannot load any textures'? Do you mean that you can't simply load an image of a red cube or that you can't use textures to make the cube red?

Generally, you should not change the contest rules after answers have been given. If you do so, it should be only to add clarification of what was meant by the rules already given.

I think this needs to be tagged [tag:graphical-output] or this question should be closed as unclear.

In respect to the close vote going on at the moment: I don't think this is specified enough. For example, does an orthographic projection count as 3D? What about an isometric projection? The question asks for a projection to be hardcoded ("does not need to be rotatable"); is it sufficient to instead hardcode the projected locations of the points? Is any lighting required, or can all the sides be the exact same shade of red? If so, is it legal to just draw a solid rectangle/hexagon, or must it be drawn as two rectangles/parallelograms/trapezia?

Someone answer in Minecraft

T-SQL, 168 chars (but no OpenGL)
Decidedly not using OpenGL or Direct3D because there is absolutely no way to do that in SQL. I think I have a pretty nice little cube, anyway.
RAISERROR('
      @@@
   @@@@@@@@@
@@@@@@@@@@@@@@@
x@@@@@@@@@@@@&&
xxx@@@@@@@@&&&&
xxxxx@@@&&&&&&&
xxxxxx&&&&&&&&&
 xxxxx&&&&&&&
   xxx&&&&
     x&&
',15,1)

Exploiting the fact that errors of high severity are raised in red:

Nice rule bending!

There are some trailing spaces in cube's 2nd line. Without them is just 156 characters long. If you specify the code block's language as “lang-sql”, the cube will be red even in the source code.

Yeah, I deliberately didn't super-golf this one because it is technically against the rules since it uses no OpenGL/Direct3D. People can vote me up if they like but I shouldn't win here.

If lazy answers like this are upvoted, what incentive is there to work on real solutions?

I don't consider it a lazy answer - I drew my cube by hand! How is that more lazy than using a built-in Cuboid/cube function in Mathematica/Sage? Toward your question of incentive, I offer my own incentive for this answer: self-amusement. I fully expected a healthy heap of downvotes, but I made (and honestly advertised) this non-compliant answer for my own delight. If your work isn't for your own pleasure, what is it good for?

 Mathematica 25
Graphics3D@{Red,Cuboid[]}

Instructions for testing this answer without Mathematica installed:

Download http://pastebin.com/3dnGNHCP and save it as *.CDF
Dowload the free CDF environment from Wolfram Research at
https://www.wolfram.com/cdf-player/ (not a small file)
The cube can be "dragged" to rotate it!

Kudos for including CDF instructions!

@JonathanVanMatre Thanks! One of the major problems for using Mathematica solutions in this site is the need for a non-free environment to test them. That can be overcome (to a certain extent) by sharing CDF documents.

Does mathematica use OpenGL?

@TheDoctor Short answer:"yes".Long answer: "You can configure it" (http://support.wolfram.com/kb/3303)

TXT, 12 bytes
This is a TXT file with ANSI escape codes and UTF-8 characters. I can show its contents as a C string:
"\033[31m\xe2\xac\xa2\033[m\n"

or as a hexdump:
0000000: 1b5b 3331 6de2 aca2 1b5b 6d0a            .[31m....[m.

This is the result when it is "executed" with cat on a terminal.
You can see the small cube, solid red, with 3 visible faces and no texture loaded:

This is a really clever answer, but txt doesn't technically meet the criteria for a programming language

But you could use /// or PHP as a workaround.

I´d use some *nix shell for that.

May i be the first to...
Processing, 513 110
void setup(){size(640,360,P3D);}void draw(){fill(255,0,0);translate(width/2,height/2,0);rotateX(0.7);box(99);}

So far the only actual OpenGL answer..

Mathematica uses OGL and D3D under the hood, although the problem becomes "How do you prove it was used when this particular graphic was rendered?"  There is probably a way to do that in MM; I just don't know what it is. I upvoted you because I like your choice of perspective.

You can reduce some characters by using a smaller size i.e. size(99,99,P3D); and then use 50 instead of width/2 and height/2 in your translate(). Also, you can remove the 0 in the 0.7, i.e. make it rotateX(.7);. Also remember to scale down the box. Finally, you can move everything into setup() and delete the void draw() altogether.

Too bad there's no award for most improved, because it would surely be yours.

Sage, 17
Note: after some research I realised that this does not use OpenGL.
cube(color='red')

Output:

I can finally beat Mathematica!
It uses Jmol (which comes with the Sage installation) to show the cube, which allows rotation by dragging.

Does this use OpeGL?

Nice:). How many chars does it cost to remove the numbers?

@belisarius I'm quite new to this Sage thing, and after going through the documentation I can't seem to find a way to remove the axes. Sorry.

@TheDoctor Sorry, no. Added a note in the answer to state that.

Looks like OpenGL/Direct has been dropped from the requirements.

@belisarius I just found out, to remove the numbers I can do cube(color='red',frame=0) which costs an extra of 8 chars.

@ace Good! Now you know more Sage! :)

Processing, 68 Chars
Ultra-golf version of @TheDoctor 's answer, using tips from @Ace, plus one of my own (rotation.)
void setup(){size(99,99,P3D);fill(#FF0000);translate(9,9,0);box(9);}

Produces a pathetically small cube of just 9 units per side (image at left.) Changing the 9's to 25's we get a larger cube (image at right.)
By keeping the cube far from the centre of the window, we can see the bottom and right hand side without needing to rotate (if it was in the centre of the window, they would be hidden.

Colour in Processing is a 4-byte value: alpha(opaqueness),R,G,B. The # notation implies an opaqueness of FF. I just found I can save 1 character by specifiying the colour as -65536, which gets coerced into 0xFFFF0000 unsigned. -9766=-38*(256+1) gives a pale pink cube.

Mathematica 9, 21
Image3D@{{{{3,0,0}}}}

Mathematica 10, 17
Image3D@{{{Red}}}

 Windows Batch, 51 chars
@echo off
color 0c
echo   _
echo /!_!
echo |/_/

I know this is cheating, but at least I get bronze (at the time this was posted). Partially inspired by Jonathan van Matre's answer.

Haha, chutzpah!

JAVASCRIPT - TQUERY (108 chars)

w=tQuery.createWorld().boilerplate().start();tQuery.createCube().addTo(w).setBasicMaterial().color(0xff0000)
<script src="https://jeromeetienne.github.io/tquery/build/tquery-bundle.js"></script>

http://jsfiddle.net/Gy4w7/335/

Postscript 920
Requires mat.ps.
/olddiv/div load def/div{dup 0 eq{pop pop
100000}{olddiv}ifelse}def(mat.ps)run/disp<</cam[0
0 10]/theta[0 0 0]/eye[0 0 20]/Rot 3 ident>>def/makerot{theta
0 get roty theta 1 get rotx matmul theta 2 get rotz matmul}def/proj{DICT
begin cam{sub}vop Rot matmul 0 get aload pop eye aload pop 4 3 roll div
exch neg 4 3 roll add 1 index mul 4 1 roll 3 1 roll sub mul exch end}dup
0 disp put def/v[[1 1 -1][-1 1 -1][-1 -1 -1][1 -1 -1][1 1 1][-1 1 1][-1 -1 1][1 -1 1]]def
/fv[[0 1 2 3][0 4 5 1][1 5 6 2][2 6 7 3][3 7 4 0][4 7 6 5]]def/R 20 def/H -3 def/ang 0 def
{300 700 translate 1 70 dup dup scale div setlinewidth
disp begin/cam[ang sin R mul H ang cos R mul]def/theta[ang H R atan 0]def/Rot makerot def end
fv{{v exch get proj}forall moveto lineto lineto lineto closepath 1 0 0 setrgbcolor fill}forall
fv{{v exch get proj} forall moveto lineto lineto lineto closepath 0 setgray stroke}forall
showpage/ang ang 3 add def}loop

Ungolfed and commented.
%!
/olddiv/div load def
/div{dup 0 eq{pop pop 100000}{olddiv}ifelse}def
(mat.ps)run

/disp <<
    /cam [ 0 0 10 ] % Camera position
    /theta [ 0 0 0 ] % Rotation sequence
    /eye [ 0 0 20 ] % Eye relative to image surface
    /Rot 3 ident
>> def

/makerot {
    theta 0 get roty
    theta 1 get rotx matmul
    theta 2 get rotz matmul
} def

% Ax Ay Az
/proj { DICT begin
    %3 array astore
    %dup == flush
    cam {sub}vop %Camera translation
    %pstack()=
    Rot matmul %Camera rotation
    0 get aload pop % Dx Dy Dz
    eye aload pop % Dx Dy Dz Ex Ey Ez
    %pstack()=
    4 3 roll div % Dx Dy Ex Ey Ez/Dz
    exch neg % Dx Dy Ex Ez/Dz -Ey
    4 3 roll add % Dx Ex Ez/Dz Dy-Ey
    1 index mul % Dx Ex Ez/Dz Ez(Dy-Ey)/Dz
    4 1 roll 3 1 roll % Ez(Dy-Ey)/Dz Ez/Dz Dx Ex
    sub mul exch % Ez(Dx-Ex)/Dz Ez(Dy-Ey)/Dz
    %pstack ()=
end } dup 0 disp put def

/v [[  1  1  -1 ] %cube vertices
    [ -1  1  -1 ]
    [ -1 -1  -1 ]
    [  1 -1  -1 ]
    [  1  1   1 ]
    [ -1  1   1 ]
    [ -1 -1   1 ]
    [  1 -1   1 ]] def
/fv [[ 0 1 2 3 ] %cube faces out of vertices
     [ 0 4 5 1 ]
     [ 1 5 6 2 ]
     [ 2 6 7 3 ]
     [ 3 7 4 0 ]
     [ 4 7 6 5 ]
     ] def

/R 20 def
/H -3 def
/ang 0 def

{
    300 700 translate
    1 70 dup dup scale div setlinewidth

    disp begin
        /cam [ ang sin R mul  H  ang cos R mul ] def
        /theta [ ang  H R atan  0 ] def
        /Rot makerot def
    end

    fv {
        { v exch get proj } forall
        moveto lineto lineto lineto closepath
        1 0 0 setrgbcolor fill
    } forall

    fv {
        { v exch get proj } forall
        moveto lineto lineto lineto closepath
        0 setgray stroke
    } forall

    showpage
    /ang ang 3 add def
} loop

RBX.Lua, 83 bytes
s=Instance.new("Part",workspace)s.BrickColor=BrickColor.new(21)s.Size=Vector3.new()

Result:

Explanation:
s=Instance.new("Part",workspace)  Instances a new Brick in the world.
s.BrickColor=BrickColor.new(21)   Makes it red. 21 is the color code for "Bright red".
s.Size=                           We have to set the size, because a brick isn't cubic.
Vector3.new()                     Initiates a [0, 0, 0] size. The brick rounds this up
                                  to the minimum size.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Robots! Collect these pickles!
I seem to have gotten myself into a bit of a pickle. Literally. I dropped a bunch of pickles on the floor and now they're all scattered about! I need you to help me collect them all. Oh, did I mention I have a bunch of robots at my command? (They're also all scattered all over the place; I'm really bad at organizing things.)
You must take input in the form of:
P.......
..1..2..
.......P
........
P3PP...4
.......P

i.e., multiple lines of either ., P (pickle), or a digit (robot's ID). (You may assume that each line is of equal length, padded with ..) You can input these lines as an array, or slurp from STDIN, or read in a comma-separated single line, or read a file, or do whatever you would like to take the input.
Your output must be in the form of n lines, where n is the highest robot ID. (Robot IDs will always be sequantial starting at 1.) Each line will contain the robot's path, formed from the letters L (left), R (right), U (up), and D (down). For example, here's an example output for that puzzle:
LLU
RDR
LRRR
D

It can also be
LLU RDR LRRR D

Or
["LLU","RDR","LRRR","D"]

Or any format you would like, as long as you can tell what the solution is supposed to be.
Your goal is to find the optimal output, which is the one that has the least steps. The amount of steps is counted as the greatest amount of steps from all of the robots. For example, the above example had 4 steps. Note that there may be multiple solutions, but you only need to output one.
Scoring:

Your program will be run with each of the 5 (randomly generated) test cases.
You must add the steps from each run, and that will be your score.
The lowest total, cumulative score will win.
You may not hard-code for these specific inputs. Your code should also work for any other input.
Robots can pass through each other.
Your program must be deterministic, i.e. same output for every run. You can use a random number generator, as long as it's seeded and consistently produces the same numbers cross-platform.
Your code must run within 3 minutes for each of the inputs. (Preferrably much less.)
In case of a tie, most upvotes will win.

Here are the test cases. They were randomly generated with a small Ruby script I wrote up.
P.......1.
..........
P.....P...
..P.......
....P2....
...P.P....
.PP..P....
....P....P
PPPP....3.
.P..P.P..P

....P.....
P....1....
.P.....PP.
.PP....PP.
.2.P.P....
..P....P..
.P........
.....P.P..
P.....P...
.3.P.P....

..P..P..P.
..1....P.P
..........
.......2P.
...P....P3
.P...PP..P
.......P.P
..P..P..PP
..P.4P..P.
.......P..

..P...P...
.....P....
PPPP...P..
..P.......
...P......
.......P.1
.P..P....P
P2PP......
.P..P.....
..........

......PP.P
.P1..P.P..
......PP..
P..P....2.
.P.P3.....
....4..P..
.......PP.
..P5......
P.....P...
....PPP..P

Good luck, and don't let the pickles sit there for too long, or they'll spoil!

Oh, and why pickles, you ask?
Why not?

There is no reasonable way to show that you actually found the "optimal output" since this is essentially a traveling salesman(men) problem and is NP complete.

@Wally Hmm, it is? Perhaps someone should find the minimum steps for the test case provided, and then all answers can be based upon that.

The test case is probably small enough to brute force a minimum - if someone wanted to do that. And/or everyone who answers could tell what they got for the test case and you could require other answers to at least match that minimum.

Sorry, I downvoted temporarily. Perhaps you could change the goal to something better (ie. clearly provable)

@belisarius Alright, edited the goal.

So, downvote removed :)

"[I am in a pickle]. Literally". *Pictures a doorknob stuck in a pickle*. Thanks for misusing the word. It gave me a chance to think of something funny (the best way to counter misuse of the word is to assume it is meant literally; it makes the sentence very funny).

Can robots pass through each other? If not, what are the timing restrictions on interpreting the paths?

How to calculate the score when I'm using random numbers in the algorithm? Should I just hardcode a seed?

To stop people coding to your tests, maybe you could have a couple of other tests used for scoring which you don't reveal in the question. I realise you can't really do that now that the question is posted, but maybe for future reference?

@PeterTaylor Yes, robots can pass through each other. I shall edit for clarification.

@SztupY Your answer must be deterministic. Therefore, hardcoding a seed would work. Edited to clarify

@Gareth The problem with that is that scores will not be known until the testcases are revealed, and then submissions after that will already see the testcases.

There are 20 pickles in the first test case, 20 in the second, 22 in the third, 19 in the fourth and 22 in the fifth. So, we can forget about using brute-force. (Calculated using  prompt().split('').filter(function(a){return a==='P'}).length.)

Ruby, 15+26+17+26+17 = 101
Robot Finds Pickles!
Okay, here's a baseline to get people started, using the following super-naive algorithm:

Each tick, each robot will act in numeric order, performing the following steps:

Identify the closest (Manhattan distance) pickle that no other robots are targeting.
Figure out which adjacent squares are available to move to.
Choose one of those squares, preferring directions that move it closer to the selected pickle.

Here's what it looks like for Test Case #1:

Obviously this isn't very good but it's a start!
Code:
Tile = Struct.new(:world, :tile, :x, :y) do
    def passable?
        tile =~ /\.|P/
    end

    def manhattan_to other
        (self.x - other.x).abs + (self.y - other.y).abs
    end

    def directions_to other
        directions = []
        directions << ?U if self.y > other.y
        directions << ?D if self.y < other.y
        directions << ?L if self.x > other.x
        directions << ?R if self.x < other.x
        directions
    end

    def one_step direction
        nx,ny = case direction
            when ?U then [self.x, self.y - 1]
            when ?D then [self.x, self.y + 1]
            when ?L then [self.x - 1, self.y]
            when ?R then [self.x + 1, self.y]
        end

        self.world[nx,ny]
    end

    def move direction
        destination = one_step(direction)
        raise "can't move there" unless destination && destination.passable?

        destination.tile, self.tile = self.tile, ?.
    end
end

class World
    DIRECTIONS = %w(U D L R)

    def initialize s
        @board = s.split.map.with_index { |l,y| l.chars.map.with_index { |c,x| Tile.new(self, c, x, y) }}
        @width = @board[0].length
    end

    def [] x,y
        y >= 0 && x >= 0 && y < @board.size && x < @board[y].size && @board[y][x]
    end

    def robots
        tiles_of_type(/[0-9]/).sort_by { |t| t.tile }
    end

    def pickles
        tiles_of_type ?P
    end

    def tiles_of_type type
        @board.flatten.select { |t| type === t.tile }
    end

    def inspect
        @board.map { |l| l.map { |t| t.tile }*'' }*?\n
    end
end

gets(nil).split("\n\n").each do |input|
    w = World.new(input)
    steps = Hash[w.robots.map { |r| [r.tile, []] }]
    while (pickles_remaining = w.pickles).size > 0
        current_targets = Hash.new(0)

        w.robots.each do |r|
            target_pickle = pickles_remaining.min_by { |p| [current_targets[p], r.manhattan_to(p)] }

            possible_moves = World::DIRECTIONS.select { |d| t = r.one_step(d); t && t.passable? }
            raise "can't move anywhere" if possible_moves.empty?

            direction = (r.directions_to(target_pickle) & possible_moves).first || possible_moves[0]

            current_targets[target_pickle] += 1
            steps[r.tile] << direction
            r.move(direction)
        end
    end

    puts steps.values.map &:join
    p steps.values.map { |v| v.size }.max
end

Takes input on STDIN in exactly the format of the test case code-block in the original question.  Here's what it prints for those test cases:
DDLLDLLLLULLUUD
LDLRRDDLDLLLLDR
URDDLLLLLULLUUL
15
ULDLDDLDRRRURRURDDDDDDDLLL
UUULDDRDRRRURRURDLDDDDLDLL
ULUURURRDDRRRRUUUDDDDLDLLL
26
URRRDRUDDDDLLLDLL
RUUUDLRRDDDLLLDLL
LDRDDLDDLLLLLLLUU
RUUURDRDDLLLLLUUU
17
DULLUUUUULDLDLLLLLDDRUUUUR
UDLRRRURDDLLLUUUUURDRUUUUD
26
LDDLDUUDDDUDDDDDR
ULUULDDDDDRDRDDDR
LULLDUUDDDRDRDDDR
UUUURDUURRRRDDDDD
LDLLUDDRRRRRRUDRR
17

Python, 16+15+14+20+12 = 77
I don't really have any prior experience to travelling salesman type problems but I had a bit of time on my hands so I thought I would give it a shot. It basically attempts to allot each bot certain pickles by walking it though a preliminary run where they go for the ones closest to them and farthest from the others. It then brute-forces the most efficient way for each bot to collect its allotted pickles.
I really have no idea how viable this method is, but I suspect it would not work well for larger boards with fewer bots (the fourth board already sometimes takes over two minutes).
Code:
def parse_input(string):
    pickles = []
    size = len(string) - string.count('\n')
    poses = [None] * (size - string.count('.') - string.count('P'))
    for y,line in enumerate(string.strip().split('\n')):
        for x,char in enumerate(line):
            if char == '.':
                continue
            elif char == 'P':
                pickles.append((x,y))
            else:
                poses[int(char)-1] = (x,y)
    return pickles, poses

def move((px,py),(tx,ty)):
    if (px,py) == (tx,ty):
        return (px,py)
    dx = tx-px
    dy = ty-py
    if abs(dx) <= abs(dy):
        if dy < 0:
            return (px,py-1)
        else:
            return (px,py+1)
    else:
        if dx < 0:
            return (px-1,py)
        else:
            return (px+1,py)

def distance(pos, pickle):
    return abs(pos[0]-pickle[0]) + abs(pos[1]-pickle[1])

def calc_closest(pickles,poses,index):
    distances = [[distance(pos,pickle) for pickle in pickles] for pos in poses]
    dist_diffs = []
    for i, pickle_dists in enumerate(distances):
        dist_diffs.append([])
        for j, dist in enumerate(pickle_dists):
            other = [d[j] for d in distances[:i]+distances[i+1:]]
            dist_diffs[-1].append(min(other)-dist)

    sorted = pickles[:]
    sorted.sort(key = lambda ppos: -dist_diffs[index][pickles.index(ppos)])
    return sorted

def find_best(items,level):
    if level == 0:
        best = (None, None)
        for rv, rest in find_best(items[1:],level+1):
            val = distance(items[0],rest[0]) + rv
            if best[0] == None or val < best[0]:
                best = (val, [items[0]] + rest)
        return best

    if len(items) == 1:
        return [(0,items[:])]

    size = len(items)
    bests = []
    for i in range(size):
        best = (None, None)
        for rv, rest in find_best(items[:i]+items[i+1:],level+1):
            val = distance(items[i],rest[0]) + rv
            if best[0] == None or val < best[0]:
                best = (val, [items[i]] + rest)
        if best[0] != None:
            bests.append(best)
    return bests

def find_best_order(pos,pickles):
    if pickles == []:
        return 0,[]
    best = find_best([pos]+pickles,0)
    return best

def walk_path(pos,path):
    history = ''
    while path:
        npos = move(pos, path[0])
        if npos == path[0]:
            path.remove(path[0])

        if npos[0] < pos[0]:
            history += 'L'
        elif npos[0] > pos[0]:
            history += 'R'
        elif npos[1] < pos[1]:
            history += 'U'
        elif npos[1] > pos[1]:
            history += 'D'
        pos = npos
    return history

def find_paths(input_str):
    pickles, poses = parse_input(input_str)                 ## Parse input string and stuff
    orig_pickles = pickles[:]
    orig_poses = poses[:]
    numbots = len(poses)

    to_collect = [[] for i in range(numbots)]               ## Will make a list of the pickles each bot should go after
    waiting = [True] * numbots
    targets = [None] * numbots
    while pickles:
        while True in waiting:                              ## If any bots are waiting for a new target
            index = waiting.index(True)
            closest = calc_closest(pickles,poses,index)     ## Prioritizes next pickle choice based upon how close they are RELATIVE to other bots
            tar = closest[0]

            n = 0
            while tar in targets[:index]+targets[index+1:]:                 ## Don't target the same pickle!
                other_i = (targets[:index]+targets[index+1:]).index(tar)
                dist_s = distance(poses[index],tar)
                dist_o = distance(poses[other_i],tar)
                if dist_s < dist_o:
                    waiting[other_i] = True
                    break

                n += 1
                if len(closest) <= n:
                    waiting[index] = False
                    break
                tar = closest[n]

            targets[index] = tar
            waiting[index] = False

        for i in range(numbots):                            ## Move everything toward targets  (this means that later target calculations will not be based on the original position)
            npos = move(poses[i], targets[i])
            if npos != poses[i]:
                poses[i] = npos
            if npos in pickles:
                to_collect[i].append(npos)
                pickles.remove(npos)
                for t, target in enumerate(targets):
                    if target == npos:
                        waiting[t] = True

    paths = []
    sizes = []

    for i,pickle_group in enumerate(to_collect):                    ## Lastly brute force the most efficient way for each bot to collect its allotted pickles
        size,path = find_best_order(orig_poses[i],pickle_group)
        sizes.append(size)
        paths.append(path)
    return max(sizes), [walk_path(orig_poses[i],paths[i]) for i in range(numbots)]

def collect_pickles(boards):
    ## Collect Pickles!
    total = 0
    for i,board in enumerate(boards):
        result = find_paths(board)
        total += result[0]
        print "Board "+str(i)+": ("+ str(result[0]) +")\n"
        for i,h in enumerate(result[1]):
            print '\tBot'+str(i+1)+': '+h
        print

    print "Total Score: " + str(total)

boards = """
P.......1.
..........
P.....P...
..P.......
....P2....
...P.P....
.PP..P....
....P....P
PPPP....3.
.P..P.P..P

....P.....
P....1....
.P.....PP.
.PP....PP.
.2.P.P....
..P....P..
.P........
.....P.P..
P.....P...
.3.P.P....

..P..P..P.
..1....P.P
..........
.......2P.
...P....P3
.P...PP..P
.......P.P
..P..P..PP
..P.4P..P.
.......P..

..P...P...
.....P....
PPPP...P..
..P.......
...P......
.......P.1
.P..P....P
P2PP......
.P..P.....
..........

......PP.P
.P1..P.P..
......PP..
P..P....2.
.P.P3.....
....4..P..
.......PP.
..P5......
P.....P...
....PPP..P
""".split('\n\n')

collect_pickles(boards)

Output:
Board 0: (16)

    Bot1: DLDLLLLDLLULUU
    Bot2: LDLDLLDDLDRURRDR
    Bot3: URDDLLLULULURU

Board 1: (15)

    Bot1: ULRDRDRRDLDDLUL
    Bot2: DDURURULLUUL
    Bot3: ULRRDRRRURULRR

Board 2: (14)

    Bot1: URRRDDDDDRLLUL
    Bot2: UUURDRDDLD
    Bot3: DDDLDDLUUU
    Bot4: RULLLDUUUL

Board 3: (20)

    Bot1: DLULUUUUULDLLLULDDD
    Bot2: LURDDURRDRUUUULUULLL

Board 4: (12)

    Bot1: LDDLDR
    Bot2: ULUULRRR
    Bot3: LUURURDR
    Bot4: RRRDRDDDR
    Bot5: LLDLRRRDRRRU

Total Score: 77

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
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 "D2".
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 "missed". 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 "missed" 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 <<< $'A2\nA4\nB3\nC3\nC4\D4'

26x26? I sketched a solution based on regexps and recursion, and it gets extremely slow = unusable for fields more than 6x6. Either I do something very stupid, or lack of answers means that others have no success too.

I just wrote an implementation in C, it computes instantly for at least 10x10 with a 4,3,2,1 shipset

@mniip: Do you have any specific way of dealing with hard cases (big board, many ships, failing due to position of shots)? Or is it just (a bit smart) brute force?

It has a few optimizations, f.e tries to place small ships first, and excludes swapping ships of equal size from the brute force. It's kinda slow when there are lots of ships on a small and almost empty board.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ I've added an example solution link.

I used to do this with Hangman. I'd pick a 4 letter word, and then just mentally swap to whatever word didn't have the letters they'd guessed. No one ever caught on. :)

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.

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#>0,X#=<L,Y#>0,Y#=<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)->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#>0,X#=<L,Y#>0,Y#=<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)->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>=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#>0,X#=<L,Y#>0,Y#=<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] --> [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)->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>=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.

Ah darn beat me by a few dozen characters! Not sure if I can compress mine any more but I'll keep trying... nice use of Prolog!

@Claudiu: My solution still have a "buffer" of 20 or so characters. I left those checking code in there for performance reason, but they can be removed without affecting the correctness ;) I don't bother if other answers get below 500, though.

Matlab - 536 chars
Updated: Much smaller output formatting, some loop whitespace removed.
Updated: Added golfed version
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

Here is the golfed version.
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

Here's some samples.
>>bs(4,['A1';'B3'],[2,1])
1220
0000
2120
0000

>>bs(4,['A1';'B4'],[2,2])
1022
2000
0022
2100

>> bs(4,['A1';'B4';'C2'],[3,1])
1022
2010
0020
2100

>> bs(4,['A1';'B4';'C2'],[3,2])
:(

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...

Python, 464 chars
B,L,M=input()
R=range(B)
C=B+1
M=sum(1<<int(m[1:])*C-C+ord(m[0])-65for m in M)
def P(L,H,S):
 if len(L)==0:
  for y in R:print''.join('.#!'[(S>>y*C+x&1)+2*(M>>y*C+x&1)]for x in R)
  return 1
 for s in[2**L[0]-1,sum(1<<C*j for j in range(L[0]))]:
  for i in range(C*C):
   if H&s==s and P(L[1:],H&~(s|s<<1|s>>1|s<<B|s>>B|s<<C|s>>C|s<<C+1|s>>C+1),S|s):return 1
   s*=2
 return 0
P(sum(([l+1]*k for l,k in enumerate(L)),[])[::-1],sum((2**B-1)<<B*j+j for j in R)&~M,0)

Input (stdin):
7, [4,1,2,0,1], ['A1','B2','C3']

Output:
!#####.
.!.....
##!###.
.......
###.#.#
.......
#.#....

Works using integers holding bitmaps of various features:
M = bitmap of misses
H = bitmap of holes where ships can still go
S = bitmap of ships already placed
L = list of ship sizes not yet placed
B = dimension of board
C = bitmap row length

If you don't mind, do you do any optimization, or is it just straight brute force?

There's one optimization: the [::-1] which makes it try the longest ship first.  It also backtracks as soon as it finds a ship it can't place.

You can use a single tab instead of 2 or 3 spaces on lines 7, 8, 11, and 12, reducing the byte count to 458. See here.

Python, 562 characters, -8 with ugly output, +4? for bash invocation
I=int;R=range
import sys;a=sys.argv
S=I(a[1]);f=[[0]*(S+2)for _ in R(S+2)]
C=a[2].split()
X=[]
for i,n in enumerate(C):X=[i+1]*I(n)+X
Q=a[3].split()
for q in Q:f[I(q[1:])][ord(q[0])-64]=1
D=R(-1,2)
V=lambda r,c:(all(f[r+Q][c+W]<2for Q in D for W in D),0,0)[f[r][c]]
def F(X):
 if not X:print"\n".join(" ".join(" .@"[c]for c in r[1:-1])for r in f[1:-1])
 x=X[0];A=R(1,S+1)
 for r in A:
    for c in A:
     for h in(0,1):
        def P(m):
         for i in R(x):f[(r+i,r)[h]][(c,c+i)[h]]=m
        if(r+x,c+x)[h]<S+2and all(V((r+i,r)[h],(c,c+i)[h])for i in R(x)):P(2);F(X[1:]);P(0)
F(X)

Note: the indent levels are space, tab, tab + space, tab + tab, and tab + tab + space. This saves a few characters from using spaces only.
Usage and example:
Takes input from command line arguments. Outputs a blank as a space, a shot as a ., and a @ as part of a ship:
$ python bships_golf.py "7" "4 0 2 0 1" \
         "A1 C3 B5 E4 G6 G7 A3 A4 A5 A6 C1 C3 C5 C7 B6 B7 D1 D2 G3" 2>X
. @ . . @ @ @
  @   .
. @ . @   @ .
.     @ .
. . . @   @
. .   @     .
@ . . @   @ .

When unsolvable, prints nothing:
$ python bships_golf.py "3" "2" "A1 A3 B1 C1 C3" 2>X
. . .
@   @
.   .
$ python bships_golf.py "3" "2" "A1 A2 A3 B1 C1 C3" 2>X
$

The 2>X is to suppress an error message since the program exits by throwing an exception. Feel free to add a +4 penalty if deemed fair. Otherwise I'd have to do a try: ... except:0 to suppress it, which would take more characters anyway.
I can also print the output as numbers (0, 1, and 2) to shave off 8 characters, but I value aesthetics.
Explanation:
I represent the board as a list of lists of integers with size 2 greater than the input, to avoid having to do bounds checking. 0 represents an empty space, 1 a shot, and 2 a ship. I run through the shots list Q and mark all the shots. I convert the list of ships to an explicit list X of ships, e.g. [4, 0, 2, 0, 1] becomes [5, 3, 3, 1, 1, 1, 1]. Then it's a simple backtracking algorithm: in order of descending size order, try to place a ship, and then try to place the rest of the ships. If it doesn't work, try the next slot. As soon as it succeeds, the ship list X is null, and accessing X[0] throws an exception which quits the program. The rest is just heavy golfing (was initially 1615 characters).

C# solution
  public static class ShipSolution {
    private static int[][] cloneField(int[][] field) {

      int[][] place = new int[field.Length][];

      for (int i = 0; i < field.Length; ++i) {
        place[i] = new int[field.Length];

        for (int j = 0; j < field.Length; ++j)
          place[i][j] = field[i][j];
      }

      return place;

    }

    private static void copyField(int[][] source, int[][] target) {
      for (int i = 0; i < source.Length; ++i)
        for (int j = 0; j < source.Length; ++j)
          target[i][j] = source[i][j];
    }

    // Check if placement a legal one
    private static Boolean isPlacement(int[][] field, int x, int y, int length, Boolean isHorizontal) {
      if (x < 0)
        return false;
      else if (y < 0)
        return false;
      else if (x >= field.Length)
        return false;
      else if (y >= field.Length)
        return false;

      if (isHorizontal) {
        if ((x + length - 1) >= field.Length)
          return false;

        for (int i = 0; i < length; ++i)
          if (field[x + i][y] != 0)
            return false;
      }
      else {
        if ((y + length - 1) >= field.Length)
          return false;

        for (int i = 0; i < length; ++i)
          if (field[x][y + i] != 0)
            return false;
      }

      return true;
    }

    //  When ship (legally) placed it should be marked at the field
    //  2 - ship itself
    //  3 - blocked area where no other ship could be placed
    private static void markPlacement(int[][] field, int x, int y, int length, Boolean isHorizontal) {
      if (isHorizontal) {
        for (int i = 0; i < length; ++i)
          field[x + i][y] = 2;

        for (int i = x - 1; i < x + length + 1; ++i) {
          if ((i < 0) || (i >= field.Length))
            continue;

          for (int j = y - 1; j <= y + 1; ++j)
            if ((j >= 0) && (j < field.Length))
              if (field[i][j] == 0)
                field[i][j] = 3;
        }
      }
      else {
        for (int i = 0; i < length; ++i)
          field[x][y + i] = 2;

        for (int i = x - 1; i <= x + 1; ++i) {
          if ((i < 0) || (i >= field.Length))
            continue;

          for (int j = y - 1; j < y + length + 1; ++j)
            if ((j >= 0) && (j < field.Length))
              if (field[i][j] == 0)
                field[i][j] = 3;
        }
      }
    }

    // Ship placement itteration
    private static Boolean placeShips(int[][] field, int[] ships) {
      int[] vessels = new int[ships.Length];

      for (int i = 0; i < ships.Length; ++i)
        vessels[i] = ships[i];

      for (int i = ships.Length - 1; i >= 0; --i) {
        if (ships[i] <= 0)
          continue;

        int length = i + 1;

        vessels[i] = vessels[i] - 1;

        // Possible placements
        for (int x = 0; x < field.Length; ++x)
          for (int y = 0; y < field.Length; ++y) {
            if (isPlacement(field, x, y, length, true)) {
              int[][] newField = cloneField(field);

              // Mark
              markPlacement(newField, x, y, length, true);

              if (placeShips(newField, vessels)) {
                copyField(newField, field);

                return true;
              }
            }

            if (length > 1)
              if (isPlacement(field, x, y, length, false)) {
                int[][] newField = cloneField(field);

                // Mark
                markPlacement(newField, x, y, length, false);

                if (placeShips(newField, vessels)) {
                  copyField(newField, field);

                  return true;
                }
              }
          }

        return false; // <- the ship can't be placed legally
      }

      return true; //    <- there're no more ships to be placed
    }

    /// <summary>
    /// Solve ship puzzle
    /// </summary>
    /// <param name="size">size of the board</param>
    /// <param name="ships">ships to be placed</param>
    /// <param name="misses">misses in (line, column) format; both line and column are zero-based</param>
    /// <returns>Empty string if there is no solution; otherwise possible ship placement where
    ///   . - Blank place
    ///   * - "miss"
    ///   X - Ship
    /// </returns>
    public static String Solve(int size, int[] ships, String[] misses) {
      int[][] field = new int[size][];

      for (int i = 0; i < size; ++i)
        field[i] = new int[size];

      if (!Object.ReferenceEquals(null, misses))
        foreach (String item in misses) {
          String miss = item.Trim().ToUpperInvariant();

          int x = int.Parse(miss.Substring(1)) - 1;
          int y = miss[0] - 'A';

          field[x][y] = 1;
        }

      if (!placeShips(field, ships))
        return "";

      StringBuilder Sb = new StringBuilder();

      foreach (int[] line in field) {
        if (Sb.Length > 0)
          Sb.AppendLine();

        foreach (int item in line) {
          if (item == 1)
            Sb.Append('*');
          else if (item == 2)
            Sb.Append('X');
          else
            Sb.Append('.');
        }
      }

      return Sb.ToString();
    }
  }

  ...

  int size = 4;
  int[] ships = new int[] { 1, 1, 1 };
  String[] misses = new String[] {"C1", "C2", "B2", "A3", "A1", "B3", "D1"};

  // *X**
  // .**X
  // **.X
  // XX.X
  Console.Out.Write(ShipSolution.Solve(size, ships, misses));

While this is a great and fast solution, it doesn't seem to handle unsolvable tasks correctly. For example,   size=1 ships={1} moves={"A1"}.

I'm sorry, I've missed the condition when the next ship can't be placed legally. I've edited the solution.

Because the question is a [tag:code-golf], please try to keep your character count as low as possible (by removing whitespace for example), and include the character count in your code.

Character count as it stands now is 5399.

Perl, 455 447 437 436 422 418
$n=($N=<>+0)+1;@S=map{(++$-)x$_}<>=~/\d+/g;$_=<>;$f=('~'x$N.$/)x$N;substr($f,$n*$1-$n-65+ord$&,1)=x while/\w(\d+)/g;sub f{for my$i(0..$N*$n-1){for(0..@_-2){my($f,@b)=@_;$m=($s=splice@b,$_,1)-1;pos=pos($u=$_=$f)=$i;for(s/\G(~.{$N}){$m}~/$&&("\0"."\377"x$N)x$s|(o."\0"x$N)x$m.o/se?$_:(),$u=~s/\G~{$s}/o x$s/se?$u:()){for$k(0,$N-1..$n){s/(?<=o.{$k})~|~(?=.{$k}o)/!/sg}return$:if$:=@b?f($_,@b):$_}}}}$_=f$f,@S;y/!/~/;print

Indented:
$n=($N=<>+0)+1;
@S=map{(++$-)x$_}<>=~/\d+/g;
$_=<>;
$f=('~'x$N.$/)x$N;
substr($f,$n*$1-$n-65+ord$&,1)=x while/\w(\d+)/g;
sub f{
    for my$i(0..$N*$n-1){
        for(0..@_-2){
            my($f,@b)=@_;
            $m=($s=splice@b,$_,1)-1;
            pos=pos($u=$_=$f)=$i;
            for(s/\G(~.{$N}){$m}~/
              $&&("\0"."\377"x$N)x$s|(o."\0"x$N)x$m.o/se?$_:(),
              $u=~s/\G~{$s}/o x$s/se?$u:()){
                for$k(0,$N-1..$n){
                    s/(?<=o.{$k})~|~(?=.{$k}o)/!/sg
                }
                return$:if$:=@b?f($_,@b):$_
            }
        }
    }
}
$_=f$f,@S;
y/!/~/;
print

I expect it can be golfed further (e.g. with eval<> for pre-formatted input, as I see it's OK (?)), and also some other things (50 $ sigils? no, they'll stay).
Speed, as I said earlier, can be an issue (from instantaneous (see example below) to very-very long), depending on where the solution is on recursion tree, but let it be the question of obsolescence of hardware used. I'll do optimized version later, with recursion gone and 2-3 other obvious tricks.
It's run like this, 3 lines being fed through STDIN:
$ perl bf.pl
7
4 1 2 0 1
A1 B2 C3
xo~o~o~
~x~~~~~
o~xo~o~
~~~o~o~
o~~~~o~
o~~~~~~
o~ooooo

~ is the ocean (artistic solution, isn't it), o's  and xs are ships and shots.
First 5 lines get the input and prepare our 'battlefield'. $N is size, @S is unrolled array of ships (e.g. 1 1 1 1 2 3 3 5 as above), $f is a string representing battlefield (rows with newlines concatenated). Next is recursive subroutine, which expects current battlefield state and list of remaining ships. It checks left to right, top to bottom and tries to place each ship in each position, both horizontally and vertically (see? Ripe to optimize, but that'll be later). Horizontal ship is obvious regexp replacement, vertical a bit trickier -- bitwise string manipulation to replace in 'column'. On success (H, V or both), new inaccessible positions are marked with !, and it forks to next iteration. And so on.
Edit: OK, here's 594 bytes (when un-indented) version that actually tries to be useful (i.e. fast) - optimized to the best of my ability while still implementing the same techniques - recursion (albeit done 'manually') and regexps. It maintains a 'stack' - @A - array of states worth to investigate. A 'state' is 4 variables: current battlefield string, index from where to start trying to place ships, reference to array of remaining ships, and index of next ship to try. Initially there's a single 'state' - start of empty string, all ships. On match (H or V, see above), current state is pushed to investigate later, updated state (with a ship placed and inaccessible positions marked) is pushed and block is restarted. When end of battlefield string is reached without success, next available state from @A is investigated (if any).
Other optimizations are: not restarting from the very beginning of the string, trying to place large ships first, not checking ship of same size if previous one failed in the same position, + maybe something else (like no $& variable etc.).
$N=<>+0;
$S=[reverse map{(++$-)x$_}<>=~/\d+/g];
$_=<>;
$f=('~'x$N.$/)x$N;
substr($f,$N*$2-$N+$2-66+ord$1,1)=x while/(\w)(\d+)/g;
push@A,$f,0,$S,0;
O:{
    ($f,$i,$S,$m)=splice@A,-4;
    last if!@$S;
    F:{
        for$j($m..$#$S){
            next if$j and$$S[$j]==$$S[$j-1];
            $s=$$S[$j];
            my@m;
            $_=$f;
            $n=$s-1;
            pos=$i;
            push@m,$_ if s/\G(?:~.{$N}){$n}~/
                ${^MATCH}&("\0"."\377"x$N)x$s|(o."\0"x$N)x$n.o/pse;
            $_=$f;
            pos=$i;
            push@m,$_ if s/\G~{$s}/o x$s/se;
            if(@m){
                push@A,$f,$i,$S,$j+1;
                my@b=@$S;
                splice@b,$j,1;
                for(@m){
                    for$k(0,$N-1..$N+1){
                        s/(?<=o.{$k})~|~(?=.{$k}o)/!/gs
                    }
                    push@A,$_,$i+1,\@b,0
                }
                redo O
            }
        }
        redo if++$i-length$f
    }
    redo if@A
}
print@$S?'':$f=~y/!/~/r

.
perl bf+.pl
10
5 4 3 2 1
A1 B2 C3 A10 B9 C10 J1 I2 H3 I9 J10 A5 C5 E5 F6 G7
xooooo~oox
~x~~~~~~x~
ooxooooxo~
~~~~~~~~o~
xoxoxoo~o~
~o~o~x~~o~
~o~o~ox~~~
~~~~~o~ooo
oxo~~~~~x~
x~x~o~o~ox

OTOH, it still takes forever for impossible case 6 5 4 3 2 1 in example above. Maybe practical version should exit immediately if total ship tonnage exceeds battlefield capacity.

Java, 1178
Yeah much too long ._.
import java.util.*;class S{public static void main(String[]a){new S();}int a;int[][]f;List<L>l;Stack<Integer>b;S(){Scanner s=new Scanner(System.in);a=s.nextInt();f=new int[a][a];for(int[]x:f)Arrays.fill(x,95);s.next(";");b=new Stack();for(int i=1;s.hasNextInt();i++){b.addAll(Collections.nCopies(s.nextInt(),i));}s.next(";");while(s.findInLine("([A-Z])")!=null)f[s.match().group(1).charAt(0)-65][s.nextInt()-1]=79;l=new ArrayList();for(int i=0;i<a;i++){l.add(new L(i){int g(int c){return g(c,i);}void s(int c,int v){f[c][i]=v;}});l.add(new L(i){int g(int r){return g(i,r);}void s(int r,int v){f[i][r]=v;}});}if(s()){String o="";for(int r=0;r<a;r++){for(int c=0;c<a;c++)o+=(char)f[c][r];o+='\n';}System.out.print(o);}}boolean s(){if(b.empty())return true;int s=b.pop();Integer n=95;for(L c:l){int f=0;for(int x=0;x<a;x++){if(n.equals(c.g(x)))f++;else f=0;if(f>=s){for(int i=0;i<s;i++)c.s(x-i,35);if(s())return true;for(int i=0;i<s;i++)c.s(x-i,n);}}}b.push(s);return false;}class L{int i;L(int v){i=v;}void s(int i,int v){}int g(int i){return 0;}int g(int c,int r){int v=0;for(int x=-1;x<2;x++)for(int y=-1;y<2;y++)try{v|=f[c+x][r+y];}catch(Exception e){}return v&(f[c][r]|32);}}}

Ungolfed:
import java.util.*;

class S {
    public static void main(String[] a) {
        new S();
    }

    /**
     * Number of rows/columns
     */
    int a;

    /**
     * A reference to the full field
     */
    int[][] f;

    /**
     * List of Ls representing all columns/rows
     */
    List<L> l;

    /**
     * Stack of all unplaced ships, represented by their length as Integer
     */
    Stack<Integer> b;

    S() {
        // Read input from STDIN:
        Scanner s = new Scanner(System.in);
        a = s.nextInt();
        f = new int[a][a];
        // initialize field to all '_'
        for(int[] x: f)
            Arrays.fill(x, 95);
        // ; as separator
        s.next(";");
        b = new Stack();
        // Several int to represent ships
        for (int i = 1; s.hasNextInt(); i++) {
            // nCopies for easier handling (empty Stack => everything placed)
            b.addAll(Collections.nCopies(s.nextInt(), i));
        }
        // ; as separator
        s.next(";");
        // find an uppercase letter on this line
        while (s.findInLine("([A-Z])") != null) {
            // s.match.group(1) contains the matched letter
            // s.nextInt() to get the number following the letter
            f[s.match().group(1).charAt(0) - 65][s.nextInt() - 1] = 79;
        }
        // Loop is left when line ends or no uppercase letter is following the current position

        // Now create a List of Lists representing single columns and rows of our field
        l = new ArrayList();
        for (int i = 0; i < a; i++) {
            l.add(new L(i) {
                int g(int c) {
                    return g(c, i);
                }

                void s(int c, int v) {
                    f[c][i] = v;
                }
            });
            l.add(new L(i) {
                int g(int r) {
                    return g(i, r);
                }

                void s(int r, int v) {
                    f[i][r] = v;
                }
            });
        }
        // try to place all ships
        if (s()) {
            // print solution
            String o = "";
            for (int r = 0; r < a; r++) {
                for (int c = 0; c < a; c++) {
                    o += (char) f[c][r];
                }
                o += '\n';
            }
            System.out.print(o);
        }
    }

    /**
     * Try to place all ships
     *
     * @return {@code true}, if a solution is found
     */
    boolean s() {
        if (b.empty()) {
            // no more ships
            return true;
        }
        // take a ship from the stack
        int s = b.pop();
        // 95 is the Ascii-code of _
        Integer n = 95;
        // go over all columns and rows
        for (L c : l) {
            // f counts the number of consecutive free fields
            int f = 0;
            // move through this column/row
            for (int x = 0; x < a; x++) {
                // Is current field free?
                if (n.equals(c.g(x))) {
                    f++;
                } else {
                    f = 0;
                }
                // Did we encounter enough free fields to place our ship?
                if (f >= s) {
                    // enter ship
                    for (int i = 0; i < s; i++) {
                        c.s(x - i, 35);
                    }
                    // try to place remaining ships
                    if (s()) {
                        return true;
                    }
                    // placing remaining ships has failed ; remove ship
                    for (int i = 0; i < s; i++) {
                        c.s(x - i, n);
                    }
                }
            }
        }
        // we have found no place for our ship so lets push it back
        b.push(s);
        return false;
    }

    /**
     * List representing a single row or column of the field.
     * "Abstract"
     */
    class L {
        /**
         * Index of row/column. Stored here as loop-variables can not be final. Used only {@link #g(int)} and {@link #s(int, int)}
         */
        int i;

        L(int v) {
            i = v;
        }

        /**
         * Set char representing the state at the i-th position in this row/column.
         * "Abstract"
         */
        void s(int i, int v) {
        }

        /**
         * Get char representing the state at the i-th position in this row/column.
         * "Abstract"
         *
         * @return {@code '_'} if this and all adjacent field contain no {@code '#'}
         */
        int g(int i) {
            return 0;
        }

        /**
         * Get char representing the state at the position in c-th column and r-th row
         *
         * @return {@code '_'} if this and all adjacent field contain no {@code '#'}
         */
        int g(int c, int r) {
            // v stores the result
            int v = 0;
            // or all adjacent fields
            for (int x = -1; x < 2; x++) {
                for (int y = -1; y < 2; y++) {
                    // ungolfed we should use something like
                    // v |= 0 > c + x || 0 > r + y || c + x >= a || r + y >= a ? 0 : f[c + x][r + y];
                    // but his will do (and is shorter)
                    try {
                        v |= f[c + x][r + y];
                    } catch (Exception e) {
                    }
                }
            }
            // we use '_' (95), 'O' (79), '#' (35). Only 35 contains the 32-bit
            // So we only need the 32-bit of the or-ed-value + the bits of the value directly in this field
            return v & (f[c][r] | 32);
        }

    }
}

Sample-Input

6 ; 3 2 1 ; A1 A3 B2 C3 D4 E5 F6 B6 E3 D3 F4

Sample-Output

O###_#
_O____
O_OOO#
#_#O_O
#_#_O#
_O___O

With

O missed shot
# ship-part
_ shoot here next ;-)

See on ideone.com
Input-handling expects the spaces around numbers / ; and won't work otherwise.
I am placing big ships first as they have fewer places to go. If you want to switch to small-first you can replace pop() by remove(0) and push(s) by add(0,s) even replacing only one of the two should still result in a valid program.
If you allow ships touching each other the g(int,int) function can be vastly simplified or removed.

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

authors: เด็กวัด สายโหด


text:
Every 2^n times
Let n be the number of times your program has been executed. If n is a power of 2, then print 2^x where n = 2^x; otherwise, simply output the number. Example run:
[1st time] 2^0
[2nd time] 2^1
[3rd time] 3
[4th time] 2^2
[5th time] 5

and so on. This is a popularity contest, so the answer with the most upvotes wins..

why does it output 0 in the first run?

did you mean "where n = 2^x? Otherwise the second time the output would be 2^4, the fourth time 2^16 and so on.

@mniip both typos. I probably should've read that more carefully... :P

Umm... 1 is a power of two. 2^0=1

@JanDvorak Uggh, you're right.

You still say x = 2^x rather  than n = 2^x

Is there any rule about how we count the number of times we've been run? I've just posted an answer that uses an external data file, but as I was finishing it it occurred to me that you might have wanted us to be modifying our own source code instead (which would only be a little bit harder).

@Blckknght I thought about doing that, but people will up vote the more creative one more.

Java - API Abuse
There are plenty of computers online that can count, so why store the count myself?
Full-on abuse of the Stack API to get quota and remaining quota to see how many times it's been run today:
public static void main(String[] args) throws Exception {
    URLConnection c = new URL("http://api.stackexchange.com/2.2/info?site=stackoverflow").openConnection();
    c.setRequestProperty("Accept-Encoding", "gzip");
    GZIPInputStream gz = new GZIPInputStream(c.getInputStream());
    BufferedReader r = new BufferedReader(new InputStreamReader(gz));
    String reply = r.readLine();
    r.close();

    reply = reply.substring(reply.indexOf("quota_max"), reply.length()-1);
    String[] t = reply.split("[:,]");
    int runs = Integer.parseInt(t[1]) - Integer.parseInt(t[3]);
    if((runs & (runs -1)) == 0){
        int exp = 0;
        while(runs % 2 == 0){
            runs = runs >> 1;
            exp++;
        }
        System.out.println("2^" + exp);
    } else {
        System.out.println("" + runs);
    }
}

Obviously this only works with a fresh daily quota for your IP, and only up to the quota. If you want support for higher numbers, post a [feature-request] to raise quota_max to MAX_INT.

JavaScript
alert((n=Math.log((l=localStorage).m=~~l.m+1)/Math.log(2))==(n|0)?"2^"+n:l.m)
Successive alerts are as follows:
2^0
2^1
3
2^2
5
6
7
2^3
9
...and so on.

Thank you kindly... 'Twas the only way to keep track of executions in JavaScript... I'm considering using localStorage for an upcoming JS game...

For something as small as a counter, a cookie should work as well.

@celtschk Great idea, but I believe making a cookie would have taken more bytes

C – writing to the executable
This C code updates the string data in the executable, so essentially this is self-modifying code. If you run it over 9,999,999 times, you get interesting stuff.
#include <stdio.h>
#include <stdlib.h>

int main(int argc,char **argv){
    //               'abcdefghijklmnopqrstuvwxyz1' << that's 27 characters inside the quotes
    const char *data="Da best marker in da world 1\0\0\0\0\0\0";
    FILE *f;
    int i,n,m;
    char c;
    long int pos;
    m=n=strtol(data+27,NULL,10);
    i=0;
    while(1){
        if(n==0){
            printf("This code should never have been reached... Unless you've messed with my executable.\n");
            return 1;
        }
        if(n==1){
            printf("2^%d\n",i);
            break;
        }
        if(n&1){
            printf("%d\n",m);
            break;
        }
        i++;
        n>>=1;
    }
    f=fopen(argv[0],"r+b");
    i=0;
    c=fgetc(f);
    while(!feof(f)){
        if(data[i]==c){
            i++;
            if(i==27)break;
        } else i=0;
        c=fgetc(f);
    }
    if(i!=27)return 1;
    n=0;
    pos=ftell(f);
    c=fgetc(f);
    while(c!='\0'){
        n=10*n+c-'0';
        c=fgetc(f);
    }
    n++; //The big increment!
    fseek(f,pos,SEEK_SET);
    fprintf(f,"%d",n);
    fflush(f);
    fclose(f);
    return 0;
}

It Segmentation faults after compiling it with GCC 4.8.1-10ubuntu9: gcc test.c, ./a.out 2^0 Segmentation fault (core dumped)

On Mac it works, haven't tried Linux or Windoze. Apparently Linux is more strict with accessing yourself.

Java
The following code modifies it's own class file to store the new run count. This was especially fun when you had no idea how the byte code looks, but after countless hours of Googling and Testing it finally works! :)
Demo (using 7 as starting value for demo purposes):
[timwolla@/data/workspace/java]javac Runs.java
[timwolla@/data/workspace/java]java Runs
7
[timwolla@/data/workspace/java]java Runs
2^3
[timwolla@/data/workspace/java]java Runs
9
[timwolla@/data/workspace/java]java Runs
10

Code:
import java.io.*;
import java.util.*;

class Runs {

    public static void main(String[] args) throws Exception {
        // RUN-- makes the string easy to find in the byte code
        String runString = "RUN--1";

        // extract the number
        int runs = Integer.parseInt(runString.substring(5));

        // output the number properly
        int power = 0;
        boolean outputted = false;
        while (Math.pow(2, power) <= runs) {
            if (Math.pow(2, power) == runs) {
                outputted = true;
                System.out.println("2^"+power);
            }
            power++;
        }
        if (!outputted) System.out.println(runs);

        // increase run count
        runs++;

        // build new string
        String newRunString = runString.substring(0, 5) + runs;

        // get folder of class file
        String folder = Runs.class.getProtectionDomain().getCodeSource().getLocation().getFile();
        // append class file name
        String me = folder + "/Runs.class";

        // and open it up
        RandomAccessFile in = new RandomAccessFile(me, "rw");

        int read;
        int state = 0;
        while ((read = in.read()) != -1) {
            char c = (char) read;

            // state machine to find the RUN--
            switch (state) {
                case 0:
                    // 2 bytes before: upper byte of the two byte length
                    if (c == ((runString.length() >> 8) & 0xFF)) state++;
                break;
                case 1:
                    // 1 byte before: lower byte of the two byte length
                    if (c == (runString.length() & 0xFF)) state++;
                    else state = 0;
                break;
                case 2:
                    if (c == 'R') state++;
                    else state = 0;
                break;
                case 3:
                    if (c == 'U') state++;
                    else state = 0;
                break;
                case 4:
                    if (c == 'N') state++;
                    else state = 0;
                break;
                case 5:
                case 6:
                    if (c == '-') state++;
                    else state = 0;
                break;
                case 7:
                    // we found run, now: Modify byte code

                    // back to the bytes that determine the length
                    in.seek(in.getFilePointer() - 8);

                    // expand the file if neccessary
                    int lengthChange = (newRunString.length() - runString.length());
                    in.setLength(in.length() + lengthChange);

                    // write new length
                    in.writeByte(((newRunString.length() >> 8) & 0xFF));
                    in.writeByte((newRunString.length() & 0xFF));

                    // length changed, shift all the following bytes by one
                    if (lengthChange > 0) {
                        long target = in.getFilePointer();
                        in.seek(in.length() - 1 - lengthChange);
                        while (in.getFilePointer() > target) {
                            in.write(in.read());
                            in.seek(in.getFilePointer() - 3);
                        }
                        in.seek(target);
                    }

                    // write new string
                    in.writeBytes(newRunString);

                    return;
                case 8:
            }
        }
    }
}

perl
Here's a short bit of perl to do it. Where should the data be stored? Why in the program file itself, of course! =)
$b = sprintf '%b', $x=x();
print $b=~/^10*$/ ? "2^".(length($b)-1) : $x, "\n";
open F, "+<", $0;
seek F, -3-length $x, 2;
print F $x+1, " }\n";
sub x { 1 }

Originally I had used the magic DATA file handle like so, but I feel the above is "purer":
$b = sprintf '%b', $x = <DATA>;
print $b =~ /^10*$/ ? "2^".(length($b)-1)."\n" : $x;
open F, "+<", $0;
seek F, -length $x, 2;
print F $x+1, "\n";
__DATA__
1

You can store tell DATA before you read from it, then seek back to that spot.

Sinatra-based Ruby Example
This server-based solution stores a personal counter for each user in a cookie.
Try it at http://every-2-to-the-n-times.herokuapp.com/
require 'sinatra'
require 'sinatra/cookies'

# https://github.com/sinatra/sinatra-contrib/issues/113
set :cookie_options, :domain => nil

get '/' do
   x = cookies[:x].to_i || 1
   cookies[:x] = x + 1

   # power of 2 test from http://grosser.it/2010/03/06/check-if-a-numer-is-a-power-of-2-in-ruby/
   return (x & (x - 1) == 0) ? "2^#{Math.log2(x).to_i}" : x.to_s
end

dg
Here I present you a portable code! At every run a # is added at the end, making a progress bar! Also, you can move the code to another machine and resume from where you were.
import '/math'

with fd = open __file__ 'r' =>
  code = fd.read!
  times = code.count('#') - 2
with fd = open __file__ 'w' =>
  fd.write $ code.rstrip! + '#'
exp = math.log2 times
if exp.is_integer! => print $ '2^{}'.format $ int exp
   otherwise => print times

#

After 18 times:
import '/math'

with fd = open __file__ 'r' =>
  code = fd.read!
  times = code.count('#') - 2
with fd = open __file__ 'w' =>
  fd.write $ code.rstrip! + '#'
exp = math.log2 times
if exp.is_integer! => print $ '2^{}'.format $ int exp
   otherwise => print times

###################

Ahh, thanks for pointing this language out to me. It incorporates what I love about both Python and Haskell.

@Kaya I'm happy you like it! In case you haven't already seen, there's a homepage at https://pyos.github.io/dg and a tutorial as well! Lots of goods. And don't hesitate to open an issue on the repository if you feel like so. EDIT: I just wanted to point out that I am not the creator of the lang.

Bash
Simple self-editing shell script.
n=1;e=0;p=1
sed -i s/"n=$n"/"n=`expr $n + 1`"/g $0
if [[ $n -eq $p ]];then
    echo 2^$e
    sed -i s/"p=$p"/"p=`expr $p \* 2`"/g $0
    sed -i s/"e=$e"/"e=`expr $e + 1`"/g $0
else
    echo $n
fi

Bash
I like dfernig's Bash solution, but I would like to post mine as well:
n=$(expr `cat $0|wc -c` - 170)
if [ $(echo "obase=2;$n"|bc|grep -o 1|wc -l) == 1 ]
then echo -n "2^"; echo "obase=2;$n"|bc|grep -o 0|wc -l;
else echo $n; fi
echo "" >> $0

I think the solution can be considered different, because

the code actually executed doesn't change
the program dinamically calculates if n is a power of 2

The "memory" is the script size (initially 171 bytes), which is increased by 1 with the append of a newline at each execution.
Powers of 2 are recognized by converting the program size (minus 170, of course) to binary, and then counting the ones: if there is exactly one one, then n is a power of 2. The exponent is the number of zeros in binary.

Javascript
I chose to not use the obvious log2 solution but work with bitwise operators to find the single bit position in the binary representation of power of 2 numbers.
Number.prototype.singleBitPosition = function() {
  var r=1, k;
  if (this==0) return -1;
  while(this==(k=this>>r<<r)) r++; //set r last bits to zero and compare
  return k?-1:r; //if k is zero, there is one single bit to 1 in number representation ie power of 2
};

var n;
if (n === undefined) n=0;
n++;

var e = n.singleBitPosition();
if (e > 0) {
  console.log('2^'+(e-1));
} else {
  console.log(n);
}

great strategy, but unfortunately, the brief states that it needs to display the value of the number of times it has been executed, rendered accordingly... Yours is just a for loop from 1 to 130, with the rendering... :/

@WallyWest, yeah, thanks for pointing this out.

No offence intended...

I had not taken your comment as an offense, that was a real thanks ! Sorry if my words are not well chosen, english is not my mother tongue.

Java solution
Uing the java preferences API to store the run amount; and precalculated the powers of 2 for a hashmap to compare
import java.util.HashMap;
import java.util.prefs.Preferences;
class Pow
{
    public static void main(String[]a)
    {
        int rt = Integer.valueOf(Preferences.userRoot().get("Pow.run", "1"));
        HashMap<String,Integer> powof2 = new HashMap<>();
        //pregenerating the powers of 2;
        for (int i = 0; i < 46340; i++)//highest power of 2 before int overflow
        {
            powof2.put(((int)Math.pow(2, i))+"",i);
        }
        if(powof2.containsKey(rt+""))
        {System.out.println("2^"+powof2.get(rt+""));}
        else
        {
            System.out.println(rt);
        }
        rt++;
        Preferences.userRoot().put("Pow.run", ""+(rt));
    }
}

Fortran 77
Code:
      program twok
      rewind 1
      read(1,'(I20,I3)',end=10,err=30)n,k
      go to 20
10    n=-1
      k=0
20    n=n+1
      if (n .eq. 2**k) then
        if (k.le.9) then
          write(*,'(A3,i1)')' 2^',k
        else
          write(*,'(A3,i2)')' 2^',k
        endif
        k=k+1
      else
        write(*,*)n
      endif
      if (n .lt. 0) then
         n=-1
         k=0
      endif
      rewind 1
      write(1,'(I20,I3)')n,k
30    continue
      end

Result:
$ ./a.out       !       $ ./a.out
 2^0            !        2^1
$ ./a.out       !
 2^1            !       $ while true
$ ./a.out       !       > do
 3              !       > ./a.out | grep "2^"
$ ./a.out       !       > done
 2^2            !        2^2
$ ./a.out       !        2^3
 5              !        2^4
$ ./a.out       !        2^5
 6              !        ...
...             !        2^12
$ ./a.out       !        2^13
 2147483647     !       ^C # (after about 5 minutes)
$ ./a.out       !       $ ./a.out
 2^31           !        14718
$ ./a.out       !       $ ./a.out
 0              !        14719
$ ./a.out       !       $
 2^0            !

This counts the number of runs done within a particular directory.  Possible improvement would be to request a file in the /tmp directory, and to add a semaphore so multiple instances don't try to update the counter at the same time.

Ruby
Alright, I think I'll try this now. It searches itself for the definition of n.
def p2 n
  n == 1 ? 0 : p2(n >> 1) + 1
end
n = 1
if (n != 0) & (n & (n - 1) == 0) || n == 1
  puts("2^" + (p2(n).to_s))
else
  puts n
end

contents = File.read(__FILE__)
newContents = contents.gsub(/(?<=n \= )[0-9]+/) {|n| (n.to_i + 1).to_s}
File.write(__FILE__, newContents)

(tested in Ruby 1.9.3)

C
One of the "proper" ways to do it (without using files, that is).
You can give it reset on the command line to set it back to zero. You can also move or copy the executable around. Moving the executable resets it, and multiple copies of the executable are independent.
#include <stdio.h>
#include <sys/msg.h>
#include <sys/shm.h>

int main(int argc, char **argv) {
   // get a shared memory segment associated with our program
   long key = ftok(argv[0], 1);
   long id = shmget(key, sizeof(long), 0666 | IPC_CREAT);
   long *num = (long*) shmat(id, NULL, 0);

   // reset parameter
   if (argc == 2 && !strcmp(argv[1], "reset")) {
      *num = 0;
   }

   if (*num & *num-1) {
      // not a power of two
      printf("%li\n", *num);
   } else {
      // power of two
      int exp = 0;
      int n=*num;
      while (n >>= 1) exp++;
      printf("2^%d\n", exp);
   }

   ++*num;

   // detach from shared memory
   shmdt(num);
   return 0;
}

Sparkling, 423 characters (yet another self-modifying code). Save it as count.spn then run spn count.spn:
var n =
19
;

var l = log2(n);
if l == floor(l) {
    printf("2 ^ %d\n", floor(l));
} else {
    printf("%.0f\n", n);
}

var f = fopen("count.spn", "rb");
var g = fopen("count.spn.2", "wb");
var line = fgetline(f);
fprintf(g, "%s", line);
fprintf(g, "%d\n", n + 1);
fgetline(f);

while (line = fgetline(f)) != nil {
    fprintf(g, "%s", line);
}

fclose(f);
fclose(g);

Here's a quick Python 3 solution, which uses a data file to store n and x between runs:
try:
    with open("count.txt") as f:
        n, x = map(int, f.readline().split())
except FileNotFoundError:
    n = x = 0

n += 1
if n == 2**x:
    print("2^{}".format(x))
    x += 1
else:
    print(n)

with open("count.txt", "w") as f:
    f.write("{} {}".format(n, x))

The output of running it 16 times:
2^0
2^1
3
2^2
5
6
7
2^3
9
10
11
12
13
14
15
2^4

Python 2
import inspect
import math

file_name = inspect.getfile(inspect.currentframe())

n = int(open(file_name).readlines()[-1].strip())

l = math.log(n, 2)
if int(l) == l:
    print '2^%d' % (l)
else:
    print n

with open(file_name, 'a') as f:
    f.write('%d\n' % (n + 1))

1

C#
static void Main()
{
  ulong cnt         = ++Properties.Settings.Default.NumberOfExecutions ;
  int?  log2        = Log2( cnt ) ;
  Console.WriteLine( log2.HasValue ? "2^{0}" : "{1}" , log2 , cnt ) ;
  Properties.Settings.Default.Save() ;
  return ;
}

static int? Log2( ulong m )
{
  int? n = null ;
  if ( m > 0 )
  {
    n = 0 ;

    // find the first set bit
    ulong mask = 0x0000000000000001ul ;
    while ( mask != 0 && 0ul == (m&mask) )
    {
      mask <<= 1 ;
      ++n ;
    } ;

    // if the mask is identical to m,
    // we've got a power of 2: return n, otherwise null
    n = mask == m ? n : null ;

  }
  return n ;
}

This does, though, require that you define a settings property in your Visual Studio project:

C/POSIX
This program uses the number of hard links to its own executable as counter of how often it was called. It creates the new hard links in the directory it was started from (because that way it's guaranteed to be on the same file system), which therefore needs write permission. I've omitted error handling.
You better make sure that you have no important file with the same name as one of the created hard links on that directory, or it will be overwritten. If e.g. the executable is named counter, the hard links will be named counter_1, counter_2 etc.
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[])
{
  /* get persistent counter */
  struct stat selfstat;
  stat(argv[0], &selfstat);
  int counter = selfstat.st_nlink;

  /* determine digits of counter */
  int countercopy = counter;
  int digits = 1;
  while (countercopy /= 10)
    ++digits;

  /* increment persistent counter */
  char* newname = malloc(strlen(argv[0]) + digits + 2);
  sprintf(newname, "%s_%d", argv[0], counter);
  link(argv[0], newname);

  /* output the counter */
  if (counter & (counter-1)) // this is zero iff counter is a power of two
    printf("%d\n", counter);
  else
  {
    /* determine which power of 2 it is */
    int power = 0;
    while (counter/=2)
      ++power;
    printf("2^%d\n", power);
  }
  return 0;
}

Example run (the first line resets the counter, in case the executable has already been run):
$ rm counter_*
$ ./counter
2^0
$ ./counter
2^1
$ ./counter
3
$ ./counter
2^2
$ ./counter
5
$ ./counter
6
$ ./counter
7
$ ./counter
2^3
$ ./counter
9
$ ls counter*
counter    counter_2  counter_4  counter_6  counter_8  counter.c
counter_1  counter_3  counter_5  counter_7  counter_9  counter.c~

Fortran 95
A file named "a" (without extension) keeps track of the run of the program.
logical::l
inquire(file="a",exist=l)
open(unit=11,file="a")
if (l) then
  read(11,*)n
  close(unit=11,status="delete")
  open(unit=11,file="a")
  n=n+1
  write(11,*)n
  do i=1,n
    if (2**i==n) then
      write(*,"(A2,I1)")"2^",i
      goto 1
    endif
  enddo
  print*,n
  else
    print*,"2^0"
    write(11,*)1
endif
1 end