text:
Unicode character classification
Real-world programs often use libraries like ICU to support Unicode.
The puzzle is to create the smallest possible function that can determine whether a given Unicode character is lowercase, uppercase, or neither (a commonly used Unicode character property).
You may indicate the property in any way (whatever is shortest for your language); just explain what the output means in your answer.
Of course, using a language feature or a function from the standard library that already provides this distinction is forbidden.
This could potentially have some practical use, since some embedded programs have to choose between including a bulky library and not supporting Unicode.

I took the liberty of adding the restriction. And yes, you absolutely should ;-)

@Joey You added that restriction just before I post my answer using Python's unicodedata :P

Character classification changes (albeit in a stable manner) with each release of Unicode. Are you asking for a function that is hard coded to a particular version of Unicode? If so, then this is nothing more than an exercise in data compression, and one where I could choose the release to my advantage.
As specified, the problem isn't actually practical, as your classification options are not a useful subset of the Unicode classifications, even for simple text processing. (There are many letters that are neither lowercase or uppercase, for example.)

In response to @MtnViewMark's comment, should we assume Unicode 6.0?

Also, where can the database of character classifications be found?

@Joey (and his upvoter): http://www.unicode.org/Public/UNIDATA/UnicodeData.txt – the usual place, basically.

MtnViewMark: Character classes are final for already-encoded characters, so nothing changes there, except characters are added. Also, how many uper- and lowercase characters have been added recently, especially in the BMP? I currently can only think of uppercase sharp s and the math alphabets (which are in the SMP, anyway). Agreed that it's only data compression, but for reasonably current versions of Unicode the number of upper- and lowercase characters is fairly stable.

Voting to close as unclear. Challenges should be self-contained, so the list or qualifications for each output should be made clear. If linked as an external file, the file should be a file that will not change over time.

C & C++, 1922 1216 bytes/chars (BMP only 1451 1005 bytes/chars)
This is the "shortest" solution that came to mind that is both valid C and C++ and that supports all of Unicode version 6.1, not just the BMP:
int s[]={-74,-68,31054,-50,-49,-48,-47,-46,-44,-43,-39,-38,-37,-34,-33,-32,-30,-29,-28,-27,-26,-25,-24,-23,-22,-17,-16,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,19,20,27,28,29,53195,31,34,36,42,49,50,52,54,58,59,62,64,66,73,81,98,102,103,140,194,263,275,290,1066,1222,1230,2685,2732,2890,3379,6009,21254,22391,30996,53209};
char l[]="l5Hf`7HIAH2IH@IH7IJFIFHJIJKHLJKFHFJFIJIHIJKIJHJFHNFJ@IH?IHJIK1IBHFJHILDI!HI4HpIFKFHWZ-HIHKFH<IDHIFJHc&H9IQ4IJBIH(Ie+H{)Hh<HI.Hn I@H$I@HPCHRAHPAHPCHRAHPAHP;HJAHPAHPAHPDHIHNKFHIHPEHJHPAHRFHIHrKHKZFLJHPEHLdx'HJKHEILIHICHM$IHOILT,HIM~8IX=IoBIFH/IAHFIJDILIJIUDIk|BHTDHt5Hv*H\\5HYBHI9HY5HYEHFIBHI>HY5HY5HY5HY5HY5HY5HY5HY5HY3H[6HICHY6HICHY6HICHY6HICHY6HICHIG";
char u[]="i5Hm8HIBH^3IJAIJ7IHFIKHFIHIFHJEHIHIFHKHIHEIHIJIHIFHFIHKOEJAIJ@IFJIFH1IOHIHJIEHDIsIKVIFHFIHI:HI@H_JFHK=IMJIHJ#Ha:IQ3IHBIJ)IR,Hy,HIMz IQ%IQAHPCHRAHPAHPCHSEIPAHjEHTEHTEHTDHSEHqLKFHJFHJKDHNEIEHJEHRHMgw'HbIFHJEIEHIJPFH$IPIL\"8IX=IoBIK0IRFIHDILIJIUCI}5Hu*H\1775HY5HY5HYIHFJHJEHIAHY5HYHIEHJAHIBHZHIEHIDHIKBHZ5HY5HY5HY5HY5HY5H]6H^6H^6H^6H^6H^G";
int x(int a,char*p){int c=0,i=0,b=-1;while(c>0||s[*p-32]){if(!c)c=s[*p-32]<0?-s[*p++-32]:1,i=s[*p++-32];b+=i,--c;if(a==b)return 1;}return 0;}

Please note that "shortest" in this case does not mean that the solution is in any way efficient; it simply means that it is the shortest source code solution. It does not require any Unicode support in the standard library, and in fact does not use the standard library at all. (Which I now understand is what code golf means ... I'm a newbie around here, what can I say.)
To build the lower and upper case data tables I worked as follows:

Downloaded UnicodeData.txt.
Extracted a list of all lines that included the text ";Ll;" or ";Lu;" to indicate a lower case letter or upper case letter respectively.
Built two vectors of code points using the data from step 2.
Converted each absolute code point value to a relative value, the difference between the previous code point and this code point. Because it is convenient for the difference to always be a positive integer (not zero or negative), I use -1 as the value of the first previous code point. In this way zero will not appear anywhere in the sequence.
Used a form of run length encoding to compress runs of identical values into a pair of values. If the next value appears two or more times consecutively, replace the sequence with the negative of the length of the sequence and the value. Otherwise the value only appears once, so just use it as is.
Terminated the compressed vector with zero to mark the end of the sequence.
I noticed there were 96 unique values in the run length encoded vectors, so I built an array of the unique integers and used the index into that array for the lower and upper case vectors.

The above process compressed the vector of lower case code points from 1751 unique values to 350 mostly small non-unique values. In like fashion, the upper case code point vector went from 1441 values to 331 values.
Next I wrote the unique value vector out as a comma separated list of integers suitable for including in source code. I assumed int was 32 bits to avoid using long so that I could save an additional four characters / bytes of source code. Then I wrote out the lower and upper case vectors as strings, where each character in the string has a code 32 greater than its index into the unique integer array. This saves about half the characters necessary to encode the lower & upper case array through omission of comma characters. Three of the characters used have to be escaped (\", \, and \177). They are assigned to unique integers that only appear once in the data so as to minimize the size of the string literals.
What I wound up with was a global array of integers, two global arrays of characters, and a function. An array named s for the unique signed integers, an array named u for the character based upper case code point indexes, and another array named l for the character based lower case code point indexes. The function x takes code point a and pointer to an array of characters p and returns 1 if the code point is in the decompressed / normalized array of code points or 0 otherwise.
If you want to determine if code point cp is lower case, you call "x(cp, l)". If you want to determine if it is upper case, you call "x(cp, u)".
Since the point to this exercise is to make the smallest code to accomplish the task, I never save the decompressed / normalized data. I decompress it piecemeal as I need it every time I call it.
It would be possible to terminate the while loop early if the code point I'm checking has already been passed by during decompression. That would add extra code so I didn't bother, deciding I'd rather pay the speed penalty.
I admit the code is ugly. I did not write it this way originally. Here is the C++ version that I derived the compact C version from:
const int Ii[] = {-74,-68,31054,-50,-49,-48,-47,-46,-44,-43,-39,-38,-37,-34,-33,-32,-30,-29,-28,-27,-26,-25,-24,-23,-22,-17,-16,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,19,20,27,28,29,53195,31,34,36,42,49,50,52,54,58,59,62,64,66,73,81,98,102,103,140,194,263,275,290,1066,1222,1230,2685,2732,2890,3379,6009,21254,22391,30996,53209};
const char Ll[] = "l5Hf`7HIAH2IH@IH7IJFIFHJIJKHLJKFHFJFIJIHIJKIJHJFHNFJ@IH?IHJIK1IBHFJHILDI!HI4HpIFKFHWZ-HIHKFH<IDHIFJHc&H9IQ4IJBIH(Ie+H{)Hh<HI.Hn I@H$I@HPCHRAHPAHPCHRAHPAHP;HJAHPAHPAHPDHIHNKFHIHPEHJHPAHRFHIHrKHKZFLJHPEHLdx'HJKHEILIHICHM$IHOILT,HIM~8IX=IoBIFH/IAHFIJDILIJIUDIk|BHTDHt5Hv*H\\5HYBHI9HY5HYEHFIBHI>HY5HY5HY5HY5HY5HY5HY5HY5HY3H[6HICHY6HICHY6HICHY6HICHY6HICHIG";
const char Lu[] = "i5Hm8HIBH^3IJAIJ7IHFIKHFIHIFHJEHIHIFHKHIHEIHIJIHIFHFIHKOEJAIJ@IFJIFH1IOHIHJIEHDIsIKVIFHFIHI:HI@H_JFHK=IMJIHJ#Ha:IQ3IHBIJ)IR,Hy,HIMz IQ%IQAHPCHRAHPAHPCHSEIPAHjEHTEHTEHTDHSEHqLKFHJFHJKDHNEIEHJEHRHMgw'HbIFHJEIEHIJPFH$IPIL\"8IX=IoBIK0IRFIHDILIJIUCI}5Hu*H\1775HY5HY5HYIHFJHJEHIAHY5HYHIEHJAHIBHZHIEHIDHIKBHZ5HY5HY5HY5HY5HY5H]6H^6H^6H^6H^6H^G";

bool isXx(int cp, const char* Xx)
{
    int count = 0, step = 0, code = -1;

    while ((count > 0) || (Ii[*Xx-32] != 0))
    {
        if (count == 0)
        {
            count = (Ii[*Xx-32] < 0) ? -(Ii[*(Xx++)-32]) : 1;
            step = Ii[*(Xx++)-32];
        }

        code += step;
        --count;

        if (cp < code)
            break;

        if (cp == code)
            return true;
    }

    return false;
}

inline bool isLl(int cp)
{
    return isXx(cp, Ll);
}

inline bool isLu(int cp)
{
    return isXx(cp, Lu);
}

In the end, the compact version takes 1922 1216 bytes (including CR+LF end of line sequences). The original version only takes 2271 1578 bytes.
To put this in context of the other solutions that only support the BMP, the equivalent compact version only takes 1451 1005 bytes (or 1800 1367 bytes for the original version).

I'm accepting this one even though it's a bit longer, because it supports astral-plane characters, does something clever, and explains how it was created. Also, it's probably possible to shorten the arrays by encoding them into character strings in some way.

Thanks. I considered encoding them in some other way, but the obvious solutions would have involved more code to decode, and I intuited that the overhead wouldn't make enough of a difference (though I didn't try so I could be wrong).

@Mechanicalsnail So after a few hours of not thinking about it, I came up with a new encoding using character strings that involves little over head and shrinks the size of the compact solution from 1922 bytes/chars to 1216 bytes/chars. So two things: 1, you were correct, and 2, since I'm a relative newbie to the codegolf.stackexchange site, what's the best way to share it? Should I replace the original above, or append it to the end of this accepted answer, or post yet another answer?

I would probably replace the existing answer. Also keep an old version when it contains something interesting or if they help understand how the solution works; if the new version is better in all respects then just delete the old one. I would add a second answer if my new solution is completely different (e.g. works by a different method, is written in a different language, etc.).

PowerShell, 2101
filter x{if(97..122+170,181,186+223..246+248..255+311..312+(0..26|%{$_*2+257})+
328..329+(0..6|%{$_*2+314})+(0..22|%{$_*2+331})+382..384+378,380,387,389+
396..397+392,402+409..411+405,414,417,419,421,426,427,424,429,432,441,442+
445..447+436,438,454,457,476,477+(0..7|%{$_*2+460})+495,496+(0..7|%{$_*2+479})+
499,501+563..569+(0..28|%{$_*2+505})+575,576,572,578+591..659+661..687+
891..893+(0..3|%{$_*2+583})+940..974+976,977,912+981..983+1007..1011+
(0..10|%{$_*2+985})+1013,1016,1019,1020+1072..1119+(0..16|%{$_*2+1121})+
(0..26|%{$_*2+1163})+1230,1231+(0..5|%{$_*2+1218})+1377..1415+7424..7467+
7522..7578+(0..33|%{$_*2+1233})+7829..7835+(0..73|%{$_*2+7681})+7936..7943+
7952..7957+7968..7975+7984..7991+8000..8005+8016..8023+8032..8039+
8048..8061+8064..8071+8080..8087+8096..8103+8112..8116+8118,8119+
(0..44|%{$_*2+7841})+8130..8135+8144..8147+8150..8151+8160..8167+8178..8180+
8182,8183,8126,8305,8319+8462..8463+8458,8467,8495,8500,8508,8509+8518..8521+
8505,8526,8580+11312..11358+11365,11366,11361,11368,11370,11372,11382,11383,
11380+11491,11492+11520..11557+64256..64262+64275..64279+65345..65370+
(0..48|%{$_*2+11393})-ne7544-ne8133-eq$_){1}elseif(65..90+192..214+216..222+
(0..27|%{$_*2+256})+(0..7|%{$_*2+313})+376,377+(0..22|%{$_*2+330})+385..386+
379,381+390..395+398..408+412..416+388,422,423,418,420,425,428+430..435+439,
440,437,444,452,455,458,497,500+(0..7|%{$_*2+461})+(0..8|%{$_*2+478})+
502..504+570..574+(0..28|%{$_*2+506})+579..582+577,584,586,588,590,902,908+
904..906+910..939+978..980+(0..11|%{$_*2+984})+1012,1015,1017,1018+1021..1071+
(0..16|%{$_*2+1120})+1216,1217+(0..26|%{$_*2+1162})+(0..5|%{$_*2+1219})+
1329..1366+4256..4293+(0..33|%{$_*2+1232})+(0..74|%{$_*2+7680})+7944..7951+
7960..7965+7976..7983+7992..7999+8008..8013+(0..44|%{$_*2+7840})+8040..8047+
8120..8123+8136..8139+8152..8155+8168..8172+8184..8187+(0..3|%{$_*2+8025})+
8450,8455,8469+8459..8461+8464..8466+8473..8477+8490..8493+8496..8499+8510,
8511,8484,8486,8488,8517+11264..11310+8579,11360+11362..11364+11367,11369,
11371,11381+65313..65338+(0..49|%{$_*2+11392})-notmatch'^(392|40[25]|414|432|572|912|930)$'-eq$_){2}else{0}}

Notes:

Returns 1 for lower-case, 2 for upper-case and 0 for neither.
Works only for BMP code points (as the char type in .NET represents a single UTF-16 code unit).

This uses a few distinct ways of compressing the code points for the two sets:

adjacent code points are conflated in a range (97..122)
code points that are two apart are conflated in a small pipeline (0..22|%{$_*2+331})
Ranges with only one missing value are done via 7522..7578-ne7544, effectively removing that single element. This may not be done with all such rages by now.

I did the first two steps automatically, the third one and minor optimizations (0..1|%{2*$_+11370} is useless) were done by hand.
Some tests:
PS> [char]'a'|x
1
PS> [char]'A'|x
2
PS> [char]'1'|x
0
PS> [char]'α'|x
1
PS> [char]'Д'|x
2

Python 3, 1369 chars (not bytes)
a='abcdefghijklmnopqrstuvwxyzªµºßàáâãäåæçèéêëìíîïðñòóôõöøùúûüýþÿāăąćĉċčďđēĕėęěĝğġģĥħĩīĭįıĳĵķĸĺļľŀłńņňŉŋōŏőœŕŗřśŝşšţťŧũūŭůűųŵŷźżžſƀƃƅƈƌƍƒƕƙƚƛƞơƣƥƨƪƫƭưƴƶƹƺƽƾƿǆǉǌǎǐǒǔǖǘǚǜǝǟǡǣǥǧǩǫǭǯǰǳǵǹǻǽǿȁȃȅȇȉȋȍȏȑȓȕȗșțȝȟȡȣȥȧȩȫȭȯȱȳȴȵȶȷȸȹȼȿɀɂɇɉɋɍɏɐɑɒɓɔɕɖɗɘəɚɛɜɝɞɟɠɡɢɣɤɥɦɧɨɩɪɫɬɭɮɯɰɱɲɳɴɵɶɷɸɹɺɻɼɽɾɿʀʁʂʃʄʅʆʇʈʉʊʋʌʍʎʏʐʑʒʓʕʖʗʘʙʚʛʜʝʞʟʠʡʢʣʤʥʦʧʨʩʪʫʬʭʮʯͱͳͷͻͼͽΐάέήίΰαβγδεζηθικλμνξοπρςστυφχψωϊϋόύώϐϑϕϖϗϙϛϝϟϡϣϥϧϩϫϭϯϰϱϲϳϵϸϻϼабвгдежзийклмнопрстуфхцчшщъыьэюяѐёђѓєѕіїјљњћќѝўџѡѣѥѧѩѫѭѯѱѳѵѷѹѻѽѿҁҋҍҏґғҕҗҙқҝҟҡңҥҧҩҫҭүұҳҵҷҹһҽҿӂӄӆӈӊӌӎӏӑӓӕӗәӛӝӟӡӣӥӧөӫӭӯӱӳӵӷӹӻӽӿԁԃԅԇԉԋԍԏԑԓԕԗԙԛԝԟԡԣԥԧաբգդեզէըթժիլխծկհձղճմյնշոչպջռսվտրցւփքօֆևᴀᴁᴂᴃᴄᴅᴆᴇᴈᴉᴊᴋᴌᴍᴎᴏᴐᴑᴒᴓᴔᴕᴖᴗᴘᴙᴚᴛᴜᴝᴞᴟᴠᴡᴢᴣᴤᴥᴦᴧᴨᴩᴪᴫᵢᵣᵤᵥᵦᵧᵨᵩᵪᵫᵬᵭᵮᵯᵰᵱᵲᵳᵴᵵᵶᵷᵹᵺᵻᵼᵽᵾᵿᶀᶁᶂᶃᶄᶅᶆᶇᶈᶉᶊᶋᶌᶍᶎᶏᶐᶑᶒᶓᶔᶕᶖᶗᶘᶙᶚḁḃḅḇḉḋḍḏḑḓḕḗḙḛḝḟḡḣḥḧḩḫḭḯḱḳḵḷḹḻḽḿṁṃṅṇṉṋṍṏṑṓṕṗṙṛṝṟṡṣṥṧṩṫṭṯṱṳṵṷṹṻṽṿẁẃẅẇẉẋẍẏẑẓẕẖẗẘẙẚẛẜẝẟạảấầẩẫậắằẳẵặẹẻẽếềểễệỉịọỏốồổỗộớờởỡợụủứừửữựỳỵỷỹỻỽỿἀἁἂἃἄἅἆἇἐἑἒἓἔἕἠἡἢἣἤἥἦἧἰἱἲἳἴἵἶἷὀὁὂὃὄὅὐὑὒὓὔὕὖὗὠὡὢὣὤὥὦὧὰάὲέὴήὶίὸόὺύὼώᾀᾁᾂᾃᾄᾅᾆᾇᾐᾑᾒᾓᾔᾕᾖᾗᾠᾡᾢᾣᾤᾥᾦᾧᾰᾱᾲᾳᾴᾶᾷιῂῃῄῆῇῐῑῒΐῖῗῠῡῢΰῤῥῦῧῲῳῴῶῷℊℎℏℓℯℴℹℼℽⅆⅇⅈⅉⅎↄⰰⰱⰲⰳⰴⰵⰶⰷⰸⰹⰺⰻⰼⰽⰾⰿⱀⱁⱂⱃⱄⱅⱆⱇⱈⱉⱊⱋⱌⱍⱎⱏⱐⱑⱒⱓⱔⱕⱖⱗⱘⱙⱚⱛⱜⱝⱞⱡⱥⱦⱨⱪⱬⱱⱳⱴⱶⱷⱸⱹⱺⱻⱼⲁⲃⲅⲇⲉⲋⲍⲏⲑⲓⲕⲗⲙⲛⲝⲟⲡⲣⲥⲧⲩⲫⲭⲯⲱⲳⲵⲷⲹⲻⲽⲿⳁⳃⳅⳇⳉⳋⳍⳏⳑⳓⳕⳗⳙⳛⳝⳟⳡⳣⳤⳬⳮⴀⴁⴂⴃⴄⴅⴆⴇⴈⴉⴊⴋⴌⴍⴎⴏⴐⴑⴒⴓⴔⴕⴖⴗⴘⴙⴚⴛⴜⴝⴞⴟⴠⴡⴢⴣⴤⴥꙁꙃꙅꙇꙉꙋꙍꙏꙑꙓꙕꙗꙙꙛꙝꙟꙡꙣꙥꙧꙩꙫꙭꚁꚃꚅꚇꚉꚋꚍꚏꚑꚓꚕꚗꜣꜥꜧꜩꜫꜭꜯꜰꜱꜳꜵꜷꜹꜻꜽꜿꝁꝃꝅꝇꝉꝋꝍꝏꝑꝓꝕꝗꝙꝛꝝꝟꝡꝣꝥꝧꝩꝫꝭꝯꝱꝲꝳꝴꝵꝶꝷꝸꝺꝼꝿꞁꞃꞅꞇꞌꞎꞑꞡꞣꞥꞧꞩꟺﬀﬁﬂﬃﬄﬅﬆﬓﬔﬕﬖﬗａｂｃｄｅｆｇｈｉｊｋｌｍｎｏｐｑｒｓｔｕｖｗｘｙｚ'
def f(x):
 if x in a:
  return 'lowercase'
 if x in a.upper()+'ℂℇℋℍİℑℐℒℕℙℛℚℝℜẞℤΩℨÅKℭℬℱℰℳℿℾⅅℌϓϒϔϴ':
  return 'uppercase'
 return 'neither'

Almost as small as the other answer (uses the same approach but using literals instead of numbers) but no effort at all.
Your browser may not render the chars properly and it is UTF-8
Edit:
Making uppercase characters and adding those which didn't correspond to any lowercase saved a ton of chars

Technically that's reusing embedded Unicode information, though, thus approximately on par with directly querying character information.

@Joye on many languages 'a' == 97. So what's the difference of comparing a char to a number or to another char?

I meant the upper() part which is relying on Python knowing how to uppercase arbitrary Unicode characters, thereby not embedding the mapping itself.

Python 2: 811 characters (after minification)
def D(s):
    k = 0
    for i in map(ord, s.decode('base64').decode('utf8')):
        for j in range(i // 2):
            yield k
            k ^= i % 2
        k ^= 1 - i % 2
U = list(D('woI0w4ouAw5CbwQfBF0ECQYEBwQDBgQIAwQDBgYEAwQLBAUEBQQDBgcEBgMOAwQDBAMEHwQjBAMEBQZ1DgQDBAQFCBHJggcGAx4FBgcEAyIDEkYDBAYGLwoDBAUEBGZgQxJtBBkEwqccTOGakkzhqbTEqxLDgxIQEAwUEBAQEAwWDxAQwpAIGAgYCBgKFgjIjAMIAwYGBAYEAwYKDA0IBAgUBAoDegPhk7heYgUGBA0GBAMEAxTDh++Kuj8GFyYvxJYbBnsUCQQRCAPqvKo0xoo='))
L = list(D('w4I0XgMUAwgDSDADEG8EHwRdBAkGBAcEAwYECAMEAwYGBAMECwQFBAUEAwYHBAQEBgwDBAMEIQQjBAQHBnUOBAMEBAUIEcKKAzbGggcGAwYGJAM2RgMEBgYvCgUEAwQEZmBFEmsEGQTCqXpO4ruwWGwsA0TDjMSpEsODEhAMFBAQEBAMFBAQEBAcBBAQEBAQEAoDBAwDBgYDBBAIBAQQEBQGAwTDsgMaA8SUAwYEBgM2AwgDCAMEBBAICANqA+GVll4EAwYEDQgFBAMOCMOFBDZM74i2PwYXJi/ElhkGfxAJBBMIA+qbpg4YCuChkjTFig=='))
f = lambda x: U[x] and 'upper' or L[x] and 'lower' or 'neither'

This supports the base multi-lingual plane only (as for the other answers). You could make it a bit shorter by omitting the encoding/decoding steps (and just putting Unicode strings into the program source), but then I think you really ought to count the length in bytes rather than characters.

Why do you only count non-whitespace characters?

Because removal of whitespace is essentially a mechanical operation. In most cases it just makes the code harder to read, without adding anything of value. When analyzing the code, of course the first thing you would do is to restore the whitespace to make it readable. So I prefer to take this step for granted, in order to focus on the more interesting and creative aspects of the challenge.

So there is no necessary whitespace in there. Plenty of languages have that and then not counting characters you need for the program to work is a bit cheating.

Would it be better if I gave the length after minification instead, like this?

That's better, I guess. Usually rules like "Don't count whitespace" are given in the task specification here and when they're absent everyone should count the same.

My opinion is that the minification step is usually uninteresting (because mechanical) and the answers would be much more interesting to read if it were usually omitted. (In a few cases, of course, something interesting can be done here, as with this Obfuscated C Contest entry.)


text:
Proving the shortest quine in a particular language

Possible Duplicate:
Golf you a quine for great good!

People have proposed short quines in various languages.
Puzzle: Find the shortest non-trivial quine in a language of your choice, and prove that it is the shortest. ("Trivial" quines are such things as the empty program, and text that will be echoed directly.)
I expect the solution will involve exhaustive search of all possible programs of length up to the length of the shortest known quine. Some cleverness is probably needed to reduce the search space to a tractable size, and filter out programs that are quines for trivial reasons.

Is an empty program on a script language a valid quine? Quines are quite boring things... BTW, I know the answer for HQ9+

@JBernardo: That would count as trivial, as specified in the question.

This isn't an exact duplicate: this question also asks for a proof that it's the shortest quine in its language.

@Joey Adams: The proof was intended as the main part of the puzzle.

If the language is Turing Complete, then the halting problem happens

source: Stack Exchange

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

sort: votes


text:
Knuth's Power Tree
In The Art of Computer Programming, Knuth describes an algorithm to compute short addition chains.  The algorithm works by computing a tree known as the Power Tree.  The tree is rooted at 1, and each level is computed from the previous.  Suppose we've computed level k.  Then, for each node (n) in level k, and each ancestor (or self) a = 1, 2, ..., n of n, add the node n+a to level k+1 if it is not already in the tree; the parent of n+a is n.
Three important things to note:

nodes should be visited in the order that they are created
levels are to be computed one at a time (not recursively)
traverse the ancestors from smallest to largest (or you end up a familiar, but less optimal tree)

A picture of the tree
Perhaps drawing this tree would be fun to golf?  Hmm.  At the least, the result would probably be a better-drawn tree. FWIW, 10 has 4 children.
             1
             |
             2
            / \
           3   4
          /\    \
         /  \    \
        5    6    8
       / \    \\   \
      /  |     \\   \
     /   |      \\   \
    7    10     9 12  16
   /   / /\ \    \ \   \\
  /   / /  \ \    \ \   \\
14  11 13  15 20  18 24 17 32

Naive Python Implementation
Since my verbose description of the tree seems to be lacking, here's a naive Python implementation.  I store the tree as a dictionary here, parent(x) := tree[x].  There's lots of fun optimization to be had here.
def chain(tree,x):
    c = [x]
    while x!=1:
        x=tree[x]
        c.append(x)
    return c[::-1]

tree = {1:None}
leaves = [1]
levels = 5
for _ in range(levels):
    newleaves = []
    for m in leaves:
        for i in chain(tree,m):
            if i+m not in tree:
                tree[i+m] = m
                newleaves.append(i+m)
    leaves = newleaves

Requirements
Your program should take one argument n, compute the complete tree with all integer nodes i with 0 <= i <= n, and then take input from the user.  For each input, print out the path from the root to that input.  If an input isn't an integer between 0 and n (inclusive), behavior is undefined.  Terminate if the user inputs zero.
Example Session
./yourprogram 1000
?1000
1 2 3 5 10 15 25 50 75 125 250 500 1000
?79
1 2 3 5 7 14 19 38 76 79
?631
1 2 3 6 12 24 48 49 97 194 388 437 631
?512
1 2 4 8 16 32 64 128 256 512
?997
1 2 3 5 7 14 28 31 62 124 248 496 501 997
?0

Please note: a tree of size n may not contain all numbers up to n.

Is it a requirement to compute the /complete/ tree even though the output does not require all that information?

Yeah, MtnViewMark's solution does not comply with that requirement.

That interpretation of the requirement excludes any lazy language. Since the program doesn't actually use the complete tree, nothing will ever cause the computation to happen. See my expanded solution notes. I suppose one could compel a lazy language to write those results to /dev/null... but why?

Ruby, 172 148 139 137 characters
P={1=>[1]}
a=->k{P[k].map{|t|P[k+t]||=P[k]+[k+t]}}
P.keys.map{|v|a[v]}until(1..$*[0].to_i).all?{|u|P[u]}
STDIN.map{|l|p P[l.to_i]||break}

Most of the code is for input and output. Building the tree is only a few chars (lines 1-2). The tree is represented by a hash where key is the node and value its path to root. Since a tree of size n may not contain all numbers up to n we continuously add more levels until all numbers up to n are present in the tree.
For the example given above:
>1000
[1, 2, 3, 5, 10, 15, 25, 50, 75, 125, 250, 500, 1000]
>79
[1, 2, 3, 5, 7, 14, 19, 38, 76, 79]
>631
[1, 2, 3, 6, 12, 24, 48, 49, 97, 194, 388, 437, 631]
>512
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
>0

Edit 1: Now the hash contains the path for each node as value already and therefore there is no need to build the path each time.
Edit 2: Changed the break condition for the final loop.
Edit 3: Changed the condition for the build-loop.

Haskell, 174 185 195 characters
(%)=lookup
t(n,w)=map(\m->(n+m,n+m:w))w
_#0=return()
k#n=maybe(foldr(\e@(i,_)r->maybe(e:r)(\_->r)$i%r)k(k>>=t)#n)((>>main).print.reverse)$n%k
main=getLine>>=([(1,[1])]#).read

This version actually totally ignores the argument, and calculates the tree incrementally on demand.
1000
[1,2,3,5,10,15,25,50,75,125,250,500,1000]
79
[1,2,3,5,7,14,19,38,76,79]
631
[1,2,3,6,12,24,48,49,97,194,388,437,631]
512
[1,2,4,8,16,32,64,128,256,512]
997
[1,2,3,5,7,14,28,31,62,124,248,496,501,997]
0

Oh look! There wasn't any requirement to output a prompt. So now the code doesn't.

Edit (195 → 185): combined main and i
Edit (185 → 174): removed prompt

Ungolf'd
Here is an expanded version of the core computation:
type KPTree = [(Int, [Int])]
  -- an association from numbers to their ancester chains
  -- ancester chains are stored biggest to smallest
  -- the associations are ordered as in the tree, reading right to left,
  -- from the lowest level up

kptLevels :: [KPTree]
kptLevels = [(1,[1])] : map expand kptLevels
  -- a list of successive KPTrees, each one level deeper than the last
  where
    expand tree = foldr addIfMissing tree (concatMap nextLeaves tree)
    addIfMissing e@(n,_) tree = maybe (e:tree) (const tree) $ lookup n tree
    nextLeaves (n,w) = map (\m -> (n+m, n+m:w)) w

kptPath :: Int -> [Int]
kptPath n = findIn kptLevels
  -- find the ancestor chain for a given number
  where
    findIn (k:ks) = maybe (findIn ks) id $ lookup n k

To illustrate the strangeness of how to apply the pre-computation requirement to a lazy language, consider this version of main:
kptComputeAllTo :: Int -> [[Int]]
kptComputeAllTo n = map kptPath [1..n]
  -- compute all the paths for the first n integers

main :: IO ()
main = do
    n <- (read . head) `fmap` getArgs
    go $ kptComputeAllTo n
  where
    go preComputedResults = loop
      where
        loop = getLine >>= process . read
        process 0 = return ()
        process i = (print $ reverse $ preComputedResults !! (i - 1)) >> loop

Even thought it builds an array of the results for the first n integers, only those that are used are ever actually computed! Here's how fast it runs with 50 million as an argument:
> (echo 1000; echo 0) | time ./3177-PowerTree 50000000
[1,2,3,5,10,15,25,50,75,125,250,500,1000]
        0.09 real         0.07 user         0.00 sys

This doesn't compute the complete tree with n nodes.

It wasn't clear how to apply the requirements to a lazy language. Usually, an input value like this is given as a help so solutions can just allocate a fixed array. Solutions in dynamic languages often ignore such input (or limits in the spec).
I took the input to be a hint to the program as a bound on subsequent inputs. Indeed a program that meets the input/output requirements of this problem needn't use it at all. Typically, code-golf doesn't mandate how the internals achieve the results.

Fascinating.  What kind of runtime do you get to compute the chain for 50M?  The algorithm Knuth describes is O(n lg n) time and 2n+lg n space.

The algorithm used was aiming for code-golf, not time efficiency: It is roughly O(n^3 lg n) in time, though oddly only O(n) in space. On my somewhat aging CPU, it can compute the chain for 10k in 9.58s, or just about 100x the time it took to compute the chain for 1k. I'm pretty sure computing the chain for 50M wouldn't be possible with this code.

So, that's why I make the requirement that you compute the whole tree.  The point of code-golf (IMO) is to satisfy all requirements in the smallest number of characters.  If you're not satisfying all the requirements, it's a fail.

The skill in writing code-golf problems is to admit as much possible variation in implementation as possible, so that the smallest possible code can produce the desired result. If the requirements presume a particular implementation approach or language it's a fail.

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


text:
Bridges and Tunnels
You are responsible for building a new freeway. However, it leads through
mountainous lands and therefore needs numerous bridges and tunnels. The
freeway itself should stay at a single level.
Input
You are given a rough ASCII description of how the mountains look like on
standard input, such as the following:
                         /\
                        /  \
                   /\  /    \
            /\    /  \/      \
           /  \  /            \                  /\
          /    \/              \                /  \
_        /                      \        /\    /    \
 \      /                        \      /  \  /      \  /\
  \    /                          \    /    \/        \/  \
   \  /                            \  /
    \/                              \/

The _ in the first column marks the beginning and the level of the road.
The mountain range is contiguous and if the last segment will be a bridge,
it has an even number of characters.
You may assume that a line of input is never longer than 100 characters
and that there are no more than 15 lines. Every line has the same length
which is possibly space-padded at the end. The road never starts within a
mountain or as a bridge. The first thing following the road tile in the
input is either a slope down or up.
Output
Output is the same mountain range, except that there is now a road where
previously was only its beginning. Output is given on standard output.
For this there are numerous rules:

The road must start at the place indicated in the input and remain the
same level throughout. To make it easier, we have prepared a number of
premade road tiles which look like this: _:
_______
 \    /
  \/\/

The road must extend to the far end of the mountain range (i.e. the
length of the input lines dictates how far the road goes).
Tunnels must be drilled whenever a mountain is where the road needs to
go. Tunnels go straight through the mountain and leave holes at the start
and the end (i.e. a tunnel replaces the slope of the mountain with a
closing parenthesis at its start and an opening parenthesis at its end).
Tunnels leave, well, a tunnel in the mountain which usually has a
ceiling. Our premade road tiles luckily can be used to reinforce the
ceiling so that the tunnel does not collapse (the line above the tunnel
has to use _ to reinforce the tunnel):
      /\
     /  \
    /____\
___)______(__
 \/        \/

The tunnel does not need to be reinforced when the mountain isn't high
enough above it. It sounds weird to me as well but I have been told the
premade road tiles are strong enough to hold even when spaced out in that
case (no tunnel ceiling is drawn when there is a slope directly above the
tunnel):
       /\
    /\/__\
___)______(__
 \/        \/

Bridges are needed whenever the road needs to cross a chasm. For short
bridges the premade road tiles are strong enough but still need a bit
support at the beginning and end of the bridge (the first downward slope
under the bridge and the last upward slope are replaced by Y so that
there is a support beam for the bridge):
_____
 Y  Y
  \/

Longer bridges need additional support. A long bridge is one that has
more than six unsupported road tiles in a row. Long bridges need a pillar
in their center. Pillars are easily built with our prebuilt pillar beams
which look like this: |. Each pillar needs two of those and they extend
down to the bottom of the chasm:
_____________________________
 Y            ||            Y
  \        /\ || /\      /\/
   \  /\  /  \||/  \  /\/
    \/  \/    \/    \/

Since the input only represents a portion of the whole mountain range
the freeway needs to be built through, it may end abruptly in the middle
of a bridge or tunnel. The long bridge rule still applies for the final
segment and you can assume that the first part beyond the given input
supports the bridge again.

Following the above rules we get the following for our input:
                         /\
                        /  \
                   /\  /    \
            /\    /  \/      \
           /  \  /            \                  /\
          /____\/______________\                /__\
_________)______________________(________)(____)____(______
 Y      Y                        Y      Y  Y  Y      Y  YY
  \    /                          \    /    \/        \/  \
   \  /                            \  /
    \/                              \/

Shortest code by character count wins. Trailing whitespace in the lines is
ignored for validation.
Sample input 1
_
 \                            /\
  \                          /  \
   \                        /    \
    \                /\    /      \              /\        /
     \    /\        /  \  /        \      /\  /\/  \      /
      \  /  \      /    \/          \    /  \/      \/\  /
       \/    \    /                  \  /              \/
              \  /                    \/
               \/

Sample output 1
____________________________________________________________
 Y             ||             YY             ||
  \            ||            /  \            ||
   \           ||           /    \           ||
    \          ||    /\    /      \          ||  /\        /
     \    /\   ||   /  \  /        \      /\ |/\/  \      /
      \  /  \  ||  /    \/          \    /  \/      \/\  /
       \/    \ || /                  \  /              \/
              \||/                    \/
               \/

Sample input 2
                                           /\  /\
                                          /  \/  \                    /
           /\                            /        \  /\              /
    /\    /  \                          /          \/  \            /
   /  \  /    \/\                      /                \    /\    /
  /    \/        \                    /                  \  /  \  /
_/                \                  /                    \/    \/
                   \                /
                    \            /\/
                     \  /\      /
                      \/  \    /
                           \  /
                            \/

Sample output 2
                                           /\  /\
                                          /  \/  \                    /
           /\                            /        \  /\              /
    /\    /  \                          /          \/  \            /
   /  \  /    \/\                      /                \    /\    /
  /____\/________\                    /__________________\  /__\  /____
_)________________(__________________)____________________()____()_____
                   Y       ||       Y
                    \      ||    /\/
                     \  /\ ||   /
                      \/  \||  /
                           \| /
                            \/

Note
Trailing spaces in the output are ignored for comparison with the
reference solutions.
Winning condition
Shortest code wins, as is customary in golf. In case of a tie, the earlier
solution wins.
Test cases
There are two tests scripts, containing identical test cases:

bash
PowerShell

Invocation is in both cases: <test script> <my program> [arguments],
e.g. ./test ruby bridges.rb or ./test.ps1 ./bridges.exe.
Another note
This task was part of a golf contest held at my university during
2011-W24. The scores and languages of our contestants were as follows:

304 – Perl
343 – C
375 – C
648 – Python

Our own solution (thanks to Ventero) was

262 – Ruby

Note: I updated the test scripts where some test cases contained an unintentional empty line at the top. Should be fixed now.

Perl, 210 195 194 193 chars
update
Same ideas, but applied very differently, for the most part.
Run with perl -p0 (4 chars counted for the switches).
($o,$c,$r,$b)=/((.+\n)?(_.+\n)(.+\n)?)/;/\n/;$n=$-[0];$c=~s{/ }{/_}g;$r=~y{ /\\}{_)(};map{s{\\(   +)  \1(/|\n)}{\\$1||$1$2}g,y{\\/}{Y}}$b;s/\Q$o/$c$r$b/;1while(s/_ /__/||s/(\|.{$n}) /$1|/s)

This also requires a change to the bash test script, so as not to over-quote the args:
-   got=$("$cmd" "$args")
+   got=$("$cmd" $args)

BTW, I really appreciate the test scripts, @Joey.
commented:
#-p : implicitly read input and print after transformations
#-0 : "slurp mode": don't break lines

# grab the roadway line, along with the lines above and below for ceiling and buttresses
# also grab the whole match in $o for replacing later
($o,$c,$r,$b)=/((.+\n)?(_.+\n)(.+\n)?)/;

# compute line length
/\n/;$n=$-[0];

# start ceilings
$c=~s{/ }{/_}g;

# build the road and tunnels
$r=~y{ /\\}{_)(};

# use map to avoid repeating $b =~
map{
  # insert the pillar tops
  s{\\(   +)  \1(/|\n)}{\\$1||$1$2}g,
  # and the buttresses
  y{\\/}{Y}
} $b;

# put those 3 (or 2) lines back into the original
s/\Q$o/$c$r$b/;

# extend ceiling tiles to the right and pillars downward
1while(s/_ /__/||s/(\|.{$n}) /$1|/s)

edits:

replace "{3,}" with 3 literal spaces and the + quantifier, to
save another character
use the 1while(...) form, where I can omit
the semicolon at the end of the script

original (see history for commented version)
@a=map{($r=$n),y{ /\\}{_)(}if/_/;$n++;$_}<>;if($r){while($a[$r-1]=~s{(/[ _]*) }{$1_}){}}map{s{(^|\\)( {3,})  \2(/|$)}{$1$2||$2$3}g;y{\\/}{YY}}$a[$r+1];$_=join'',@a;/\n/;$n=$-[0];while(s/(\|.{$n}) /$1|/s){}print

I deliberately didn't look at @Howard's Perl solution until mine was working, but I was able to improve my golfing by looking afterward.
In particular, the regexps for tunnel ceilings and extending pillars helped. Nicely done, Howard.
Conversely, my alternative for getting line length, using the implicit $_ for the print, leaving off the final semicolon, and removing newlines could shorten Howard's to 222 characters.

For the bash test script give thanks to Ventero. I just took what he created and bashed at it until it worked somewhat ;-)

Perl, 234 characters
$_=join'',<>;$l=index($_,"\n");
($w)=/(_[^\n]*)/;$w=~y/ \\\//_()/;s/_[^\n]*/$w/e;
while(s/(\/[ _]*) (?=[^\n]*\n_)/$1_/||s/(_.{$l})[\\\/]/$1Y/s){}while(s/(\n( |Y *Y)*)Y( {3,})  \3(Y| ?\n)/\1Y\3||\3\4/||s/(?<=\|.{$l}) /|/s){}
print $_;

This is a perl regex-only solution. It passes all given test cases.
The identical but more readable version shows the steps taken to obtain the result:
$_=join'',<>;                    # read the input
$l=index($_,"\n");               # determine length of line

($w)=/(_[^\n]*)/;                # extract the line starting with _
$w=~y/ \\\//_()/;                # and build road there (i.e. replace all chars in line)
s/_[^\n]*/$w/e;                  # put road back into string

while(s/(\/[ _]*) (?=[^\n]*\n_)/$1_/||s/(_.{$l})[\\\/]/$1Y/s){}
                                 # build ceiling of tunnels
                                 # build Y supports directly below the road

while(s/(\n( |Y *Y)*)Y( {3,})  \3(Y| ?\n)/\1Y\3||\3\4/||s/(?<=\|.{$l}) /|/s){}
                                 # build center support in middle of bridges
                                 # and extend them down to the ground

print $_;                        # print result

Yikes. That looks rather evil in all parts ;-). Why do Perl people always have to solve everything with regexes? :-þ

Because regices are the weapons of a true Perl hacker :ð

A perl hacker (I called my self such in years bygone) thinks quite the other way around, Joey: if a problem can be solved with regexes, why bother with anything else?  This really is an ideal problem for regular expressions, I think: it's that or implement a backtracking state machine yourself.

That wasn't meant entirely serious. My own reference solution initially used lots of regexes as well.

C++, 662 622 598 chars, 4 lines
#include<iostream>
#include<string>
#define s for(
#define v g[t][f]
int t,f,r,q,m=-1,w,b,e,h,j,x,y,l,c=18;int main(){std::string g[19];s;r<19;h=c)getline(std::cin,g[r++]);s;c>=0;g[c--].push_back(0))(q=g[c].size())&&g[c][0]-95?0:r=c;s;c<q;y=0){x=g[r][++c];x==47?x=41,w=e=1:++y;x==92?x=40,w=0:++y;t=r-1;f=c;y>1?x=95,w?r&&v==32?v=95:0:++b:0;c-q?0:e=1;t++;s v=x;m<0;)g[h].find(47)<g[h--].npos?m=h:0;t=r+1;if(r<m){(y=v)==47?y=89,e=1:0;v=y-92?y:89;if(e){y=e=0;if((b/=2)>4){j=l=r+1;s;!y;t=j,f=c-b+1,v==32?v=124,++j:0)t=l,y=f=c-b,v==32?v=124,l++,y=0:0;}b=0;}}}s f=q,t=0;t<=m;std::cout<<g[t++]<<'\n')v=32;}

This should be it, I've tested this out with the powershell script so it should be ok...
Edit 1
Replaced all char constants with numbers, removed successive calls to std::cout + a few other minor changes.
Edit 2
last edit, just to get it less than 600.  Took out g[t][f] as a #define and moved a few things around.

Yep, I had a few test cases wrong, but that's my own fault. Looks good now :-)

Would it help to #define std::?

@FUZxxl, I don't think so, I only use "std::" 4 times so that's 20 characters, if I used a define i would need 2 chars at each of those places(eg "a cout" using a as std::) and the define would take more than 12 chars, "using namespace std" isn't worth it either.

Ruby, 382 356 353 characters
I thought to give a non-regex solution a shot.
m=$<.read;n,r,s,$e,t=(/\n/=~m)+1,/^_/=~m,m.size,(u,d=47,92),0;def j y;$e.member? y;end;(n-1).times{|i|x=r+i;c=m[x];j(c)||(m[x]=95;a,b=x-n,x+n;t<41||a<0||m[a]>32||m[a]=95;b>s||!j(m[b])||(m[b]<d||(p=(/\/|\n/=~m[b..s])/2+b;p-b<4||(w=[f=false,f];p.step(s,n){|p|2.times{|i|(w[i]||=j m[i=p+i])||m[i]='|'}}));m[b]='Y'));c!=u||t=m[x]=41;c!=d||t=m[x]=40};print m

The biggest space saver here is to use conditional || operator instead of if - elsif - end. So instead of writing if(a) lorem_ipsum end I've written !a||lopem_ipsum. Larger blocks can included using parenthesis !a||(block). If the condition includes && operators then they must negated by using parenthesis and a ! or by using De Morgan's laws.
And here's the same with more words
# read the STDIN to string
mountains = $<.read
line_length,road_level,size,$slopes,in_tunnel =
        (/\n/ =~ mountains) + 1, # Fint the first new line
        /^_/ =~ mountains, # Find the index of the road
        mountains.size,
        (slope_up,slope_down=47,92),
        0

def is_slope y;$slopes.member? y;end

# For each index in the road line
(line_length - 1).times { |i|
  curindex = road_level + i
  curchar = mountains[curindex]

  # If not a slope then
  (is_slope(curchar))|| (

    # mark road as underscore
    mountains[curindex] = 95
    above, below = curindex - line_length, curindex + line_length

    # add roof to tunnel if in tunnel and the mountain
    # is high enough
    in_tunnel<41||above<0||mountains[above]>32||mountains[above]=95

    # If there's a slope character below the road
    below>size||!is_slope(mountains[below])||(

      # if there's a downward slop - start a bridge
      mountains[below]<slope_down||(

          # If bridge is longer than 6 characters
          # Add support to the middle
          support_pos = (/\/|\n/=~mountains[below..size])/2+below
          support_pos-below<4||(
            # Init collision detection
            collision_detected=[f=false,f]
            # Build supports as long as
            # There is mountains below
            support_pos.step(size,line_length) { |support_pos|

               # Add two parallel suppports
               2.times { |i|

               # Add support if the bottom of the
               # gap has not been reached
               (collision_detected[i]||=is_slope(mountains[i=support_pos+i]))||mountains[i] = '|'
               }
            }
          )
      )

      # Add support to the beginning and to the end
      # of the bridge
      mountains[below] = 'Y'
    )
  )

  # Add tunnel entrance and exit
  curchar!=slope_up||in_tunnel=mountains[curindex]=41
  curchar!=slope_down||in_tunnel=mountains[curindex]=40
}

print mountains

The tests are ok - I had just screwed up the test script while pasting it ... awkward.

Scala, 462 characters
object B extends App{var r="""(?s)((?:.*\n)?)((?:.*?\n)?)(_.*?\n)(.*?\n)(.*)""".r
var r(a,b,c,d,e)=io.Source.stdin.mkString
var s=a+b.replaceAll("(?<=/ {0,99}) (?=.*\\\\)","_")+c.replaceAll("\\\\","(").replaceAll("/",")").replaceAll(" ","_")+d.replaceAll("\\\\( {3,99})  \\1/","Y$1||$1Y").replaceAll("\\\\( {3,99})  \\1\\n","Y$1||$1\n").replaceAll("\\\\( {0,9})/","Y$1Y")+e
for(i<-1 to 15)s=s.replaceAll("(?s)(?<=\\|.{"+s.split("\n")(0).size+"}) ","|")
print(s)}

Not particularly competitive, but I've learnt a lot about regular expressions today. :-)

Erlang, 1182 characters
-module(b).
-export([t/0]).
t()->r([]).
r(R)->case io:get_line("")of eof->{_,Q}=lists:foldl(fun([$ |L],{$_,Q})->{$ ,[[$X|L]|Q]};([C|_]=L,{_,Q})->{C,[L|Q]}end,{$ ,[]},R),{_,P}=lists:foldl(fun s/2,{s,[]},lists:flatten(Q)),io:put_chars(lists:reverse(P));L->r([L|R])end.
s($X,{s,R})->{{r,s},[$ |R]};s($/,{{r,s},R})->{{r,r},[$/|R]};s($\\,{{r,r},R})->{{r,s},[$\\|R]};s($\n,{{r,_},R})->{u,[$\n|R]};s(_,{{r,r}=S,R})->{S,[$_|R]};s($_,{_,R})->{u,[$_|R]};s($\n,{u,R})->{{g,i,1,1,[]},[$\n|R]};s($\\,{u=S,R})->{S,[$(|R]};s($/,{u=S,R})->{S,[$)|R]};s(_,{u=S,R})->{S,[$_|R]};s($\\,{{g,i,X,_L,T},R})->{{g,o,X+1,X,[$Y|T]},R};s($/,{{g,o,X,L,T},R})->a(o,X,L),{{g,i,X+1,X,[$Y|T]},R};s($\n,{{g,S,X,L,T},R})->a(S,X,L),{{d,1},[$\n,f(T,X)|R]};s(C,{{g,S,X,L,T},R})->{{g,S,X+1,L,[C|T]},R};s($\n,{{d,_},R})->{{d,1},[$\n|R]};s($ ,{{d,X},R})->{{d,X+1},[case get(X)of y->$|;_->$ end|R]};s($/,{{d,X},R})->put(X,n),{{d,X+1},[$/|R]};s($\\,{{d,X},R})->put(X,n),{{d,X+1},[$\\|R]};s($\n=N,{S,R})->{S,[N|R]};s(X,{S,R})->{S,[X|R]}.
a(o,X,L)when X-L-1>6->Pos=round((X-L-1)/2+L),put(Pos,y),put(Pos+1,y);a(_,_,_)->v.
f(L,M)->{_,R}=lists:foldl(fun(C,{X,R})->case get(M-X)of y->{X+1,[$||R]};_->{X+1,[C|R]}end end,{1,[]},L),R.

Not competitive at all. To be honest, I was simply interested in producing some nice ascii art, not so much in the golfing. Note that this does not use regular expressions, instead, I wrote the state machine myself. This will also need the overquoting fix in the shell script, mentioned in the perl solution above.

Powershell, 300 295 287 bytes
-8 bytes fix peeked from DCharness'es answer.
param($s)filter e{$r,$e=$_-split'#';$e|%{$r=$r-replace($_-split';')};$r}
$x=$s-match'(.+
)?(_.+)(
.+)?'
$o,$c,$r,$b=$Matches[0..3]
for($s=$s|% *ce $o(("$c#/ ;/_"|e)+("$r# ;_#/;)#\\;("|e)+($b+'#\\(   +)  \1;\$1||$1#/|\\;Y'|e));$s-ne($x="$s#_ ;__#(?s)(?<=\|.{$($r|% Le*)}) ;|"|e)){$s=$x}$s

Ungolfed test script:
$f = {

param($s)
$x=$s-match'(.+
)?(_.+)(
.+)?'
$o,$c,$r,$b=$Matches[0..3]
$c=$c-replace'/ ','/_'                  # we assume that road does not start as a tunnel
$r=$r-replace' ','_'
$r=$r-replace'/',')'
$r=$r-replace'\\','('
$b=$b-replace'\\(   +)  \1','\$1||$1'   # we assume that road does not start as a bridge under a chasm
$b=$b-replace'/|\\','Y'
$s=$s.replace($o,"$c$r$b")              # string method replace (not operator) does not handle regexp
for(;$s-ne($x=$s-replace'_ ','__'-replace"(?s)(?<=\|.{$($r.Length)}) ",'|')){$s=$x}
$s

}

$pass = 0
$count = 0

@(
# Test 2
,(2,@'
    /\                  /\                  /\
   /  \                /  \                /  \
  /____\              /____\              /____\
_)______(____________)______(____________)______(_____
         Y    ||    Y        Y    ||    Y        Y
          \   ||   /          \   ||   /          \
           \  ||  /            \  ||  /            \
            \ || /              \ || /              \
             \||/                \||/                \
              \/                  \/
'@,@'
    /\                  /\                  /\
   /  \                /  \                /  \
  /    \              /    \              /    \
_/      \            /      \            /      \
         \          /        \          /        \
          \        /          \        /          \
           \      /            \      /            \
            \    /              \    /              \
             \  /                \  /                \
              \/                  \/
'@)

# Test 1
,(1,@'
____________________________________________________________
 Y             ||             YY             ||
  \            ||            /  \            ||
   \           ||           /    \           ||
    \          ||    /\    /      \          ||  /\        /
     \    /\   ||   /  \  /        \      /\ |/\/  \      /
      \  /  \  ||  /    \/          \    /  \/      \/\  /
       \/    \ || /                  \  /              \/
              \||/                    \/
               \/
'@,@'
_
 \                            /\
  \                          /  \
   \                        /    \
    \                /\    /      \              /\        /
     \    /\        /  \  /        \      /\  /\/  \      /
      \  /  \      /    \/          \    /  \/      \/\  /
       \/    \    /                  \  /              \/
              \  /                    \/
               \/
'@)

# Test 3
,(3,@'
    /\
   /  \
  /____\/\/\/\/\/\/\/\
_)____________________(
'@,@'
    /\
   /  \
  /    \/\/\/\/\/\/\/\
_/                    \
'@)

# Test 4
,(4,@'
___________________________________________________
 Y           ||           YY          ||          Y
  \          ||          /  \         |/\        /
   \         ||         /    \        /  \      /
    \    /\  ||    /\  /      \      /    \    /
     \  /  \ ||   /  \/        \    /      \  /
      \/    \||  /              \  /        \/
             \| /                \/
              \/
'@,@'
_
 \                        /\                      /
  \                      /  \          /\        /
   \                    /    \        /  \      /
    \    /\        /\  /      \      /    \    /
     \  /  \      /  \/        \    /      \  /
      \/    \    /              \  /        \/
             \  /                \/
              \/
'@)

# Test 5
,(5,@'
                                                      /
                                                     /
                                                    /__
___________________________________________________)___
 Y           ||           YY          ||          Y
  \          ||          /  \         |/\        /
   \         ||         /    \        /  \      /
    \    /\  ||    /\  /      \      /    \    /
     \  /  \ ||   /  \/        \    /      \  /
      \/    \||  /              \  /        \/
             \| /                \/
              \/
'@,@'
                                                      /
                                                     /
                                                    /
_                                                  /
 \                        /\                      /
  \                      /  \          /\        /
   \                    /    \        /  \      /
    \    /\        /\  /      \      /    \    /
     \  /  \      /  \/        \    /      \  /
      \/    \    /              \  /        \/
             \  /                \/
              \/
'@)

# Test 6
,(6,@'
_______________________________)
 YYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
'@,@'
_                              /
 \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
'@)

# Test 7
,(7,@'
_________________________________)
 Y              ||              Y
  \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
'@,@'
_                                /
 \                              /
  \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
'@)

# Test 8
,(8,@'
      /\    /\    /\    /\    /\    /\
_)(__)__(__)__(__)__(__)__(__)__(__)__(
   YY    YY    YY    YY    YY    YY
'@,@'
      /\    /\    /\    /\    /\    /\
_/\  /  \  /  \  /  \  /  \  /  \  /  \
   \/    \/    \/    \/    \/    \/
'@)

# Test 9
,(9,@'
  /\/\/\/\/\/\/\/\
_)________________(
'@,@'
  /\/\/\/\/\/\/\/\
_/                \
'@)

# Test 10
,(10,@'
      /\                                                            /\
     /  \                                                          /  \
    /    \                                                        /    \
   /      \                                                      /      \
  /________\                                                    /________\/\/\/\/\
_)__________(__________________________________________________)__________________(______)(_________
             Y                       ||                       Y                    Y    Y  Y   ||
              \                      ||    /\                /                      \  /    \  ||  /
               \    /\               ||   /  \              /                        \/      \ || /
                \  /  \              ||  /    \            /                                  \||/
                 \/    \             || /      \          /                                    \/
                        \        /\  ||/        \        /
                         \      /  \ |/          \      /
                          \    /    \/            \    /
                           \/\/                    \/\/
'@,@'
      /\                                                            /\
     /  \                                                          /  \
    /    \                                                        /    \
   /      \                                                      /      \
  /        \                                                    /        \/\/\/\/\
_/          \                                                  /                  \      /\
             \                                                /                    \    /  \
              \                            /\                /                      \  /    \      /
               \    /\                    /  \              /                        \/      \    /
                \  /  \                  /    \            /                                  \  /
                 \/    \                /      \          /                                    \/
                        \        /\    /        \        /
                         \      /  \  /          \      /
                          \    /    \/            \    /
                           \/\/                    \/\/
'@)

# Test 11
,(11,@'
__________________________________________________
 Y     ||     YY     ||     YY         ||
  \    ||    /  \    ||    /  \        /\
   \   ||   /    \   ||   /    \      /  \    /\
    \  ||  /      \  ||  /      \    /    \  /  \/
     \ || /        \ || /        \  /      \/
      \||/          \||/          \/
       \/            \/
'@,@'
_
 \            /\            /\
  \          /  \          /  \        /\
   \        /    \        /    \      /  \    /\
    \      /      \      /      \    /    \  /  \/
     \    /        \    /        \  /      \/
      \  /          \  /          \/
       \/            \/
'@)

# Test 12
,(12,@'
                                           /\  /\
                                          /  \/  \                    /
           /\                            /        \  /\              /
    /\    /  \                          /          \/  \            /
   /  \  /    \/\                      /                \    /\    /
  /____\/________\                    /__________________\  /__\  /____
_)________________(__________________)____________________()____()_____
                   Y       ||       Y
                    \      ||    /\/
                     \  /\ ||   /
                      \/  \||  /
                           \| /
                            \/
'@,@'
                                           /\  /\
                                          /  \/  \                    /
           /\                            /        \  /\              /
    /\    /  \                          /          \/  \            /
   /  \  /    \/\                      /                \    /\    /
  /    \/        \                    /                  \  /  \  /
_/                \                  /                    \/    \/
                   \                /
                    \            /\/
                     \  /\      /
                      \/  \    /
                           \  /
                            \/
'@)

# Test 13
,(13,@'
_____________)(____________)(_____________________
 Y    ||    Y  Y    ||    Y  Y   ||   YY    ||
  \   ||   /    \   ||   /    \  ||  /  \   |/\  /
   \  ||  /      \  ||  /      \ || /    \  /  \/
    \ || /        \ || /        \||/      \/
     \||/          \||/          \/
      \/            \/
'@,@'
_            /\            /\
 \          /  \          /  \        /\
  \        /    \        /    \      /  \    /\  /
   \      /      \      /      \    /    \  /  \/
    \    /        \    /        \  /      \/
     \  /          \  /          \/
      \/            \/
'@)

# Test 14
,(14,@'
            /\            /\
___________)__(__________)__(________)(_________
 Y   ||   Y    Y   ||   Y    Y      Y  Y    YY
  \  ||  /      \  ||  /      \    /    \  /  \/
   \ || /        \ || /        \  /      \/
    \||/          \||/          \/
     \/            \/
'@,@'
            /\            /\
_          /  \          /  \        /\
 \        /    \        /    \      /  \    /\
  \      /      \      /      \    /    \  /  \/
   \    /        \    /        \  /      \/
    \  /          \  /          \/
     \/            \/
'@)

# Test 15
,(15,@'
           /\            /\
          /__\          /__\        /\
_________)____(________)____(______)__(____)(__
 Y      Y      Y      Y      Y    Y    Y  Y  YY
  \    /        \    /        \  /      \/
   \  /          \  /          \/
    \/            \/
'@,@'
           /\            /\
          /  \          /  \        /\
_        /    \        /    \      /  \    /\
 \      /      \      /      \    /    \  /  \/
  \    /        \    /        \  /      \/
   \  /          \  /          \/
    \/            \/
'@)

# Test 16
,(16,@'
          /\            /\
         /  \          /  \        /\
        /____\        /____\      /__\    /\
_______)______(______)______(____)____(__)__()
 Y    Y        Y    Y        Y  Y      YY
  \  /          \  /          \/
   \/            \/
'@,@'
          /\            /\
         /  \          /  \        /\
        /    \        /    \      /  \    /\
_      /      \      /      \    /    \  /  \/
 \    /        \    /        \  /      \/
  \  /          \  /          \/
   \/            \/
'@)

# Test 17
,(17,@'
         /\            /\
        /  \          /  \        /\
       /    \        /    \      /  \    /\
      /______\      /______\    /____\  /__\/
_____)________(____)________(__)______()_____
 Y  Y          Y  Y          YY
  \/            \/
'@,@'
         /\            /\
        /  \          /  \        /\
       /    \        /    \      /  \    /\
      /      \      /      \    /    \  /  \/
_    /        \    /        \  /      \/
 \  /          \  /          \/
  \/            \/
'@)

# Test 18
,(18,@'
        /\            /\
       /  \          /  \        /\
      /    \        /    \      /  \    /\
     /      \      /      \    /    \  /  \/
    /________\    /________\  /______\/_____
___)__________(__)__________()______________
 YY            YY
'@,@'
        /\            /\
       /  \          /  \        /\
      /    \        /    \      /  \    /\
     /      \      /      \    /    \  /  \/
    /        \    /        \  /      \/
_  /          \  /          \/
 \/            \/
'@)

# Test 19
,(19,@'
       /\            /\
      /  \          /  \        /\
     /    \        /    \      /  \    /\
    /      \      /      \    /    \  /  \/
   /        \    /        \  /      \/
  /__________\  /__________\/______________
_)____________()___________________________
'@,@'
       /\            /\
      /  \          /  \        /\
     /    \        /    \      /  \    /\
    /      \      /      \    /    \  /  \/
   /        \    /        \  /      \/
  /          \  /          \/
_/            \/
'@)

# Test 20
,(20,@'
__________________________________________________
 Y     ||     YY     ||     YY         ||
  \    ||    /  \    ||    /  \        /\
   \   ||   /    \   ||   /    \      /  \    /\
    \  ||  /      \  ||  /      \    /    \  /  \
     \ || /        \ || /        \  /      \/    \
      \||/          \||/          \/
       \/            \/
'@,@'
_
 \            /\            /\
  \          /  \          /  \        /\
   \        /    \        /    \      /  \    /\
    \      /      \      /      \    /    \  /  \
     \    /        \    /        \  /      \/    \
      \  /          \  /          \/
       \/            \/
'@)

# Test 21
,(21,@'
      /\            /\
     /  \          /  \        /\
    /    \        /    \      /  \    /\
   /      \      /      \    /    \  /  \/
  /________\    /________\  /______\/_____
_)__________(__)__________()______________
             YY
'@,@'
      /\            /\
     /  \          /  \        /\
    /    \        /    \      /  \    /\
   /      \      /      \    /    \  /  \/
  /        \    /        \  /      \/
_/          \  /          \/
             \/
'@)

# Test 22
,(22,@'
     /\            /\
    /  \          /  \        /\
   /    \        /    \      /  \    /\
  /______\      /______\    /____\  /__\/
_)________(____)________(__)______()_____
           Y  Y          YY
            \/
'@,@'
     /\            /\
    /  \          /  \        /\
   /    \        /    \      /  \    /\
  /      \      /      \    /    \  /  \/
_/        \    /        \  /      \/
           \  /          \/
            \/
'@)

# Test 23
,(23,@'
                         /\
                        /  \
                   /\  /    \
            /\    /  \/      \
           /  \  /            \                  /\
          /____\/______________\                /__\
_________)______________________(________)(____)____(_______
 Y      Y                        Y      Y  Y  Y      Y  YY
  \    /                          \    /    \/        \/  \/
   \  /                            \  /
    \/                              \/
'@,@'
                         /\
                        /  \
                   /\  /    \
            /\    /  \/      \
           /  \  /            \                  /\
          /    \/              \                /  \
_        /                      \        /\    /    \
 \      /                        \      /  \  /      \  /\
  \    /                          \    /    \/        \/  \/
   \  /                            \  /
    \/                              \/
'@)

# Test 24
,(24,@'
    /\            /\
   /  \          /  \        /\
  /____\        /____\      /__\    /\
_)______(______)______(____)____(__)__()
         Y    Y        Y  Y      YY
          \  /          \/
           \/
'@,@'
    /\            /\
   /  \          /  \        /\
  /    \        /    \      /  \    /\
_/      \      /      \    /    \  /  \/
         \    /        \  /      \/
          \  /          \/
           \/
'@)

# Test 25
,(25,@'
   /\            /\
  /__\          /__\        /\
_)____(________)____(______)__(____)(__
       Y      Y      Y    Y    Y  Y  YY
        \    /        \  /      \/
         \  /          \/
          \/
'@,@'
   /\            /\
  /  \          /  \        /\
_/    \        /    \      /  \    /\
       \      /      \    /    \  /  \/
        \    /        \  /      \/
         \  /          \/
          \/
'@)

# Test 26
,(26,@'
  /\            /\
_)__(__________)__(________)(_________
     Y   ||   Y    Y      Y  Y    YY
      \  ||  /      \    /    \  /  \/
       \ || /        \  /      \/
        \||/          \/
         \/
'@,@'
  /\            /\
_/  \          /  \        /\
     \        /    \      /  \    /\
      \      /      \    /    \  /  \/
       \    /        \  /      \/
        \  /          \/
         \/
'@)

# Test 27
,(27,@'
_)(____________)(_____________________
   Y    ||    Y  Y   ||   YY    ||
    \   ||   /    \  ||  /  \   |/\  /
     \  ||  /      \ || /    \  /  \/
      \ || /        \||/      \/
       \||/          \/
        \/
'@,@'
_/\            /\
   \          /  \        /\
    \        /    \      /  \    /\  /
     \      /      \    /    \  /  \/
      \    /        \  /      \/
       \  /          \/
        \/
'@)

# Test 28
,(28,@'
____________________________________
 Y     ||     YY         ||
  \    ||    /  \        /\
   \   ||   /    \      /  \    /\
    \  ||  /      \    /    \  /  \/
     \ || /        \  /      \/
      \||/          \/
       \/
'@,@'
_
 \            /\
  \          /  \        /\
   \        /    \      /  \    /\
    \      /      \    /    \  /  \/
     \    /        \  /      \/
      \  /          \/
       \/
'@)

# Test 29
,(29,@'
_____________________________
 Y            ||            Y
  \        /\ || /\      /\/
   \  /\  /  \||/  \  /\/
    \/  \/    \/    \/
'@,@'
_
 \                          /
  \        /\    /\      /\/
   \  /\  /  \  /  \  /\/
    \/  \/    \/    \/
'@)

# Test 30
,(30,@'
_____
 Y  Y
  \/
'@,@'
_
 \  /
  \/
'@)

# Test 31
,(31,@'
       /\
    /\/__\
___)______(__
 YY        YY
'@,@'
       /\
    /\/  \
_  /      \
 \/        \/
'@)

# Test 32
,(32,@'
      /\
     /  \
    /____\
___)______(__
 YY        YY
'@,@'
      /\
     /  \
    /    \
_  /      \
 \/        \/
'@)

# Test 33
,(33,@'
_______
 Y    Y
  \/\/
'@,@'
_
 \    /
  \/\/
'@)

# Test 34
,(34,@'
_)()()()()()()()()()()()()()()()()()(
'@,@'
_/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
'@)

) | % {
    $num, $expected, $s = $_
    $result = &$f $s
    $passed=$result-eq$expected
    "$num : $passed"
    # $result           # uncomment this line to display results

    $pass+=$passed
    $count+=1
}

"$pass/$count passed."

Output:
2 : True
1 : True
3 : True
4 : True
5 : True
6 : True
7 : True
8 : True
9 : True
10 : True
11 : True
12 : True
13 : True
14 : True
15 : True
16 : True
17 : True
18 : True
19 : True
20 : True
21 : True
22 : True
23 : True
24 : True
25 : True
26 : True
27 : True
28 : True
29 : True
30 : True
31 : True
32 : True
33 : True
34 : True
34/34 passed.

Explanation comics:
Start here:
    /\                  /\                  /\
   /  \                /  \                /  \
  /    \              /    \              /    \
_/      \            /      \            /      \
         \          /        \          /        \
          \        /          \        /          \
           \      /            \      /            \
            \    /              \    /              \
             \  /                \  /                \
              \/                  \/

Match and zoom it!
  /    \              /    \              /    \      $ceiling \
_/      \            /      \            /      \     $road    |  $outline
         \          /        \          /        \    $bottom  /

Start ceiling:
  /_   \              /_   \              /_   \      $ceiling \
_/      \            /      \            /      \     $road    |  $outline
         \          /        \          /        \    $bottom  /

Dig tunnels, build a road:
  /_   \              /_   \              /_   \      $ceiling \
_)______(____________)______(____________)______(_____$road    |  $outline
         \          /        \          /        \    $bottom  /

Attach to the road the top parts of pillars:
  /_   \              /_   \              /_   \      $ceiling \
_)______(____________)______(____________)______(_____$road    |  $outline
         \    ||    /        \    ||    /        \    $bottom  /

The road need support:
  /____\              /____\              /____\      $ceiling \
_)______(____________)______(____________)______(_____$road    |  $outline
         Y    ||    Y        Y    ||    Y        Y    $bottom  /

Put the road back into mountainous lands:
    /\                  /\                  /\
   /  \                /  \                /  \
  /_   \              /_   \              /_   \      $ceiling \
_)______(____________)______(____________)______(_____$road    |  $outline
         Y    ||    Y        Y    ||    Y        Y    $bottom  /
          \        /          \        /          \
           \      /            \      /            \
            \    /              \    /              \
             \  /                \  /                \
              \/                  \/

Build ceilings and build down pillars:
    /\                  /\                  /\
   /  \                /  \                /  \
  /__  \              /__  \              /__  \
_)______(____________)______(____________)______(_____
         Y    ||    Y        Y    ||    Y        Y
          \   ||   /          \   ||   /          \
           \      /            \      /            \
            \    /              \    /              \
             \  /                \  /                \
              \/                  \/

A few iterations later...
    /\                  /\                  /\
   /  \                /  \                /  \
  /____\              /____\              /____\
_)______(____________)______(____________)______(_____
         Y    ||    Y        Y    ||    Y        Y
          \   ||   /          \   ||   /          \
           \  ||  /            \  ||  /            \
            \ || /              \ || /              \
             \||/                \||/                \
              \/                  \/

Thanks. But our princess is in another castle!

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


text:
Solve the eight queens problem at compile-time
Can you solve the eight queens puzzle at compile-time?
Pick any suitable output format.
I'm particularly interested in a C++ template metaprogramming solution, but you can use languages that have similar constructs, like, for example, Haskell's type system.
Ideally your metaprogram would output all solutions. No hardcoding.

Why don't you allow different languages?

@user: Because I'm interested in a C++ TMP solution. If you know of a language that has very similar constructs, feel free to post an answer, though.

Can I also use the type system of Haskell? AFAIK it should be turing complete.

@FUZxxl: Yes. I'll edit the question.

Is it sufficient to do the brute-force-solution?

As long as it's computed, I think it's fine. But efficient solutions get more points of course :)

too hard, I just did parsing on Haskell type system https://gist.github.com/456802

@Martinho: I guess it is possible with the Scala Type System, but I'm not able to suggest a solution. I'm sorry.

The problem with allowing any language is that Lisps will spoil the fun for anything where the “compile time” constraint is there as a proxy for “something different from run time”.

My meta-program finds all 92 solutions. They are printed as error messages:
error: ‘solution’ is not a member of ‘std::integral_constant<int, 15863724>’

This means the first queen should be placed at y=1, the second at y=5, the third at y=8 and so on.
The meta-program consists of two mutually recursive meta-functions put_queen and put_queens:
#include <type_traits>

template<int queens, int rows, int sums, int difs, int x, int y>
struct put_queen;

template<int queens, int rows, int sums, int difs, int x>
struct put_queens : std::integral_constant<int,
    // try all 8 possible values for y
       put_queen<queens, rows, sums, difs, x, 1>::value
     | put_queen<queens, rows, sums, difs, x, 2>::value
     | put_queen<queens, rows, sums, difs, x, 3>::value
     | put_queen<queens, rows, sums, difs, x, 4>::value
     | put_queen<queens, rows, sums, difs, x, 5>::value
     | put_queen<queens, rows, sums, difs, x, 6>::value
     | put_queen<queens, rows, sums, difs, x, 7>::value
     | put_queen<queens, rows, sums, difs, x, 8>::value
> {};

template<int queens, int rows, int sums, int difs, int x, int y>
struct put_queen : std::conditional<
    // if blocked
    rows & (1 << y)
 || sums & (1 << (x + y))
 || difs & (1 << (x - y + 8)),
    // then backtrack
    std::integral_constant<int, 0>,
    // else recurse
    put_queens<queens * 10 + y,
               rows | (1 << y),
               sums | (1 << (x + y)),
               difs | (1 << (x - y + 8)),
               x + 1
    >
>::type {};

The variable queens stores the y coordinates of the queens placed on the board so far.
The following three variables store the rows and diagonals that are already occupied by queens.
x and y should be self-explanatory.
The first argument to conditional checks whether the current position is blocked.
If it is, we backtrack by returning the (meaningless) result 0.
Otherwise, the queen is placed on the board, and the recursion continues with the next column.
When x reaches 8, we have found a solution:
template<int queens, int rows, int sums, int difs>
struct put_queens<queens, rows, sums, difs, 8> {
    // print solution as error message by accessing non-existent member
    enum { value = std::integral_constant<int, queens>::solution };
};

Since integral_constant has no member solution, the compiler prints queens as an error message.
To start the recursion, we inspect the value member of the empty board:
int go = put_queens<0, 0, 0, 0, 0>::value;

The complete program can be found at ideone.

I like: 1) using bitfields to store data, 2) the choice of output method.

Too much awesomeness for one answer.

Should it not also output the x values?

@DeadMG The x-value of each queen location is its position in the string (1-8).

I came up with a solution that uses the Haskell type system. I googled a bit for an existing solution to the problem at the value level, changed it a bit, and then lifted it to the type level. It took a lot of reinventing. I also had to enable a bunch of GHC extensions.
First, since integers are not allowed at the type level, I needed to reinvent the natural numbers once more, this time as types:
data Zero -- type that represents zero
data S n  -- type constructor that constructs the successor of another natural number
-- Some numbers shortcuts
type One = S Zero
type Two = S One
type Three = S Two
type Four = S Three
type Five = S Four
type Six = S Five
type Seven = S Six
type Eight = S Seven

The algorithm I adapted makes additions and subtractions on naturals, so I had to reinvent these as well. Functions at the type level are defined with resort to type classes. This requires the extensions for multiple parameter type classes and functional dependencies. Type classes cannot "return values", so we use an extra parameter for that, in a manner similar to PROLOG.
class Add a b r | a b -> r -- last param is the result
instance Add Zero b b                     -- 0 + b = b
instance (Add a b r) => Add (S a) b (S r) -- S(a) + b = S(a + b)

class Sub a b r | a b -> r
instance Sub a Zero a                     -- a - 0 = a
instance (Sub a b r) => Sub (S a) (S b) r -- S(a) - S(b) = a - b

Recursion is implemented with class assertions, so the syntax looks a bit backward.
Next up were booleans:
data True  -- type that represents truth
data False -- type that represents falsehood

And a function to do inequality comparisons:
class NotEq a b r | a b -> r
instance NotEq Zero Zero False                -- 0 /= 0 = False
instance NotEq (S a) Zero True                -- S(a) /= 0 = True
instance NotEq Zero (S a) True                -- 0 /= S(a) = True
instance (NotEq a b r) => NotEq (S a) (S b) r -- S(a) /= S(b) = a /= b

And lists...
data Nil
data h ::: t
infixr 0 :::

class Append xs ys r | xs ys -> r
instance Append Nil ys ys                                       -- [] ++ _ = []
instance (Append xs ys rec) => Append (x ::: xs) ys (x ::: rec) -- (x:xs) ++ ys = x:(xs ++ ys)

class Concat xs r | xs -> r
instance Concat Nil Nil                                         -- concat [] = []
instance (Concat xs rec, Append x rec r) => Concat (x ::: xs) r -- concat (x:xs) = x ++ concat xs

class And l r | l -> r
instance And Nil True                    -- and [] = True
instance And (False ::: t) False         -- and (False:_) = False
instance (And t r) => And (True ::: t) r -- and (True:t) = and t

ifs are also missing at the type level...
class Cond c t e r | c t e -> r
instance Cond True t e t  -- cond True t _ = t
instance Cond False t e e -- cond False _ e = e

And with that, all the supporting machinery I used was in place. Time to tackle the problem itself!
Starting with a function to test if adding a queen to an existing board is ok:
-- Testing if it's safe to add a queen
class Safe x b n r | x b n -> r
instance Safe x Nil n True    -- safe x [] n = True
instance (Safe x y (S n) rec,
          Add c n cpn, Sub c n cmn,
          NotEq x c c1, NotEq x cpn c2, NotEq x cmn c3,
          And (c1 ::: c2 ::: c3 ::: rec ::: Nil) r) => Safe x (c ::: y) n r
    -- safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]

Notice the use of class assertions to obtain intermediate results. Because the return values are actually an extra parameter, we can't just call the assertions directly from each other. Again, if you've used PROLOG before you may find this style a bit familiar.
After I made a few changes to remove the need for lambdas (which I could have implemented, but I decided to leave for another day), this is what the original solution looked like:
queens 0 = [[]]
-- The original used the list monad. I "unrolled" bind into concat & map.
queens n = concat $ map f $ queens (n-1)
g y x = if safe x y 1 then [x:y] else []
f y = concat $ map (g y) [1..8]

map is a higher order function. I thought implementing higher order meta-functions would be too much hassle (again the lambdas) so I just went with a simpler solution: since I know what functions will be mapped, I can implement specialized versions of map for each, so that those are not higher-order functions.
-- Auxiliary meta-functions
class G y x r | y x -> r
instance (Safe x y One s, Cond s ((x ::: y) ::: Nil) Nil r) => G y x r

class MapG y l r | y l -> r
instance MapG y Nil Nil
instance (MapG y xs rec, G y x g) => MapG y (x ::: xs) (g ::: rec)

-- Shortcut for [1..8]
type OneToEight = One ::: Two ::: Three ::: Four ::: Five ::: Six ::: Seven ::: Eight ::: Nil

class F y r | y -> r
instance (MapG y OneToEight m, Concat m r) => F y r -- f y = concat $ map (g y) [1..8]

class MapF l r | l -> r
instance MapF Nil Nil
instance (MapF xs rec, F x f) => MapF (x ::: xs) (f ::: rec)

And the last meta-function can be written now:
class Queens n r | n -> r
instance Queens Zero (Nil ::: Nil)
instance (Queens n rec, MapF rec m, Concat m r) => Queens (S n) r

All that's left is some kind of driver to coax the type-checking machinery to work out the solutions.
-- dummy value of type Eight
eight = undefined :: Eight
-- dummy function that asserts the Queens class
queens :: Queens n r => n -> r
queens = const undefined

This meta-program is supposed to run on the type checker, so one can fire up ghci and ask for the type of queens eight:
> :t queens eight

This will exceed the default recursion limit rather fast (it's a measly 20). To increase this limit, we need to invoke ghci with the -fcontext-stack=N option, where N is the desired stack depth (N=1000 and fifteen minutes is not enough). I haven't seen this run to completion yet, as it takes a very long time, but I've managed to run up to queens four.
There's a full program on ideone with some machinery for pretty printing the result types, but there only queens two can run without exceeding the limits :(

Besides an interesting solution, this is a fun reference to what can be done with class/instance logic

C, via the preprocessor
I think the ANSI committee made a conscious choice not to extend the C preprocessor to the point of being Turing-complete. In any case, it's not really powerful enough to solve the eight queens problem. Not in any sort of general fashion.
But it can be done, if you're willing to hard-code the loop counters. There's no real way to loop, of course, but you can use self-inclusion (via #include __FILE__) to get a limited sort of recursion.
#ifdef i
# if (r_(i) & 1 << j_(i)) == 0 && (p_(i) & 1 << i + j_(i)) == 0 \
                               && (n_(i) & 1 << 7 + i - j_(i)) == 0
#  if i == 0
#   undef i
#   define i 1
#   undef r1
#   undef p1
#   undef n1
#   define r1 (r0 | (1 << j0))
#   define p1 (p0 | (1 << j0))
#   define n1 (n0 | (1 << 7 - j0))
#   undef j1
#   define j1 0
#   include __FILE__
#   undef j1
#   define j1 1
#   include __FILE__
#   undef j1
#   define j1 2
#   include __FILE__
#   undef j1
#   define j1 3
#   include __FILE__
#   undef j1
#   define j1 4
#   include __FILE__
#   undef j1
#   define j1 5
#   include __FILE__
#   undef j1
#   define j1 6
#   include __FILE__
#   undef j1
#   define j1 7
#   include __FILE__
#   undef i
#   define i 0
#  elif i == 1
#   undef i
#   define i 2
#   undef r2
#   undef p2
#   undef n2
#   define r2 (r1 | (1 << j1))
#   define p2 (p1 | (1 << 1 + j1))
#   define n2 (n1 | (1 << 8 - j1))
#   undef j2
#   define j2 0
#   include __FILE__
#   undef j2
#   define j2 1
#   include __FILE__
#   undef j2
#   define j2 2
#   include __FILE__
#   undef j2
#   define j2 3
#   include __FILE__
#   undef j2
#   define j2 4
#   include __FILE__
#   undef j2
#   define j2 5
#   include __FILE__
#   undef j2
#   define j2 6
#   include __FILE__
#   undef j2
#   define j2 7
#   include __FILE__
#   undef i
#   define i 1
#  elif i == 2
#   undef i
#   define i 3
#   undef r3
#   undef p3
#   undef n3
#   define r3 (r2 | (1 << j2))
#   define p3 (p2 | (1 << 2 + j2))
#   define n3 (n2 | (1 << 9 - j2))
#   undef j3
#   define j3 0
#   include __FILE__
#   undef j3
#   define j3 1
#   include __FILE__
#   undef j3
#   define j3 2
#   include __FILE__
#   undef j3
#   define j3 3
#   include __FILE__
#   undef j3
#   define j3 4
#   include __FILE__
#   undef j3
#   define j3 5
#   include __FILE__
#   undef j3
#   define j3 6
#   include __FILE__
#   undef j3
#   define j3 7
#   include __FILE__
#   undef i
#   define i 2
#  elif i == 3
#   undef i
#   define i 4
#   undef r4
#   undef p4
#   undef n4
#   define r4 (r3 | (1 << j3))
#   define p4 (p3 | (1 << 3 + j3))
#   define n4 (n3 | (1 << 10 - j3))
#   undef j4
#   define j4 0
#   include __FILE__
#   undef j4
#   define j4 1
#   include __FILE__
#   undef j4
#   define j4 2
#   include __FILE__
#   undef j4
#   define j4 3
#   include __FILE__
#   undef j4
#   define j4 4
#   include __FILE__
#   undef j4
#   define j4 5
#   include __FILE__
#   undef j4
#   define j4 6
#   include __FILE__
#   undef j4
#   define j4 7
#   include __FILE__
#   undef i
#   define i 3
#  elif i == 4
#   undef i
#   define i 5
#   undef r5
#   undef p5
#   undef n5
#   define r5 (r4 | (1 << j4))
#   define p5 (p4 | (1 << 4 + j4))
#   define n5 (n4 | (1 << 11 - j4))
#   undef j5
#   define j5 0
#   include __FILE__
#   undef j5
#   define j5 1
#   include __FILE__
#   undef j5
#   define j5 2
#   include __FILE__
#   undef j5
#   define j5 3
#   include __FILE__
#   undef j5
#   define j5 4
#   include __FILE__
#   undef j5
#   define j5 5
#   include __FILE__
#   undef j5
#   define j5 6
#   include __FILE__
#   undef j5
#   define j5 7
#   include __FILE__
#   undef i
#   define i 4
#  elif i == 5
#   undef i
#   define i 6
#   undef r6
#   undef p6
#   undef n6
#   define r6 (r5 | (1 << j5))
#   define p6 (p5 | (1 << 5 + j5))
#   define n6 (n5 | (1 << 12 - j5))
#   undef j6
#   define j6 0
#   include __FILE__
#   undef j6
#   define j6 1
#   include __FILE__
#   undef j6
#   define j6 2
#   include __FILE__
#   undef j6
#   define j6 3
#   include __FILE__
#   undef j6
#   define j6 4
#   include __FILE__
#   undef j6
#   define j6 5
#   include __FILE__
#   undef j6
#   define j6 6
#   include __FILE__
#   undef j6
#   define j6 7
#   include __FILE__
#   undef i
#   define i 5
#  elif i == 6
#   undef i
#   define i 7
#   undef r7
#   undef p7
#   undef n7
#   define r7 (r6 | (1 << j6))
#   define p7 (p6 | (1 << 6 + j6))
#   define n7 (n6 | (1 << 13 - j6))
#   undef j7
#   define j7 0
#   include __FILE__
#   undef j7
#   define j7 1
#   include __FILE__
#   undef j7
#   define j7 2
#   include __FILE__
#   undef j7
#   define j7 3
#   include __FILE__
#   undef j7
#   define j7 4
#   include __FILE__
#   undef j7
#   define j7 5
#   include __FILE__
#   undef j7
#   define j7 6
#   include __FILE__
#   undef j7
#   define j7 7
#   include __FILE__
#   undef i
#   define i 6
#  elif i == 7
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           j0 + 1, j1 + 1, j2 + 1, j3 + 1, j4 + 1, j5 + 1, j6 + 1, j7 + 1);
#  endif
# endif
#else
#include <stdio.h>
#define _cat(a, b) a ## b
#define j_(i) _cat(j, i)
#define n_(i) _cat(n, i)
#define p_(i) _cat(p, i)
#define r_(i) _cat(r, i)
int main(void)
{
# define i 0
# define j0 0
# include __FILE__
# undef j0
# define j0 1
# include __FILE__
# undef j0
# define j0 2
# include __FILE__
# undef j0
# define j0 3
# include __FILE__
# undef j0
# define j0 4
# include __FILE__
# undef j0
# define j0 5
# include __FILE__
# undef j0
# define j0 6
# include __FILE__
# undef j0
# define j0 7
# include __FILE__
# undef j0
    return 0;
}
#endif

Despite the horrific amount of repetitive content, let me assure you that it truly is solving the eight queens problem algorithmically. Unfortunately the one thing that I couldn't do with the preprocessor is implement a general push-down stack data structure. The upshot is that I had to hard-code the value of i wherever it was used to select another value to set. (As opposed to retrieving values, which could be done completely generally. That's why the #if at the top of the file, which is what decides if a queen can be added at the current position, didn't need to be repeated eight times.)
Within the preprocessor code, i and j indicate the current position being considered, while r, p, and n keep track of which ranks and diagonals are currently unavailable for placement. However, i also doubles as the counter marking the current depth of recursion, so really all the other values actually use i as a sort of subscript, so that their values are preserved when resuming from a recursion. (And also because of the serious difficulty of modifying the value of a preprocessor symbol without completely replacing it.)
The compiled program prints all 92 solutions. The solutions are embedded directly into the executable; the preprocessor output looks like this:
/* ... #included content from <stdio.h> ... */
int main(void)
{
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           0 + 1, 4 + 1, 7 + 1, 5 + 1, 2 + 1, 6 + 1, 1 + 1, 3 + 1);
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           0 + 1, 5 + 1, 7 + 1, 2 + 1, 6 + 1, 3 + 1, 1 + 1, 4 + 1);
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           0 + 1, 6 + 1, 3 + 1, 5 + 1, 7 + 1, 1 + 1, 4 + 1, 2 + 1);
    /* ... 88 more solutions ... */
    printf("(1 %d) (2 %d) (3 %d) (4 %d) (5 %d) (6 %d) (7 %d) (8 %d)\n",
           7 + 1, 3 + 1, 0 + 1, 2 + 1, 5 + 1, 1 + 1, 6 + 1, 4 + 1);
    return 0;
}

It can be done, even though it clearly shouldn't.

Here's a C++11 solution without any templates:
constexpr int trypos(
    int work, int col, int row, int rows, int diags1, int diags2,
    int rowbit, int diag1bit, int diag2bit);

constexpr int place(
    int result, int work, int col, int row, int rows, int diags1, int diags2)
{
    return result != 0 ? result
        : col == 8 ? work
        : row == 8 ? 0
        : trypos(work, col, row, rows, diags1, diags2,
                 1 << row, 1 << (7 + col - row), 1 << (14 - col - row));
}

constexpr int trypos(
    int work, int col, int row, int rows, int diags1, int diags2,
    int rowbit, int diag1bit, int diag2bit)
{
    return !(rows & rowbit) && !(diags1 & diag1bit) && !(diags2 & diag2bit)
        ? place(
            place(0, work*10 + 8-row, col + 1, 0,
                  rows | rowbit, diags1 | diag1bit, diags2 | diag2bit),
            work, col, row + 1, rows, diags1, diags2)
        : place(0, work, col, row + 1, rows, diags1, diags2);
}

int places = place(0, 0, 0, 0, 0, 0, 0);

The solution is encoded as decimal digits, as in FredOverflow's answers.  GCC 4.7.1 compiles the above file into the following assembly source with g++ -S -std=c++11 8q.cpp:
    .file   "8q.cpp"
    .globl  places
    .data
    .align 4
    .type   places, @object
    .size   places, 4
places:
    .long   84136275
    .ident  "GCC: (GNU) 4.7.1"
    .section    .note.GNU-stack,"",@progbits

The value of the symbol places is 84136275, i.e. the first queen is at a8, the second at b4 etc.

c++ template, with only one template class is defined:
template <int N, int mask, int mask2, int mask3, int remainDigit, bool fail>
struct EQ;

template <int N, int mask, int mask2, int mask3>
struct EQ<N, mask, mask2, mask3, 0, false> {
    enum _ { Output = (char [N])1 };
};

template <int N, int mask, int mask2, int mask3, int i>
struct EQ<N, mask, mask2, mask3, i, true> { };

template <int N, int mask, int mask2, int mask3, int i>
struct EQ<N, mask, mask2, mask3, i, false> {
    enum _ { _ =
             sizeof(EQ<N*10+1, mask|(1<<1), mask2|(1<<(1+i)), mask3|(1<<(1+8-i)), i-1,
               (bool)(mask&(1<<1)) || (bool)(mask2&(1<<(1+i))) || (bool)(mask3&(1<<(1+8-i)))>) +
             sizeof(EQ<N*10+2, mask|(1<<2), mask2|(1<<(2+i)), mask3|(1<<(2+8-i)), i-1,
               (bool)(mask&(1<<2)) || (bool)(mask2&(1<<(2+i))) || (bool)(mask3&(1<<(2+8-i)))>) +
             sizeof(EQ<N*10+3, mask|(1<<3), mask2|(1<<(3+i)), mask3|(1<<(3+8-i)), i-1,
               (bool)(mask&(1<<3)) || (bool)(mask2&(1<<(3+i))) || (bool)(mask3&(1<<(3+8-i)))>) +
             sizeof(EQ<N*10+4, mask|(1<<4), mask2|(1<<(4+i)), mask3|(1<<(4+8-i)), i-1,
               (bool)(mask&(1<<4)) || (bool)(mask2&(1<<(4+i))) || (bool)(mask3&(1<<(4+8-i)))>) +
             sizeof(EQ<N*10+5, mask|(1<<5), mask2|(1<<(5+i)), mask3|(1<<(5+8-i)), i-1,
               (bool)(mask&(1<<5)) || (bool)(mask2&(1<<(5+i))) || (bool)(mask3&(1<<(5+8-i)))>) +
             sizeof(EQ<N*10+6, mask|(1<<6), mask2|(1<<(6+i)), mask3|(1<<(6+8-i)), i-1,
               (bool)(mask&(1<<6)) || (bool)(mask2&(1<<(6+i))) || (bool)(mask3&(1<<(6+8-i)))>) +
             sizeof(EQ<N*10+7, mask|(1<<7), mask2|(1<<(7+i)), mask3|(1<<(7+8-i)), i-1,
               (bool)(mask&(1<<7)) || (bool)(mask2&(1<<(7+i))) || (bool)(mask3&(1<<(7+8-i)))>) +
             sizeof(EQ<N*10+8, mask|(1<<8), mask2|(1<<(8+i)), mask3|(1<<(8+8-i)), i-1,
               (bool)(mask&(1<<8)) || (bool)(mask2&(1<<(8+i))) || (bool)(mask3&(1<<(8+8-i)))>)};
};
int main(int argc, _TCHAR* argv[])
{
    // output all solutions to eight queens problems as error messages
    sizeof(EQ<0, 0, 0, 0, 8, false>);
    return 0;
}

so the error message will be looked like:
error C2440: 'type cast' : cannot convert from 'int' to 'char [15863724]'