text:
Implement PCRE in your language.

Note: After trying this myself, I soon realized what a mistake this was. Therfore, I am modifying the rules a bit.

The minimum required functionality:

Character classes (., \w, \W, etc.)
Multipliers (+, *, and ?)
Simple capture groups

Your challenge is to implement PCRE in the language of your choice subject to the following conditions:

You may not use your language's native RegEx facilities in any way. You may not use a 3rd party RegEx library either.
Your entry should implement as much of the PCRE spec. as possible.
Your program should accept as input, 2 lines:

the regular expression
the string input to match against

Your program should indicate in its output:

Whether the RegEx matched anywhere in the input string
The results of any capturing groups

The winner shall be the entry that implements as much of the spec. as possible. In case of a tie, the winner shall be the most creative entry, as judged by me.

Edit: to clarify a few things, here are some examples of input and expected output:

Input:

^\s*(\w+)$
         hello

Output:

Matches: yes
Group 1: 'hello'

Input:

(\w+)@(\w+)(?:\.com|\.net)
sam@test.net

Output:

Matches: yes
Group 1: 'sam'
Group 2: 'test'

That's a really challenging challenge, given the amount of features in PCRE. Recursion, backtracking, lookahead/assertions, unicode, conditional subpatterns, ...

See PCRE docs; PERL RE; PHP PCRE docs are great too.

@user300: The goal is to implement as much as possible. Obviously everything would be a little too hard.

@George: How about you list the features you want and give some test cases, just so that we're all on even ground.

@Marko: Is that better?

@George: I think @Marko was after specific features, or rather, the minimal subset you'd want to people to implement first. On the whole, though, PCRE is really way too hard a challenge for a casual coding competition. I suggest changing this to a very small, specific RE subset, and make the challenge to implement.

@Mtn: You're right. I've edited the question now.

@George, why not just ask for POSIX regexes instead? That roughly corresponds to your minimum subset.

Awesome task. Click. Whirrrrr. Working...

@Jonathan: I'm guessing it was harder than it seemed?

I think the part with the groups is pretty complicated. I have given a little thought and had trouble identifying characters inside groups inside groups inside groups (as in Inception).

Actually, I have a good chunk working, just need to clean it up a bit and finish the \w part. Got distracted back to working on 'paying' software. Plus the baby is a lot more active, and it's really hard to program with a noisy baby ;-) Wouldn't have it any other way.

@JonathanWatmough (3 years later) Still waiting... ;-)

Python
Since implementing full PCRE is too much I implemented only an essential subset of it.
Supports |.\.\w\W\s+*(). Input regexp must be correct.
Examples:
$ python regexp.py
^\s*(\w+)$
   hello
Matches:     hello
Group 1 hello

$ python regexp.py
(a*)+
infinite loop

$ python regexp.py
(\w+)@(\w+)(\.com|\.net)
sam@test.net
Matches:  sam@test.net
Group 1 sam
Group 2 test
Group 3 .net

How it works:
For detailed theory read this Introduction to Automata Theory, Languages, and Computation.
The idea is to convert the original regular expression into a nondeterminist finite automata (NFA). Actually, PCRE regular expressions are at least context free grammars for which we need push-down automata, but we'll limit ourselves to a subset of PCRE.
Finite automatas are directed graphs in which nodes are states, edges are transitions and each transition has a matching input. Initially you start from a start node, predefined. Whenever you receive an input that matches one of the transition you take that transition  to a new state. If you reached a terminal node it is called that automata accepted input. In our case input is a matching function that returns true.
They are called nondeterminist automata because sometimes there are more matching transitions that you can take from the same state. In my implementation all transition to the same state must match the same thing, so I stored the matching function together with the destination state (states[dest][0]).
We transform our regexp to a finite automata using building blocks. A building block has a start node (first) and an end node (last) and matches something from the text (possible empty string).
The simplest examples include

matching nothing: True (first == last)
matching a character: c == txt[pos] (first == last)
matching end of string: pos == len(txt)(first == last`)

You will also need the new position in text where to match next token.
More complicated examples are (capital letters stand for blocks).

matching B+:

create nodes: u, v (matching nothing)
create transitions: u -> B.first, B.last -> v, v -> u
when you get to node v you already matched B. Then you have two options: go further, or try to match B again.

matching A|B|C:

create nodes: u, v (matching nothing)
create transitions: u -> A.first, u -> C.first, u -> C.first,
create transitions: A->last -> v, B->last -> v, C->last -> v,
from u you can go to any block

All regexp operators can be transformed like this. Just give a try for *.
The last part is to parse the regexp which requires a very simple grammar:
 or: seq ('|' seq)*
 seq: empty
 seq: atom seq
 seq: paran seq
 paran: '(' or ')'

Hopefully implementing a simple grammar (I think is LL(1), but correct me if I'm wrong) is much easier than building an NFA.
Once you have the NFA you need to backtrack until you reach terminal node.
Source code (or here):
from functools import *

WORDCHAR = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890_'

def match_nothing(txt, pos):
  return True, pos

def match_character(c, txt, pos):
  return pos < len(txt) and txt[pos] == c, pos + 1

def match_space(txt, pos):
  return pos < len(txt) and txt[pos].isspace(), pos + 1

def match_word(txt, pos):
  return pos < len(txt) and txt[pos] in WORDCHAR, pos + 1

def match_nonword(txt, pos):
  return pos < len(txt) and txt[pos] not in WORDCHAR, pos + 1

def match_dot(txt, pos):
  return pos < len(txt), pos + 1

def match_start(txt, pos):
  return pos == 0, pos

def match_end(txt, pos):
  return pos == len(txt), pos

def create_state(states, match=None, last=None, next=None, name=None):
  if next is None: next = []
  if match is None: match = match_nothing

  state = len(states)
  states[state] = (match, next, name)
  if last is not None:
    states[last][1].append(state)

  return state

def compile_or(states, last, regexp, pos):
  mfirst = create_state(states, last=last, name='or_first')
  mlast = create_state(states, name='or_last')

  while True:
    pos, first, last = compile_seq(states, mfirst, regexp, pos)
    states[last][1].append(mlast)
    if pos != len(regexp) and regexp[pos] == '|':
      pos += 1
    else:
      assert pos == len(regexp) or regexp[pos] == ')'
      break

  return pos, mfirst, mlast

def compile_paren(states, last, regexp, pos):
  states.setdefault(-2, [])   # stores indexes
  states.setdefault(-1, [])   # stores text

  group = len(states[-1])
  states[-2].append(None)
  states[-1].append(None)

  def match_pfirst(txt, pos):
    states[-2][group] = pos
    return True, pos

  def match_plast(txt, pos):
    old = states[-2][group]
    states[-1][group] = txt[old:pos]
    return True, pos

  mfirst = create_state(states, match=match_pfirst, last=last, name='paren_first')
  mlast = create_state(states, match=match_plast, name='paren_last')

  pos, first, last = compile_or(states, mfirst, regexp, pos)
  assert regexp[pos] == ')'

  states[last][1].append(mlast)
  return pos + 1, mfirst, mlast

def compile_seq(states, last, regexp, pos):
  first = create_state(states, last=last, name='seq')
  last = first

  while pos < len(regexp):
    p = regexp[pos]
    if p == '\\':
      pos += 1
      p += regexp[pos]

    if p in '|)':
      break

    elif p == '(':
      pos, first, last = compile_paren(states, last, regexp, pos + 1)

    elif p in '+*':
      # first -> u ->...-> last -> v -> t
      # v -> first (matches at least once)
      # first -> t (skip on *)
      # u becomes new first
      # first is inserted before u

      u = create_state(states)
      v = create_state(states, next=[first])
      t = create_state(states, last=v)

      states[last][1].append(v)
      states[u] = states[first]
      states[first] = (match_nothing, [[u], [u, t]][p == '*'])

      last = t
      pos += 1

    else:  # simple states
      if p == '^':
    state = create_state(states, match=match_start, last=last, name='begin')
      elif p == '$':
    state = create_state(states, match=match_end, last=last, name='end')
      elif p == '.':
    state = create_state(states, match=match_dot, last=last, name='dot')
      elif p == '\\.':
    state = create_state(states, match=partial(match_character, '.'), last=last, name='dot')
      elif p == '\\s':
    state = create_state(states, match=match_space, last=last, name='space')
      elif p == '\\w':
    state = create_state(states, match=match_word, last=last, name='word')
      elif p == '\\W':
    state = create_state(states, match=match_nonword, last=last, name='nonword')
      elif p.isalnum() or p in '_@':
    state = create_state(states, match=partial(match_character, p), last=last, name='char_' + p)
      else:
    assert False

      first, last = state, state
      pos += 1

  return pos, first, last

def compile(regexp):
  states = {}
  pos, first, last = compile_or(states, create_state(states, name='root'), regexp, 0)
  assert pos == len(regexp)
  return states, last

def backtrack(states, last, string, start=None):
  if start is None:
    for i in range(len(string)):
      if backtrack(states, last, string, i):
    return True
    return False

  stack = [[0, 0, start]]   # state, pos in next, pos in text
  while stack:
    state = stack[-1][0]
    pos = stack[-1][2]
    #print 'in state', state, states[state]

    if state == last:
      print 'Matches: ', string[start:pos]
      for i in xrange(len(states[-1])):
    print 'Group', i + 1, states[-1][i]
      return True

    while stack[-1][1] < len(states[state][1]):
      nstate = states[state][1][stack[-1][1]]
      stack[-1][1] += 1

      ok, npos = states[nstate][0](string, pos)
      if ok:
    stack.append([nstate, 0, npos])
    break
      else:
    pass
    #print 'not matched', states[nstate][2]
    else:
      stack.pop()

  return False

# regexp = '(\\w+)@(\\w+)(\\.com|\\.net)'
# string = 'sam@test.net'
regexp = raw_input()
string = raw_input()

states, last = compile(regexp)
backtrack(states, last, string)

+1 Wow... I tried to do this myself with PHP and utterly failed.

TIL (a+b)+ matches abaabaaabaaaab.


text:
My Word can beat up your Word
PROBLEM
Given two words, find the winner in a digital root battle.
Define the digital root of a word this way:

Each letter of the alphabet is assigned a number:  A = 1, B = 2, C = 3, ..., Z = 26
Add the values for each letter to total the word. Take "CAT", for example. C+A+T = 3+1+20 = 24
Add all the single digits that make up that result: 24 => 2 + 4 = 6
Repeat step #3 until you reach a single digit. That single digit is the digital root of the word.

Rules:

A winner is declared if its digital root is larger than the other.
If the digital root values are equal, shorten the words by removing every instance of the highest value letter from both words and recalculating.
Repeat steps #1 and #2 until there is a winner or one of the words has only a single letter (or no letters) remaining.
If the digital root values are equal after going through the shortening process, the longer word is declared the winner.
If the words are of equal length and no winner is found after going through the shortening process, no winner is declared.

Special rules:

No use of modulus is allowed in the calculation of the digital root itself. It can be used anywhere else.
Assume words will consist only of uppercase letters - no punctuation, no spaces, etc.

INPUT
Pull the words in through stdin (comma-separated). method parameters, or however you want. Make it clear in your solution or the code how the words are parsed or prepared.
OUTPUT
Display the winning word. If there is no winner, display "STALEMATE".
Examples:
intput: CAN,BAT
CAN = 18 = 9
BAT = 23 = 5

output: CAN
intput: ZOO,NO
ZOO = 56 = 11 = 2
NO = 29 = 11 = 2

OO = 30 = 3
N = 14 = 5

output: NO
UPDATE: Input must be read using stdin with the words as a comma-separated string.
UPDATE: Added a couple examples to test against.
UPDATE: clarified the removal of the highest valued letter in the case of a tie - this also alters slightly the stop condition as well - if a word is one letter or zero letters long, the shortening process is stopped

You should decide on the input, not leave it to choice, as it makes a huge difference in the programs. By picking an input method, and specing it, you remove "creative interpretations", and make a challenge that is equal for all.

@MtnViewMark - Understood, but effectively I'm trying to remove the reading of the input from the character count. I'm not interested in the most clever or shortest way to read in the two words. Requiring a specific method also handicaps certain languages - I guess I'm just trying to get at the meat of the problem.

@Steve - Then you shouldn't specify the output as "display" either, yes? However, I think you are perhaps eliminating too much from the problem. A clever and short golf often stems from combining different aspects of the problem in tricky ways, for example folding some of the processing into the input or output. As for handicapping languages -- pretty much all of them can read stdin and write stdout.

@MtnViewMark - Fair point. I'll make a simple update and clear it up. My language of choice just has a lengthy way of reading from stdin, so I get biased. :)

Does taking the input an argument to main count as being from stdin? Oh, and generally, if you want to keep the requirements down on stray stuff like reading from stdin and having to import or include other modules or files, making the puzzle require a function rather than a whole program would probbaly be the best way to go.

It would probably be a good idea to add some examples too, so that there are values to test against.

@Jonathan - That was my intent without explicitly stating it (requiring a function/method) - my fault. I'll be clearer next time. For now, assume a full program is required. I also added some simple examples to test against.

Oh. floccinaucinihilipilification

@Steve: If the word BANANA ties another word, does it become BAANA or BAAA?

@Eelvex - my intent was that it becomes "BAAA" - post should have read "by removing every instance of the highest value letter".

It would really help to see a more comprehensive set of test vectors. In particular, it would be good to have test vectors that prove that code is correctly shortening BANANA to BAAA, not BAANA (as I thought you meant prior to your clarification). I wonder how many submitted solutions get that right - since it complicates things significantly (which is fine, just subtle).

The problem never states that only two words will be supplied; is this given? Oh, and Rules #2/#3 are the suck :)

I couldn't be bothered to put this on EVERY entry, so here's a tip for anyone who sees this: if you have "-64" anywhere in your code to convert ascii codes, you can save yourself a character and make it "-1", since that's what it will work out to anyway!

Would subtracting nine from the total value until it's less than ten be considered "using a modulus"?

J, 100
z=:"."0@":@(+/)^:9@(64-~a.i.])@(#~' '&i.)"1
f=:*@-/"2@(z@((]#~]i.~{.@\:~)"1^:([:=/z))){'STALEMATE'&,

runs like this:
f 'NO',:'ZOO'
NO
f 'CAN',:'BAT'
CAN
f 'FAT',:'BANANA'
FAT
f 'ONE',:'ONE'
STALEMATE

it doesn't yet accept input exactly as asked.

APL (Dyalog) (91 86)
⎕ML←3⋄{Z≡∪Z←{2>⍴⍕⍵:⍵⋄∇+/⍎¨⍕⍵}¨+/¨⎕A∘⍳¨⍵:G[↑⍒Z]⋄1∊↑¨⍴¨⍵:'STALEMATE'⋄∇1∘↓¨⍵}G←Z⊂⍨','≠Z←⍞

Explanation (in order of execution):

⎕ML←3: set ML to 3 (this makes ⊂ mean partition, among other things).
G←Z⊂⍨','≠Z←⍞: read input, separate by commas, store in G and pass to the function.
+/¨⎕A∘⍳¨⍵: calculate the score for each word. (⎕A is a list containing the alphabet.)
Z←{2>⍴⍕⍵:⍵⋄∇+/⍎¨⍕⍵}¨: calculate the digital root for each score (by summing all digits as long as there is still more than one digit) and store them in Z.
Z≡∪Z: if all scores are unique...
:G[↑⍒Z]: ...then output the word with the highest score (from the original list).
⋄1∊↑¨⍴¨⍵:'STALEMATE': otherwise (if there's a tie), if one of the words is of length 1, output STALEMATE.
⋄∇1∘↓¨⍵: otherwise, take the first letter off each word and run the function again.

Ruby - 210
d,e=(a,b=$<.read.chop.split(/,/)).map{|w|w.bytes.sort}
r=->w,o=65{n=0;w.map{|c|n+=c-o};n>9?r[n.to_s.bytes,48]:n}
d.pop&e.pop while r[d]==r[e]&&d[1]&&e[1]
$><<[[:STALEMATE,a,b][a.size<=>b.size],a,b][r[d]<=>r[e]]

Tests:
$ ruby1.9 1128.rb <<< CAN,BAT
CAN

$ ruby1.9 1128.rb <<< ZOO,NO
NO

$ ruby1.9 1128.rb <<< ZOO,ZOO
STALEMATE

First line can be shortened to d,e=(a,b=gets.split ?,).map{|w|w.bytes.sort}.

Why not shorten this further by using some other word to denote a tie? i.e. "TIE" vs. "STALEMATE"

@Gaffi because the spec requires that the word "STALEMATE" be used.

@chron Shame on me, I stopped reading at "If the words are of equal length and no winner is found after going through the shortening process, no winner is declared."

Haskell, 205 characters
import List
s b=d.sum.map((-b+).fromEnum)
d q|q<10=q|1<3=s 48$show q
f=map(s 64.concat).tails.group.reverse.sort
w(a,_:b)=f a#f b where x#y|x<y=b|x>y=a|1<3="STALEMATE"
main=getLine>>=putStrLn.w.span(/=',')

Sample runs:
> ghc --make WordVsWord.hs
[1 of 1] Compiling Main             ( WordVsWord.hs, WordVsWord.o )
Linking WordVsWord ...

> ./WordVsWord <<< CAN,BAT
CAN

> ./WordVsWord <<< ZOO,NO
NO

> ./WordVsWord <<< FAT,BANANA
FAT

> ./WordVsWord <<< ONE,ONE
STALEMATE

Edit: (227 -> 219) better picking of winner, shortened pattern match in w, imported older, shorter module
Edit: (219 -> 208) Incorporate JB's suggestions
Edit: (208 -> 205) handle negative numbers, exploiting odd rules in Haskell about hyphen

Using straight list comparison is a very nice touch.  A few suggested "at-a-glance" improvements: ',':b→_:b (-2), if you're not too attached to multiline processing interact$unlines.map([...]).lines→putStr.[...]=<<getLine (-11), if you allow yourself to lax output putStr→print (-1).  I hate those negation operation taking so many chars, but can't find a way around it.

Thanks, JB! I incorporated most of suggestions. I felt the output should follow the spec, in particular end with a newline. But I'd be willing to save those two characters if it got close! :-)

Good job with the subtractions!

Perl, 224 225 229
Basic golfing (nothing smart yet):
split",",<>;$_=[sort map-64+ord,/./g]for@a=@_;{for(@b=@a
){while($#$_){$s=0;$s+=$_ for@$_;$_=[$s=~/./g]}}($a,$b)=
map$$_[0],@b;if($a==$b){pop@$_ for@a;@{$a[1]}*@{$a[0]}&&
redo}}say+("STALEMATE",@_)[$a<=>$b||@{$a[0]}<=>@{$a[1]}]

Perl 5.10 and above, run with perl -M5.010 <file> or perl -E '<code here>'
$ perl -M5.010 word.pl <<<CAN,BAT
CAN
$ perl -M5.010 word.pl <<<ZOO,NO
NO

$ perl -M5.010 word.pl <<<NO,ON
STALEMATE

VBA (242 462)
Function s(q,Optional l=0)
s=-1:t=Split(q,","):r=t:m=t
For j=0 To 1
m(j)=0:w=t(j)
While Len(w)>1 Or Not IsNumeric(w)
b=0
For i=1 To Len(w)
a=Mid(w,i,1):a=IIf(IsNumeric(a),a,Asc(a)-64):b=b+a
If m(j)+0<a+0 Then m(j)=a
Next
w=b
Wend
r(j)=b
Next
s=IIf(r(0)>r(1),0,IIf(r(0)<r(1),1,s))
For j=0 To 1
r(j)=Replace(t(j),Chr(m(j)+64),"",,1)
Next
If s<0 And Len(t(0))+Len(t(1))>2 Then s=s(r(0) & "," & r(1),1)
If l=0 Then If s>=0 Then s=t(s) Else s="STALEMATE"
End Function

Turns out the below code didn't match the spec, so I had to re-work, adding much length (see above). :-/ This may be able to be golfed further, but it's already pretty compact and I doubt I'll be able to bring it back down to a competitive score.
The original (below) did not remove the highest-valued letter from the words when there was a tie.
Sub s(q)
t=Split(q,",")
r=t
For j=0 To 1
w=t(j):b=0
For i=1 To Len(w)
b=b+Asc(Mid(w,i,1))-64
Next
While Len(b)>1
d=0
For i=1 To Len(b)
d=d+Mid(b,i,1)
Next
b=d
Wend
r(j)=b
Next
MsgBox IIf(r(0)>r(1),t(0),IIf(r(0)<r(1),t(1),"STALEMATE"))
End Sub

K, 106
{a::x;@[{$[(>). m:{+/"I"$'$+/@[;x].Q.A!1+!26}'x;a 0;(<). m;a 1;.z.s 1_'x@'>:'x]};x;"STALEMATE"]}[","\:0:0]

Uses exception handling to catch stack errors, which result in cases of stalemate.

This really took my fancy and is my first post. Although it is old I noticed no one had done a php version so here is mine.
<?php $f='CAN,CBN';$w=explode(',',$f);$a=$ao=$w[0];$b=$bo=$w[1];$c='';
function splice($a,$t){$s=$h=0;$y=array();$x=str_split($a);
foreach($x as $k=>$v){$s=$s+ord($v)-64;if($v>$h){$h=$k;}}
$y[0]=$s;if($t==1){unset($x[$h1]);$y[1]=$x;}return $y;}
while($c==''){$y1=splice($a,0);$y2=splice($b,0);$y3=splice($y1[0],1);
$y4=splice($y2[0],1);if($y3[0]>$y4[0]){$c=$ao;}else if($y3[0]<$y4[0]){$c=$bo;
}else if((strlen($a)<1)OR(strlen($b)<1)){if(strlen($a)<strlen($b)){$c=$ao;}
else if(strlen($b)<strlen($a)){$c=$bo;}else{$c='STALEMATE';}}}
echo $c;
?>

534 Characters.
Now I am unsure as to the rules for starting off so I started with $f='CAN,CBN' as my input. I hope that was right. I have run all the tests and it passes all of them although it is not particularly elegant. I really must get some sleep now but I had great fun working this out - thank you for a great puzzle.
Coded on http://codepad.org/ZSDuCdin

You can use $f=trim(fgets(fopen('php://stdin'))); for taking the input.

Scratch that, $w=fgetcsv(STDIN); works better.

D: 326 Characters
import std.algorithm,std.array,std.conv,std.stdio;void main(string[]a){alias reduce r;auto b=array(splitter(a[1],","));auto s=map!((a){int n=r!"a+b"(map!"cast(int)(a-'A')+1"(a));while(n>9)n=r!"a+b"(map!"cast(int)(a-'0')"(to!string(n)));return n;})(b);int v=r!"a>b?a:b"(s);writeln(count(s,v)>1?"STALEMATE":b[countUntil(s,v)]);}

More Legibly:
import std.algorithm, std.array, std.conv, std.stdio;

void main(string[] a)
{
    alias reduce r;

    auto b = array(splitter(a[1], ","));
    auto s = map!((a){int n = r!"a + b"(map!"cast(int)(a - 'A') + 1"(a));

                      while(n > 9)
                          n = r!"a+b"(map!"cast(int)(a - '0')"(to!string(n)));

                      return n;
                     })(b);
    int v = r!"a > b ? a : b"(s);

    writeln(count(s, v) > 1 ? "STALEMATE" : b[countUntil(s, v)]);
}

Mathematica
Some details still missing
a = {"ZOO"}; b = {"NO"}
f = FixedPoint[IntegerDigits@Total@# &, #] &

If[(s = f /@
        NestWhile[(# /. Max@# -> 0 &) /@ # &, (ToCharacterCode @@ # - 64) & /@ #,
        f[#[[1]]] == f[#[[2]]] &, 1, 5] &@{a, b})[[1, 1]] > s[[2, 1]],
   a, b, "STALMATE"]

{"NO"}

Mathematica  220 207
After writing this, I noticed that this follows the same reasoning that Belisarius used,
h@u_ := ToCharacterCode@u - 64;
m@w_ := FromCharacterCode[Most@Sort@h@w + 64];
f@v_ := FixedPoint[Tr@IntegerDigits@# &, Tr@h@v];
x_~g~y_ := If[f@x == f@y, g[m@x, m@y], If[f@x > f@y, 1, 2]];
x_~z~x_ := "STALEMATE";
x_~z~y_ := {x, y}[[x~g~y]]

Usage
z["ZOO", "NO"]
z["CAN", "BAT"]
z["FAT", "BANANA"]
z["ONE", "ONE"]

Because the response is not competitive (being so long-winded), I decided to use an input format more congenial to Mathematica.

CoffeeScript - 335
z=(a,b,g=a,h=b)->c=y a;d=y b;e=a.length;f=b.length;return g if(c>d);return h if(d>c);return g if(e<2&&f>1);return h if(f<2&&e>1);return "STALEMATE" if(f==e&&f<2);z(x(a),x(b),a,b)
y=(a)->t=0;t+=c.charCodeAt(0)-1 for c in a;t-=9 while 9<t;t
x=(a)->for i in[90..65]
 b=new RegExp(String.fromCharCode(i));return a.replace b, "" if b.test a

Not as happy with this one as I might have been, but I'll put it up anyway. The actual scoring is very concise (y function), but the ifs to compare results (in z) get pretty long.
To use it call z with your two words (e.g. z 'FOO','BAR'). It will score both words and return the higher scoring word. If it's a tie, it will recurse with the modified words (keeping the originals to return eventually, hence the extra two parameters) which it gets from the x function.
The equivalent (expanded) javascript for those interested:
var x, y, z;

z = function(a, b, g, h) {
  var c, d, e, f;
  if (g == null) {
    g = a;
  }
  if (h == null) {
    h = b;
  }
  c = y(a);
  d = y(b);
  e = a.length;
  f = b.length;
  if (c > d) {
    return g;
  }
  if (d > c) {
    return h;
  }
  if (e < 2 && f > 1) {
    return g;
  }
  if (f < 2 && e > 1) {
    return h;
  }
  if (f === e && f < 2) {
    return "STALEMATE";
  }
  return z(x(a), x(b), a, b);
};

y = function(a) {
  var c, t, _i, _len;
  t = 0;
  for (_i = 0, _len = a.length; _i < _len; _i++) {
    c = a[_i];
    t += c.charCodeAt(0) - 1;
  }
  while (9 < t) {
    t -= 9;
  }
  return t;
};

x = function(a) {
  var b, i, _i;
  for (i = _i = 90; _i >= 65; i = --_i) {
    b = new RegExp(String.fromCharCode(i));
    if (b.test(a)) {
      return a.replace(b, "");
    }
  }
};

Racket 479 bytes
(define(dl n)(let p((ol '())(n n))(let-values(((q r)(quotient/remainder n 10)))(if(= q 0)(cons r ol)(p(cons r ol)q)))))
(define(dr N)(let p2((n N))(define s(apply +(dl n)))(if(< s 10)s(p2 s))))
(let p3((l(for/list((i(string->list s)))(-(char->integer i)64)))(k(for/list((i(string->list t)))(-(char->integer i)64))))
(let((a(dr(apply + l)))(b(dr(apply + k))))(cond[(> a b)s][(< a b)t][(equal? l k)"STALEMATE"][else(p3(remove*(list(apply max l))l)(remove*(list(apply max k))k))])))

Ungolfed:
(define (f s t)

  (define (getDigitList n)                     ; sub-fn  to get digit list
    (let loop ((ol '())
               (n n))
      (let-values (((q r) (quotient/remainder n 10)))
        (if (= q 0) (cons r ol)
            (loop (cons r ol) q)))))

  (define (digit_root N)                       ; sub-fn to get digital root of a number
    (let loop2 ((n N))
      (define s (apply + (getDigitList n)))
      (if (< s 10)
          s
          (loop2 s))))

  (let loop3 ((l (for/list ((i (string->list s)))  ; actual fn to compare 2 strings
                   (- (char->integer i) 64)))
              (k (for/list ((i (string->list t)))
                   (- (char->integer i) 64))))
    (let ((a (digit_root (apply + l)))
          (b (digit_root (apply + k))))
      (cond
        [(> a b) s]
        [(< a b) t]
        [(equal? l k) "STALEMATE"]
        [else (loop3 (remove* (list (apply max l)) l)
                     (remove* (list (apply max k)) k)
                     )]
        ))))

Testing:
(f "CAN" "BAT")
(f "ZOO" "NO")

Output:
"CAN"
"NO"

JAVA
    public static void main(String args[]) throws Exception{
        String input=(new BufferedReader(new InputStreamReader(System.in)).readLine());
        StringTokenizer st = new StringTokenizer(input, ",");
        String w1 = st.nextToken();String w2 = st.nextToken();int s1=0;int s2=0;
        String flag="";
        do{ Integer sum1=0;Integer sum2=0;
        for (int i=0;i<w1.length();i++)
            sum1+=((int)w1.charAt(i) - 64);
        for (int i=0;i<w2.length();i++)
            sum2+=((int)w2.charAt(i) - 64);
        while (sum1.toString().length()>1){
            s1=0;
            for (int i=0;i<sum1.toString().length();i++)
                s1+=((int)sum1.toString().charAt(i)-48);
            sum1=s1;
        }
        while (sum2.toString().length()>1){
            s2=0;
            for (int i=0;i<sum2.toString().length();i++)
                s2+=((int)sum2.toString().charAt(i)-48);
            sum2 =s2;
        }
        flag=(s1>s2)?w1:(s1!=s2)?w2:"";
        if (flag!="")
            {st = new StringTokenizer(input,",");
                if (s1>s2)
                    System.out.println(st.nextToken());
                else{
                    st.nextToken();
                    System.out.println(st.nextToken());
                }
            }
        int max=0;
        for (int i=0;i<w1.length();i++){
            max=((int)w1.charAt(i)>max)?(int)w1.charAt(i):max;
        }
        w1 = w1.replace((char)max, (char)64);
        max=0;
        for (int i=0;i<w2.length();i++){
            max=((int)w2.charAt(i)>max)?(int)w2.charAt(i):max;
        }
        w2 = w2.replace((char)max, (char)64);
            }while(flag=="" && !w1.equals(w2));
    if (flag.length()<1)
        System.out.println("STALEMATE");
        }

The code above replaces all max character in case of tie.. is that required?

C++, 473 (I'm borrowing a course iron)
#include<iostream>
#define $ string
#define _ return
using namespace std;$ S($&s){int i=-1,m=i,x=0;while(++i<s.length())if(s[i]-'@'>x)m=i,x=s[i];s.erase(m,1);_ s;}int M($ w){int i,v=0;for(i=0;i<w.length();++i)v+=w[i]-'@';while(v>9){i=0;while(v)i+=v-v/10*10,v/=10;v=i;}_ v;}$ B($ x, $ y){while(!(M(x)-M(y)))S(x),S(y);if(M(x)>M(y))_ x;if(M(x)<M(y))_ y;_"STALEMATE";}int main(int c,char**v){$ s;cin>>s;$ x=s.substr(0,s.find(',')),y=s.substr(s.find(',')+1);cout<<B(x,y)<<endl;_ 0;}

I'm sure I could shorten it up somehow, but I'm tired.
Edit: originally took command line argument, modified to use cin.  It's probably a few characters longer now but I'm too tired to recount it.

Python :383 chars
run the function c('CAN','BAT'):
def k(j):
 l=list(j);l.remove(max(j));return''.join(l)
def f(x):
 x=str(x)
 if len(x)==1 and x.isdigit():return int(x)
 return f(sum('ABCDEFGHIJKLMNOPQRSTUVWXYZ'.index(y)+1 for y in x)) if x.isalpha() else f(sum(map(int,x)))
def c(a,b):
 v=f(a);u=f(b);
 if v>u:return a
 if v<u:return b
 return'STALEMATE' if v==u and (len(a)==1 or len(b)==1)else c(k(a),k(b))

F#, 559 533 530 bytes
Not competitive as of yet.
I'm sure c can be made shorter as well as the last few lines.
Not having easier access to command line args is also hurting here.
open System
let m=Seq.map
let a s=s="";s.ToUpper()|>m(fun c->int c-64)
let rec c i=if i>9 then string i|>m(int>>(-))|>m(fun x->x 48)|>Seq.sum|>c else i
let b i=Seq.fold(fun(r,a)j->(Seq.sum i-a)::r,a+j)([],0)(Seq.sortBy(~-)i)|>fst|>m c
[<EntryPoint>]
let x z=
 let y=z.[0].Split(',')
 let u,v=y.[0].Length,y.[1].Length
 printf"%s"(Seq.fold2(fun s l r->if l=r then 3::s else if l>r then 0::s else 1::s)[](b<|a y.[0])(b<|a y.[1])|>Seq.tryFind((>)3)|>function|None when u>v->y.[0]|None when u<v->y.[1]|Some x->y.[x]|_->"STALEMATE")
 0

Try it online!

Saved 3 bytes by constraining s to string by comparing it with string

Ungolfed version
open System
let m=Seq.map // this is just to save some characters and I'll use Seq.map for this version

let toIntList s =
    s = "" // constrain s to type string
    s.ToUpper()
    |>Seq.map (fun c -> int c - 64) // converts char value to int and offsets it so that A=1

let rec digitSumUntilSingle i =
    if i > 9 then
        string i                // convert number to string
        |>Seq.map ( int>>(-) )  // convert individual char to int and partially apply substraction
                                // this returns a function
        |>Seq.map (fun x -> x 48) // provide last parameter for substraction, this is equivalent to
                                  // charValue - 48
        |>Seq.sum                 // sum over all digits
        |>digitSumUntilSingle     // recursively call this function again in case we are >9
    else
        i

let calculateDigitalRoot input =
    Seq.fold(fun (result, acc) current ->       // calculate digital root for all possible iterations
                (Seq.sum input - acc)::result,  // basically, this calculates Rule 3 until the end for a given word
                acc + current
            ) ([], 0) (Seq.sortBy (~-) input) // sort input by value descending
    |>fst   // only interested in the lits, not the final accumulator
    |>Seq.map digitSumUntilSingle

[<EntryPoint>]
let main (args) =
    let y = args.[0].Split(',')
    let leftLength = y.[0].Length
    let rightLength = y.[1].Length

    Seq.fold2 (fun state left right ->
                if left = right then
                    3::state
                else if left > right then
                    0::state                // 0 is chosen because this represents y[0] index
                else
                    1::state
               ) [] (calculateDigitalRoot (toIntList y.[0])) (calculateDigitalRoot (toIntList y.[1]))
    |> Seq.tryFind ((>) 3)                  // try to find first variation where left and right digital root isn't equal
    |> function
        | None when leftLength > rightLength -> y.[0]
        | None when leftLength < rightLength -> y.[1]
        | Some x -> y.[x]
        | _ ->"STALEMATE"
    |>printf "%s"
    0

PHP, 339 (not to spec), 410 382 359 339 337 Bytes
$b=$w=fgetcsv(STDIN);function a($c){for(;a&$g=$c[$p++];)$f+=ord($g)-64;$f=trim($f);for(;$f[1]&a;$f=$h)for($h=0;a&$r=$f[$q++];$h=bcadd($h,$r));return$f;}function d($f){return strtr($f,[max(str_split($f))=>'']);}for(;$c==$d;$b=[$e,$f]){$x=$z++?d:trim;$e=$x($b[0]);$f=$x($b[1]);$c=a($e);$d=a($f);$e||die(STALEMATE);$c!=$d&&die($w[$c<=$d]);}

EDIT 1: +71 bytes. Using STDIN instead of fopen('php://stdin','r'); and short tags. Also, full conformance to the spec.
EDIT 2: -28 bytes. Using fgetcsv(STDIN) instead of explode(',',trim(fgets(STDIN))), and used for loop instead of while loop.
EDIT 3: -23 bytes. Merged functions a and b, merged for loops.
EDIT 4: -20 bytes. Turned c from a recursive into a loop. Then, removed function c and put its code into the global namespace.
EDIT 5: -2 bytes. Thanks to @Titus for the -r flag.

no need for a PHP tag with -r flag

PHP, 296 281 267 bytes
function f(&$s){for(;$c=$s[$i++];$m>$c||$m=$c)$p+=ord($c)&31;for($s=str_replace($m,'',$s);9<$p=array_sum(str_split($p)););return$p;}for(list($a,$b)=$x=fgetcsv(STDIN);$s==$t&&$a&$b;$t=f($b))$s=f($a);echo($s-=$t)||($s=strlen($x[0])-strlen($x[1]))?$x[+($s<0)]:STALEMATE;

run with -n or try it online (TiO includes breakdown).
Back in Feb 2011, the current PHP version was 5.3.5; so I could not

use shorthand list assignment ([$a,$b]=fgetcsv(...) and such)
alias count_chars inline
index function results directly
use negative string indexes instead of substr

But neither would have saved a lot; so it doesn´t matter much.
Most costly things were the loops (of course) and rule #4 (40 36 bytes).

source: Stack Exchange

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

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

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

sort: votes


text:
Hitting 495 (Kaprekar)
Input:
A three digit number

from stdin or as an argument
not all digits are the same
may start with one or two zero's

Process
Order the input-digits ascending and descending to form two new numbers.
Subtract the smallest from the largest. Use the difference as new input. NB: This process needs 3 digits, so 10 has to be returned, or taken care of, as 010.
Repeat this process (Kaprekar transformation) until you hit 495.
Output:
The number of steps it took to reach 495.
Example:
Input: 211
211 – 112 = 099
990 – 099 = 891 (rather than 99 - 99 = 0)
981 – 189 = 792
972 – 279 = 693
963 – 369 = 594
954 − 459 = 495

Output: 6

May I assume, that the input doesn't consists of three identical digits like in 111 or 222?

Yes (second bullet: not all digits are the same).

Complete set of test cases: http://svn.lando.us/joey/Public/SO/CG1255/testcases.txt

Warning: in some programming languages (e.g. JavaScript), numbers starting with zeros (e.g. 077) are parsed as octals if you're not careful.

I realize this question might come in a bit late in the game, but... what are we expected to return for 495 itself? 0, 1, any?

@J B Joey's test set has it as 0; I think he's right.

@JB: I interpreted »the number of steps it took to reach 495« in that way that if you start with 495 you are already there without executing the algorithm. Might be debatable but arguably it makes the task more interesting since you have to handle one special case.

@Joey: well it's only a special case for the pattern lookup family of algorithms ;) But originally that's precisely why I asked, seing many "495"s pop up in the answers. I'd go for 0 spontaneously myself as well.

steenslag: Again, I do appreciate the accepted answer, but I consider it ill-placed. Since this is a code golf there exists an objective measure of a winning answer and that should be the accepted one. I cannot move the checkmark, though.

@Joey: OK. it's gone to the Golfscript solution.

Even more interesting question is - why does it always converge to 495?

I looked at the description and at the wikipedia page, what happens if its a negative number? Input: 123 gives 123-321=-198 Will the next step simply be 198-891?

@TeunPronk "subtract the smallest from the largest", so no negative numbers.

@MartinBüttner how is this question about three-digit numbers a duplicate of the four-digit version?

Golfscript, 29 26 characters
.$)\0=-.5<{7\}4if-\~495=!*

Basically a mix of Joey's PS- and my Ruby-solution.
Edit: Thanks Nabb for a suggestion on how to shorten this by 3 characters.

Windows PowerShell, 61 65 70 72 73 82
Evil alternative approach. It becomes apparent if you desperately search for patterns in the input.
Be sure to also check out Ventero's Ruby and Golfscript solutions which use the same technique which was sort of a joined work :-)
(7..3+1..5)[($x=($a="$args")[0..2]|sort)[2]-$x[0]]*($a-ne495)

A little explanation might be in order for this, I guess. Suppose you have a number consisting of three digits. For convenience they are labeled a, b and c here with c being the largest. You then are going to subtract abc from cba.
If we picture that, we are going to get (c − a − 1), 9 and (10 + a - c) as the individual digits. This will always hold, no matter the input digits. This also means that the middle digit get no say in how long the sequence will be, simply because it always is 9.
So basically the first and last digit of the sorted digits suffice in determining the length of the sequence. One can easily make a list with every conceivable combination of first and last digit (there are only 45) to search for patterns there.
As it turns out, there are at least two. Both play with the first few results of the different digits: [6 5 4 3 1 2 3 4 5]. First, taking the difference between the largest and the smallest digit and subtracting one gives the appropriate index in the aforementioned list of results. Second, interpreting the smallest and largest digit as a single number and doing modulo 11 yields the same, except that one has to prepend another 6 to the list.

A rare case of golfing leading to fast code.

Accepted answer for admiration of analysis.

J, 43 37
<:$".@(\:,'-',/:)~@":@((3$10)&#:)^:a:

Sample run (note how stripping the 3 leading chars displays a trace):
   <:$".@(\:,'-',/:)~@":@((3$10)&#:)^:a:211
6
   ".@(\:,'-',/:)~@":@((3$10)&#:)^:a:211
211 99 891 792 693 594 495
   <:$".@(\:,'-',/:)~@":@((3$10)&#:)^:a:494
1
   <:$".@(\:,'-',/:)~@":@((3$10)&#:)^:a:495
0

This version repeatedly (^:) converts to decimal ((3$10)&#:), concatenates the descending list (\:), a minus sign '-' and the ascending list (/:), and evaluates (".).  Until the result is stable (a:).  Then it counts the number of returned elements (<:$).
I'm as surprised as you it needs fewer characters than the table lookup variant.

I like how you have made the 495 implicit by stopping at a fixed point.

Python, 89 characters
n=input()
c=0
while n-495:s=''.join(sorted('%03d'%n));n=int(s[::-1])-int(s);c+=1
print c

J, 40
Using the Joey/Ventero approach.  (go upvote them first)
(-&4`(7&-)@.(<&5)".'-'1}\:~y)-'495'-:y=.

This doesn't beat Golfscript, but I liked the idea of sorting the number, replacing the middle digit with a - and evaluating that.

Windows PowerShell, 80 79
for($a="$args";$a-495;++$i){$a=-join($x="00$a"[-1..-3]|sort)[2..0]-+-join$x}+$i

History:

2011-03-05 00:27 (113) Initial attempt.
2011-03-05 00:33 (107) One sort has to suffice.
2011-03-05 00:36   (92) Inlined the filter.
2011-03-05 00:41   (87) No format string anymore. There are other ways.
2011-03-05 00:43   (85) Unnecessary parentheses.
2011-03-05 01:01   (83) -eq → -.
2011-03-05 15:42   (80) I no longer need to cast the initial input to int. Removed unneeded parentheses.
2015-09-11 08:20   (79) I can move a + and save a space by abusing that - can only mean arithmetic and thus always converts both operands to a number.

Side note: My test cases.

Ruby 1.8, 64 55 52 48 characters
l=gets.bytes;i=l.max-l.min;p /495/?0:i<5?7-i:i-4

Note that the input shouldn't contain a line break.
For Ruby 1.9, the solution needs an additional space before the last colon.

(64 -> 55) Thanks to Joey for pointing out that the input already consists of 3 digits.
(55 -> 53) Thanks to steenslag for pointing out Array#minmax
(53 -> 52) Actually just using Array#max and Array#min directly is shorter.
(52 -> 48) Implicitly match a regexp against $_ to test for 495.

Rather amazing... is this the same trick as @Joey's evil approach?

@steenslag: Yes, we both developed it together, kinda.

I'm by no means a math expert, but this could be a minor mathematical novelty. Can it be expanded to include four digits, or even more?

@steenslag: There is a similar number for four digits, but I don't know whether such a formula exists. It may be likely, though I suspect in that case it would look more like (3rd and 4th digit) minus (2nd and 1st digit). Feel free to experiment, though. The discovery above was coincidental after looking at the map I created that maps sorted digits to the result :-)

C - 133
newline added for appearance
c;main(n,l,h,t,i){scanf("%d",&n);for(;n!=495;c++,n=(h-l)*99)
for(l=n%10,h=l,i=2;i--;)t=(n/=10)%10,t<l?l=t:t>h?h=t:0;printf("%d\n",c);}

APL, 42 chars/bytes*
{⍵=495:⍺+0⋄L←⍵⊤⍨3⍴10⋄(⍺+1)∇10⊥L[⍒L]-L[⍋L]}

APL entry was missing from historic golf! Had to rectify. Trivial implementation, nothing fancy. Tested on ngn/apl.
Explanation
The function is initially called with a single number ⍵. It will recursively call itself ∇ with the number of steps already taken ⍺ and the new number ⍵.
⍵=495: ⍺+0

Terminating condition: if ⍵ is 495, return the number of steps already taken (0 if ⍺ is yet undefined—this may differ in other dialects.)
L←(3⍴10)⊤⍵

Decode ⍵ into a list of 3 digits base 10. Above ⊤ is reflected to save 1 char.
(⍺+1) ∇ 10⊥L[⍒L]-L[⍋L]

Sort the list both ways, subtract one from the other member-wise, encode the result in base 10 (this works for negative digits too; may differ in other dialects) and recurse, adding 1 to ⍺ (or just 1 if undefined, see above.)
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.

42 characters. Incidental? :)

Lua 173 bytes
Going for the longest one:
T=table c=T.concat i=1 n=tonumber p=io.read()while l~="495"do l={p:match"(%d)(%d)(%d)"}T.sort(l)k={}k[1]=l[3]k[2]=l[2]k[3]=l[1]p=('%03i'):format(c(k)-c(l))i=i+1 end print(i)

Python, 63
f=lambda n:n-495and-~f(99*(int(max(`n`))-int(min(`n`))*(n>99)))

A recursive function. Gives 0 for n==495 and otherwise transforms n and increments the counter by 1 with -~.
The transformation uses the fact that for three-digit numbers abc-cba equals 99*(a-c). To account for two-digit numbers, we set the min digit to 0 unless n>99.

JavaScript 145
This was the best I could do on such short notice:
for(n=prompt(i=o=e='');!i--|n-495;o+=n+' - '+a+' = '+(n=(p=n-a+e)[2]?p:0+p)+'\n')b=n.split(e).sort(),n=b.reverse(a=b.join(e)).join(e);alert(o+~i)

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

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


text:
ASCII art Bresenham line drawing
Write the shortest possible program that draws a Bresenham line in ASCII art.  Your program should take two integers x and y (command line or stdin, your choice) and draw an ASCII line which starts in the upper left and goes right x units and down y units.  You must use _ and \ characters and place them in the correct location according to Bresenham's algorithm.
You may assume x >= y, so no vertical segments are required.
Note that because you're using the _ character, for a line with y=3 you will likely need to output 4 lines of text (and you may emit a leading blank line when it isn't necessary).
examples:
11 3
_
 \___
     \___
         \_
11 1
_____
     \_____

5 4

\
 \_
   \
    \

For points which are exactly halfway you may choose either rounding:
10 1
____
    \_____
or
_____
     \____

Perl, 74
/ /;print int(.5+$_*$'/$`)>int(.5+--$_*$'/$`)?$/.$"x$_.'\\':'_'for 1..$`

Run with -n option (counted in code size).
$ perl -n bresenham.pl <<<'11 3'
_
 \___
     \___
         \_
$ perl -n bresenham.pl <<<'11 1'
_____
     \_____
$ perl -n bresenham.pl <<<'5 4'

\
 \_
   \
    \
$ perl -n bresenham.pl <<<'10 1'
____
    \_____

C 136 123 Characters
z,x,y,i,f;main(){for(scanf("%d%d",&x,&y);i<=x;i++){f=f?printf("_"):1;z+=y;if(2*z>=x&&i<x)f=0,z-=x,printf("\n%*c",i+1,92);}}

Delphi, 109 bytes
Quite small if you ask me :
var x,y,i:Word;begin Read(x,y);for i:=1to(x)do if(i*y+x div 2)mod x<y then Write(^J,'\':i)else Write('_')end.

The 2 integers are read from the command line.
The newline is written by the seldomly used ^J syntax (meaning LineFeed), the following '\' character is indented using the little-known syntax  :Write(string:width).
It's a pitty Delphi div for integer-divide (instead of just \). Ah well...

Pretty neat and short. Read(input,x,y) can be shortened to read(x,y), and without program and apptype it becomes 157 characters.

@Wouter van Nifterick : A few hours later and it's down to 109 characters now! Don't think there's much to win left...

That's a clever use of write() here. I figured that rewriting if(i*y+x div 2)mod x<y then to if(i*y*2+x)mod(x*2)<y*2then could help, but it's the exact same amount of characters.

APL (Dyalog Classic), 39 bytes
{⍉↑(-1++\a)↑¨'_\'[a←-2-/⌊.5+⍵×⍺÷⍨⍳1+⍺]}

Try it online!

Charcoal, 22 bytes
Ｆ…·¹θ⎇‹﹪⁺×ιη⌊∕θ²θη¶\¦_

It took a while to figure out the right formula, but it now works! Credit to the Delphi answer.
Link is to verbose version of code.
Try it online!


text:
Break the broken hash
Some time ago, I found this unused hash function (written in Java) in our codebase:
long hashPassword(String password)
{
    password = password.toUpperCase();
    long hash = 0;
    int multiplier = 13;
    for (int i = 0; i < password.length(); i++)
    {
        hash += hash * multiplier + (short)password.charAt(i);
        multiplier++;
    }
    hash = Math.abs(hash);
    hash <<= hash % 11;
    hash = Math.abs(hash);
    return hash;
}

I am very happy that it was unused, because it is beyond broken. Not only is this hash function very weak with an ouput of only 8 bytes, but it is also reversible, and it collides very easily: there are many similar inputs that will generate the same hash. A friend and I worked on the problem, and we managed to create a C# program that does just that: take a hash, and show the reasonable inputs that could have generated this hash.
Now is your turn. Write a program, in any language, that accepts a numeric hash as its sole parameter, and yields all possible inputs (made of 5+ characters with only printable ASCII characters) that would produce the given hash if passed to the function above, each on a new line. You don't need to handle any specific kind of error, as long as it works for any given numeric hash.
On your post, please include the hash of a word of your choice, and five possible inputs that have this hash (though your program must not be limited to finding only five).
Most elegant solution wins, and elegance is defined as algorithmic elegance (in other words, brute-force won't win). I'll accept an answer on March 13.
Example input and output (UNIX shell optional):
$ ./hashbreaker 224443104
ZNEAK
Y^4Q]
\2'!'
ZMUB9
Y_%AK
[and many, many, many more results...]

Sorry, Not familiar with C#. What does (short) password.chartAt(i) do? Will it return the ASCII code of the character? A -> 65 etc?

@Dogbert, essentially, yes. (It actually converts the character into a 16-bit value which is its codepoint in the Unicode basic plane, but given that the problem specification restricts interest to ASCII and ASCII values map directly to Unicode codepoints, you can treat it as returning the ASCII code).

@Dogbert This snippet is actually Java, but we broke it with C#. I'll clarify. For the rest, @Peter Taylor has it right.

I fail to get how you can get 224443104 for "ZNEAK". ASCII codes are 90, 78, 69, 65, 75; ((((0*13+90)*14+78)*15+69)*16+65)*17+75 is 5478988; abs that is the same; 5478988%11 is 9 and 5478988<<9 is 2805241856 (abs that is the same as well).  What am I missing?

@J-B, you're missing the + of +=, which causes your multipliers to be one too small. It should be ((((0*14+90)*15+...

@Peter Taylor: good catch, thanks!

By simple estimation there is an average of over 6*10^17 results in the range 5 to 20 characters (though the number will vary wildly depending on the number of possible backtracks through the last 3 operations), do you really want them all as output? I'm sorry, zneak. I'm afraid I can't do that.

@eBusiness I know, I know! Life is hard, and posting that many would drain one's bandwidth quick enough. Luckily, all you have to post along your answer, as specified in the question, are 5 collisions. I'm sure you can do at least that.

It's not so much bandwidth I'm concerned about, but no computer in the world has enough memory to store all the results. One really can't optimise a task that is incompletable.

@eBusiness Whatever your concern is, rest assured that you need no more than 5 with your post. Your computer should be able to handle that (and your ISP too).

eBusiness makes a good point. Your spec says "yields all possible inputs (made of 5-20 characters with only printable ASCII characters) that would produce the given hash", but a program which emits one possible input per nanosecond would, for an average hash, take more than a decade to execute (there are approximately 2^123 possible inputs, ignoring lower-case a-z since they are upper-cased by the hash function, and only 2^64 possible outputs - if that).

@Peter Taylor I didn't do a very complex analysis, but I'm pretty sure a smart program doesn't need to go through 2^123 possibilities. And since I don't see any practical use of breaking those hashes, I'm at ease stopping the program once I get the feeling it's working.

@zneak, you're missing the point. 2^123 objects in 2^64 buckets means that on average each bucket contains 2^(123-64) = 2^59 objects. If you prefer to look at it this way: a program which meets your spec will output about 8 exabytes. You really need to change the spec to either limit it to the first N values for a reasonable N or to limit the search space to strings up to some smaller size.

@Peter Taylor I was very wrong with my numbers, but I still hope that you realize I'm more interested in the algorithm than the output itself. I've removed the upper bound on input size to make it more clear: just generate values that match the hash until I press Ctrl+C.

Hmmm, well, now the specification as it stand calls for infinite results.

Which means that people using (most) functional languages have to complicate things by using lazy output.

@eBusiness Yes, it does. If you write a general solution, it shouldn't be a problem. @Peter Taylor, I really don't know about functional languages, but aren't dynamic stacks a standard feature among them? That said, if you don't stack overflow after a few minutes of running with your favorite language, I won't mind it if practical restrictions prevent you from outputting exabytes of data.

@zneak, functional languages often do output via interactive emitting of the results of the function. In other words, they don't output part-way through a calculation - so if you have an infinite calculation, you'll never see any output. See J-B's solution as an example: it's a function which returns a list of all the solutions it finds.

Another partial answer:
using System;
using System.Collections.Generic;

namespace Sandbox {
    class Launcher {
        public static int Main(string[] args) {
            long h4;
            if (args.Length != 1 || !long.TryParse(args[0], out h4)) {
                Console.Error.WriteLine("Usage: Sandbox.exe <hash>");
                return -1;
            }

            // TODO Handle 15-char or longer solutions. 15 chars is the point at which simple mod breaks because the multipliers wrap.
            for (int len = 5; len < 15; len++)
                foreach (long h3 in invAbs(h4))
                    foreach (long h2 in h3Toh2(h3))
                        foreach (long h1 in invAbs(h2))
                            foreach (string soln in solveH1Inner(h1, new char[len], len - 1, 1, 13 + len))
                                Console.WriteLine(soln);

            return 0;
        }

        private static IEnumerable<string> solveH1Inner(long rem, char[] chs, int off, long mul, long mod) {
            if (off < 0) {
                if (rem == 0) yield return new string(chs);
                yield break;
            }

            long mask = (mul & -mul) - 1;
            if ((rem & mask) != 0) yield break;

            foreach (char ch in " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_{|}~") {
                if ((ch * mul) % mod == rem % mod) {
                    chs[off] = ch;
                    foreach (string soln in solveH1Inner(rem - mul * ch, chs, off - 1, mul * mod, mod - 1))
                        yield return soln;
                }
            }

            yield break;
        }

        private static IEnumerable<long> invAbs(long h4) {
            if (h4 < 0 && h4 != long.MinValue) throw new ArgumentException();
            yield return h4;
            if (h4 != long.MinValue) yield return -h4;
        }

        private static IEnumerable<long> h3Toh2(long h3) {
            // h3 = h2 << (h2 % 11)
            // where h2 is either long.MinValue or non-negative.
            // long.MinValue << (long.MinValue % 11) = 0
            if (h3 == 0) yield return long.MinValue;

            for (int shift = 0; shift < 11; shift++) {
                if (shift == 0 && h3 < 0) continue;

                long mask = (1L << shift) - 1;
                if ((h3 & mask) != 0) break;

                long inc = shift == 0 ? 0 : 1L << (64 - shift);
                long maskBottom = inc - 1;
                long bottom = (h3 >> shift) & maskBottom;
                long top = 0;
                do {
                    if ((top + bottom) % 11 == shift) yield return (top + bottom);
                    top += inc;
                } while (top > 0);
            }
        }
    }
}

There are some minor optimisations which could be done, but I think it's more legible like this. (Arguably I should eliminate the enumerators and push the WriteLine in too, but hey).
Example of collisions for 199681664

PETER
OTTER
R(DER
Q6SVR
R*&$@

I got more than enough answers without reversing both abs calls, so I skipped that.  They'd be trivial to add back if really needed.  I'm not even taking long overflow into account, but that'd let you insert most any word you like in the greater hashes.  As if that was needed to get collisions.
import Data.Char
import Data.Bits
import Control.Monad

printables = [32..95]

reverseModShift11 x = do
  let zeros = head $ filter (testBit x) [0..]
  b <- [0 .. zeros]
  let h = x `shiftR` b
  guard $ (h `mod` 11) == (fromIntegral b)
  return h

reverseBase p m n | m < 13    = []
                  | n <  0    = []
                  | n == 0 && m == 13 = return p
                  | otherwise = do
  let r = n `mod` m
  c <- filter (\x -> x `mod` m == r) printables
  reverseBase (chr c:p) (m-1) ((n-c) `div` m)

reverseBases = join . ap (map (reverseBase "") [14..29]) . return

breakHash = reverseModShift11 >=> reverseBases

Sample use:
*Main> breakHash 224443104
["]#'!'","\\2'!'","[A'!'","ZP'!'","Y_'!'",
  (...)
"[?EAK","ZNEAK","Y]EAK",
  (...)
"] TQ]","\\/TQ]","[>TQ]","ZMTQ]","Y\\TQ]"]

JavaScript 224 LOC
This function will calculate all results of a given length, optionally limited to results starting with a given string, that is if it's done within the 1 second that I have allotted. If no results exist it is done virtually instantly. The function rely heavily on a very slow custom built 64 bit integer library, an equivalent C function would probably be 100 to 1000 times faster. I might set up a nice web interface.

<title>Break Hash</title>

Some collisions for 224443104
EBUSINESS"XUWL]NHHHF{I
EBUSINESS"XUWL]NHHHF|&
EBUSINESS"XUWL]NHHHGYI
EBUSINESS"XUWL]NHHHGZ&
EBUSINESS"XUWL]NHHHH7I

Clever, clever.


text:
Check printer - Convert to English text from the input value.
Check printer function (or subroutine) - Convert to English text from the input value. 12.34 -> "twelve dollars and thirty four cents". For the range .01 to 9999.99 assuming valid input.

can we assume that answers could be in codegolf way?

Is this a function or a whole program?

Hm... I did this once for MMIX... Wait some time and I change it to satisfy the conditions. That's fun!

How should 12.00 be written?  "twelve dollars" or "twelve dollars and xx/00" or something?

You are generally expected to tag questions with a type-of-puzzle tag (so far code-golf or code-challenge). Please correct my edit if I chose poorly.

Common Lisp, 95
Newline not counted in:
(lambda(n &aux(d(floor n))(c(round(*(- n d)100))))
(format()"~R dollar~P and ~R cent~P"d d c c))

Sample use (assigning it to f):
CL-USER> (f .01)
"zero dollars and one cent"
CL-USER> (f 12.34)
"twelve dollars and thirty-four cents"
CL-USER> (f 9999.99)
"nine thousand nine hundred ninety-nine dollars and ninety-nine cents"


text:
Chessboard pattern
Input:
a positive number \$n\$, smaller than \$80\$, from stdin or as a command-line argument.
Output: A square chessboard pattern, the size of the input number. The dark fields are represented by the letter X, the white fields by a space. The top-left field should be X.
A complete program is required. This is code-golf so the shortest code in bytes wins

Examples:
Input: 1
Output:
X

Input: 8
Output:
X X X X
 X X X X
X X X X
 X X X X
X X X X
 X X X X
X X X X
 X X X X

I was looking for a tag like 'light-weight' for this.

Whole and complete program, I suppose?

@J B: Yes. How do I formulate that? Add 'to stdout' to the required output?

Just say you want a complete program.  You might also want to specify command-line arguments, to prevent confusion with function arguments.

When you say top-right, do you mean top-left? If not, please correct the example output for input 8.

@Peter Taylor: This is.. it is... well , it is corrected.

I assume an input of zero should produce no output?

Was it intentional that this is described as a chessboard pattern, yet the board is placed incorrectly for a game of chess? (Should have light square in the bottom right.)

Pyth, 13 chars
Note: Pyth is much too new to be eligible to win. However, it was a fun golf and I thought I'd share it.
VQ<*QX*d2N\XQ

Try it here.
How it works:
                       Q = eval(input())
VQ                     for N in range(Q):
  <         Q                                                        [:Q]
   *Q                                    (Q*                        )
     X*d2N\X                                assign_at(" "*2, N, "X")

Basically, this uses X to generate "X " or " X" alternately, then repeats that string Q times, and takes its first Q characters. This is repeated Q times.
How does the X (assign at) function work? It takes the original string, "  " in this case, an assignment location, N in this case, and a replacement character, "X" in this case. Since Pyth's assignments are modular, this replaces the space at location N%2 with an X, and returns the resultant string, which is therefore "X " on the first, third, etc. lines, and " X" on the others.

... but APL isn't. Thanks for bumping. Wonder if OP will re-accept...

"Pyth is much too new to be eligible to win" I don't understand this and reaccept this one.

@steenslag To explain, there is a standard loophole that languages newer than the question are ineligible. This is to prevent languages specifically designed to do well at a specific challenge. You're free to do what you want with your challenge, of course.

Golfscript - 17 chars
~:N,{"X "N*>N<n}%

Analysis
~ convert input to an int
:N store in the variable N
,{...} for each value of [0...N-1]
"X "N* repeat "X " to give a string of N*2 characters
> take the substring starting from the loop index...
N< ...ending N characters later
n put a newline a the end of each string

Perl, 41 40
for$i(1..$_){say substr" X"x$_,$i%2,$_}

Perl 5.10 or later, run with perl -nE 'code' (n counted in code size)
Sample output:
$ perl -nE'for$i(1..$_){say substr" X"x 40,$i%2,$_}' <<<5
X X X
 X X
X X X
 X X
X X X
$ perl -nE'for$i(1..$_){say substr" X"x 40,$i%2,$_}' <<<8
X X X X
 X X X X
X X X X
 X X X X
X X X X
 X X X X
X X X X
 X X X X

What does the 'x' in 'x 40' do?

@steenslag: x is the string repetition operator. 'a' x 3 yields 'aaa'.

Python, 48 Characters
x,i=input(),0
exec'print(x*"X ")[i:i+x];i^=1;'*x

Python, 76 characters
n=input()
p='X '*n
print n/2*(p[:n]+'\n'+p[1:n+1]+'\n'),
if n&1:print p[:n]

Scala - 141 95 characters
var a=args(0).toInt
for(y<-1 to a;x<-1 to a)print((if((x+y)%2<1)"X"else" ")+("\n"*(x/a)take 1))

Usage: scala filename N where n is your input to the program.

APL (16)
Assuming ⎕IO=0 (i.e. zero-indexed arrays, it is a setting)
' X'[=/¨2⊤¨⍳2⍴⎕]

Explanation:

⍳2⍴⎕: read a number N, and create a N×N matrix containing (0,0) to (N-1,N-1).
2⊤¨: get the least significant bit of each number in the matrix. (So now we have (0,0), (0,1), (0,0)... (1,0), (1,1), (1,0)...)
=/¨: for each pair, see if the two numbers are equal. (Now we have 1 0 1 0 1 0 ...)
' X'[...]: put a space for each 0 and an X for each 1.

Ruby 45 42
(x=gets.to_i).times{|i|puts ("X "*x)[i,x]}

Demo: http://ideone.com/Mw25e

(x=gets.to_i).times saves three chars. Why the sudden  renewed interest in this oldie?

@steenslag Thanks! I've applied your tip. I just saw this question at the top of the list and thought I'd post an answer to dust off my Ruby skills. Apparently I haven't dusted them off enough. :)

Brainfuck, 140 bytes
-[+[+<]>>+]>++++[<++++++++>-]<<<<<<,[->+>+>+<<<]>>[->[->.<[->>.>]<<<]<[<<<]>>>>>[-<+>]>[-<+>]<<[->>+<<]<<[-<+>]<[->+>>+<<<]++++++++++.[-]>>]

C++ - 253 obfuscated characters
#include <iostream.h>
int main(int i,char*c[]=0)
{
  char a=i,b=i>>8;i&32512?((i>>16&255)<a)?(cout<<b)?main((i^30720)+65536):0:(cout<<endl)?(((b=(i>>24)+1)<a)?main((i&2130706559)+((b&1)?16785408:16799744)):0):0:main((i>=2?atoi(1[c]):8)|22528);
}

I love all the magic numbers.

JavaScript, 169
function b(w){var i=w,j=w,r='';while(i--){while(j--){if((i+j)%2)r+=' ';else r+='X'}j=w;r+="\n"}return r}do{n=parseInt(prompt('Number'))}while(isNaN(n)||n<1);alert(b(n));

I'm pretty sure you can convert to number like +'1' instead of parseInt('1'). Won't give you an integer, but I don't think having it be an integer is important here, is it?

k (26 chars)
26 For bare function:
{-1',/x#',x#'("X ";" X");}

Or a further 7 to take input from stdin
{-1',/x#',x#'("X ";" X");}"I"$0:0

Bash: 60 characters
yes X|fmt -w80|paste -d '' <(yes '
 ') -|head -$1|cut -c1-$1

The table size is passed as command-line parameter, for example bash chesstable.sh 8.

APL (Dyalog Extended), 12 bytesSBCS
Anonymous tacit prefix function. Requires ⎕IO←0 (zero-based indexing).
'X '⊇⍨2|⍳+⍀⍳

Try it online!
⍳ ɩndices 0…n–1
+⍀ plus table with that horizontally and vertically:
 ⍳ ɩndices 0…n–1
2| division remainder when divided by two
'X '⊇⍨ use that matrix to index into the string

Java 10, lambda function, 92 87 84 bytes
n->{for(int i=0;i<n*n;)System.out.print(((i%n+i/n)%2<1?"X":" ")+(++i%n<1?"\n":""));}

Try it online here.
Thanks to ceilingcat for golfing 4 bytes and to Kevin Cruijssen for golfing 3 more.
Ungolfed version:
n -> { // void lambda taking an int as argument
    for(int i = 0; i < n*n; ) // loop over the entire square
            System.out.print(((i%n + i/n) % 2 < 1 ? "X" : " ") // print an 'X' or a space depending on which line&column we're on
               + (++i % n < 1 ? "\n" : "")); // print a newline at the end of a line
}

Java 8, full program, 155 139 bytes
interface M{static void main(String[]a){int i=0,n=new Byte(a[0]);for(;i<n*n;)System.out.print(((i%n+i/n)%2<1?"X":" ")+(++i%n<1?"\n":""));}}

Try it online here.
Ungolfed version:
interface M {
    static void main(String[] a) {
        int i = 0, // iterator variable for the loop
            n = new Byte(a[0]); // take the argument and convert it to an int
        for(; i < n*n; ) // loop over the entire square
            System.out.print( ((i%n + i/n) % 2 < 1 ? "X" : " ") // print an 'X' or a space depending on which line&column we're on
                             +(++i % n < 1 ? "\n" : "") ); // print a newline at the end of a line
        }
    }
}

@ceilingcat Thanks! I managed to shave off one more byte, and applied your approach to my full program as well. 16 bytes saved there.

Doing two s+= is 2 bytes shorter than those parenthesis: n->{var s="";for(int i=0;i<n*n;s+=++i%n<1?"\n":"")s+=(i%n+i/n)%2<1?"X":" ";return s;}

Or 1 more byte off (84 in total) by printing directly (with the parenthesis back again xD): n->{for(int i=0;i<n*n;)System.out.print(((i%n+i/n)%2<1?"X":" ")+(++i%n<1?"\n":""));}. Try it online.

Suggest "X ".charAt(i%n+i/n&1) instead of ((i%n+i/n)%2<1?"X":" ")

Japt, 8 7 bytes
ÆîSi'XY

Run it online
7 6 bytes if we can replace X with x:
ÆîSixY

Run it online

Alternative 8 byte solution:
Æî"X "éY

Run it online

Ah, you edited while I was in chat! Was gonna suggest the same thing.

Python 2, 47 bytes
n=input()
s='X '*n
exec"print s[:n];s=s[1:];"*n

Try it online!

Python 2, 47 bytes
n=input()
i=0
exec"i^=1;print'X'*i+n/2*' X';"*n

Try it online!
Trims trailing space.

Scala, 68 bytes
  def^(n:Int)=for(a<-1 to n)println(("x_"*n).substring(n%2+1,n+n%2+1))

or
  def^(n:Int)=for(a<-1 to n)println(("x_"*n).substring(a%2+1).take(n))

Try it online!

MATL, 9 bytes
:&+o~88*c

Try it online!
ASCII c 88 multiplied * by not ~ the parity o of the broadcast self-addition &+ of the range : from 1 to the input.

Javascript, 67 bytes
for(j=n=readline()|0;j--;)console.log(' X'.repeat(n).substr(j%2,n))

Try it online
C, 83 bytes
i,j;main(n){for(scanf("%d",&n);i++<n;puts(""))for(j=0;j<n;)putchar(i+j++&1?88:32);}

Try it online
Basic C64, 89 bytes
1 INPUTN:FORI=1TON;FORJ=1TON:IFI+JAND1THENPRINT" ";:GOTO3
2 PRINT"X";
3 NEXT:PRINT"":NEXT

You may use the on...go to command conditionally, like ON-(I+JAND1)GOTO3:?"X";: where it is zero, it will fall through to the following statement, in this case, if (I + J AND 1) === 0 then it will print the X. This allows you to pack in more statements per line and save bytes.

C 81 bytes

Scala, 40 and 54
The number of characters is 40 for a function, 54 for a complete program.
The solution giving only a function body is:
("X "*n)sliding n take n foreach println
Try it online

The solution giving a complete program is:
val n=readInt;("X "*n)sliding n take n foreach println
You can run it using the following command line.
scala -e 'val n=readInt;("X "*n)sliding n take n foreach println' <<< 8
where 8 is the input.

Welcome to PP&CG and nice first answer. There's a nice site called Try It Online that allows you to get easy byte counts and share runs. Check the other Scala answer to see an example of it. It's not required mind you, just nice to have.

Thanks @Veskah for the suggestion.

Nice solution changing this to a function and using map you get 34 Characters: ("X "*n)sliding n take n map println

@pme Thanks for the suggestion, but there is no output if I replace foreach with map. However I change it to a function as you suggested.

you are right - sorry seems map is lazy;(.

brainfuck, 249 bytes
>-[-[-<]>>+<]>->+++>-[<+>---]+>>>>>>+[[-]>,[>++++++[<-------->-]<<<[->>++++++++++<<]>+>[-<<+>>]]<]<[<+<+>>-]<<[->[->+<<<+<[<<<.>>>->-<]>[<<<.>>+>-]>>]++++++++++.[-]>[<+>>+<-]>>++<[>->+<[>]>[<+>-]<<[<]>-]>[-]>-[<<<<<<<[>+<[-]]+>[<->-]>>>>>>[-]]<<<<<]

Try it online!
Could definitely be golfed more.

C (gcc), 90 88 83 82 bytes
-2 thanks to ceilingcat
And -5 more by ceilingcat. Iterate backwards for extra confusion!
Another -1 by ceilingcat. Iterate using negative integers for extra confusion!
m;main(n,v)int**v;{for(n*=m=~(n=atoi(v[1]));n++;)putchar(n%m?n%m-n/m&1?88:32:10);}

Try it online!
Ungolfed
m;

main(n, v) int**v;
{
    for (n *= m = ~(n = atoi(v[1])); n++;)
        putchar(n % m ? n % m - n / m & 1 ? 88 : 32 : 10);
}

Python - 127 characters
from sys import*
r=stdout.write
s=int(raw_input())
[[r((x+y+1)%2 and"x"or" ")for x in range(s)]and r("\n")for y in range(s)]

C - 92 86
i,j;main(n){for(scanf("%d",&n);i<n;puts(""),i++)for(j=0;j<n;j++)putchar("X "[i+j&1]);}

83 Bytes

Python 48 Chars
EDIT: Kinda Wrong...There's an extra space at the end...but thats not visible. If you change the space to "O" (or any nonwhitespace char) then modify [i%2:n] to [i%2:n+i%2]. for the correct version.
n=input()
i=0;
while i<n:print('X '*n)[i%2:n];i+=1

Q, 33
{$[1=x mod 2;x;x-1]cut(x*x)#"X "}

{(x;x-1-x mod 2)#"X "} for 22... ah no, has the same bug as yours - doesnt have 4 X's on the odd rows for input 8.

Ruby 58
i=ARGV[0].to_i
1.upto(i*i){|n|print n%i==0?"\n":' x'[n%2]}

VB.net, 161
Module C
   Sub Main()
     Dim n As Integer
     If Integer.TryParse(Console.ReadLine,n) Then
     For x=1To n
        For y=1To n
          Console.Write("* "((x+y)Mod 2))
        Next
        Console.WriteLine()
      Next
     End If
    End Sub
End Module

PHP - 136 chars (without whitespace)
Allows for x and y function input.
Also supports odd inputs now.
If you style the output to have 0.65 em line-height and change this ▒█ and █░ to □■ and ■□ then it comes out looking like a real  (square) chessboard.
Code:
function gen_cb($x,$y)
{
$c=0;
$y*=2;
for($i=0;$i<$y;$i++){
for($j=0;$j<$x;$j++){
echo $c%2==0 ? "░█" : "█░";
}
echo "<br/>";
$c++;
}
}
gen_cb(7,7);

Output:
░█░█░█░█░█░█░█
█░█░█░█░█░█░█░
░█░█░█░█░█░█░█
█░█░█░█░█░█░█░
░█░█░█░█░█░█░█
█░█░█░█░█░█░█░
░█░█░█░█░█░█░█

Does it work for boards with an odd number of squares per side?

@Gareth Now it does

PHP, 87
for($x=0;$x<$m=$argv[1];$x++){echo"\n";for($y=0;$y<$m;$y++)echo($y^($x%2))%2?' ':'X';}

CJam, 18 bytes
I probably could have just ported the GolfScript answer, but here is a different approach. (And CJam is not eligible for winning anyway.)
l~,_f{f{+2%S'X?}N}

Test it here.
The idea is to iterate over the 2D grid with x and y indices on the stack, using the f{f{...}} trick. Given x and y, we can simply determine black and white as (x+y)%2 and use that to pick between the character X and a string containing a space.

J, 21 chars
J was missing too.
   ([:u:32+56*=/~@$&1 0) 5
X X X
 X X
X X X
 X X
X X X

Previous, 22 chars:
Char codes from mod2 pattern of row # + column #:
   ([:u:88-56*2&|@+/~@i.) 5

-2 Bytes: ([:{&' X'=/~@$&1 0)

14 bytes 'X '{~2|+/~@i. Try it online!

PHP, 75 bytes
for(;@$i++<$k=$argv[1];){for($j=0;$j++<$k;)echo($i+$j)%2?' ':'X';echo"\n";}

Japt v1.4.6 -R, 10 bytes
Æç"X " tXU

Try it
-3 bytes thanks to @Shaggy!
Æç"X " tXU   # full program
Æ            # generate a range of numbers based on input
             # and map each number through a function
 ç"X "       # inside the function, repeat "X " a bunch of times
       tXU   # select a substring from the "X " repeated string
             # The -R flag joins the array with new lines

10 bytes

Nice interpreter :)

Thanks :) Drop into the chatroom if you have any feedback or feature requests.

@Shaggy 8 bytes :P

Canvas, 6 bytes
XX＼ｍ⤢ｍ

Try it here!

C# (Visual C# Interactive Compiler), 61 bytes
x=>{for(int i=x++*x;--i>0;)Write(" X\n"[i%x<1?2:i/x+i%x&1]);}

Try it online!
-2 bytes thanks to @ceilingcat!

This gives an incorrect output for odd inputs.

OK - Think I got it :) Thanks for pointing that out.

05AB1E, 13 bytes
„X ×Â‚εI∍}I∍»

Can definitely be golfed a bit more..
Try it online or verify some more test cases.
Explanation:
„X ×           # Repeat string "X " the (implicit) input amount of times
    Â‚         # Pair it with its reverse
      εI∍}     # Shorten both strings to a length equal to the input
          I∍   # Extend this list of strings to a length equal to the input
            »  # Join the strings by newlines (and output implicitly)

PowerShell, 39 bytes
param($n)1..$n|%{' X'*$n|% S*g($_%2)$n}

Try it online!

Unexpanded Sinclair ZX-81/Timex TS-1000/1500 and compatibles, ~96 Tokenized BASIC bytes
 1 LET X$="X X X X X X X X X X X "
 2 INPUT I
 3 FOR X=SGN PI TO I
 4 PRINT X$( TO I)
 5 LET X$=X$(VAL "2" TO )+X$(SGN PI)
 6 NEXT X

There are some limitations here; as the Sinclair ZX-81 by default only allows 32 character per line, and only 22 lines per screen by default, I have limited the maximum "chess board" to that, 22 x 22.
I is used here as a user input variable to determine the required "size" of the chess board. Once entered into the loop, the X$ string is essentially shifted to the right by one character in line 5.
Enjoy typing!

C64/128 and C64Mini (and compatibles), 68 tonekized BASIC bytes
 0fOi=0to11:a$=a$+"V ":nE:inputi:fOx=1toi:?leF(a$,i):a$=rI(a$,21)+leF(a$,1):nE

I've limited the potential size of the chess board pattern to a width of 22 because whilst the C64 might have 40 text columns, it only has 25 rows and therefore going over 22 will mean that some of the pattern is lost because when exiting a symbolic listing the C64 with typically add a carriage return, then the ready. prompt, and another carriage return where the cursor will reside.
To explain, here is the non-obfuscated symbolic listing:
 0 for i=0 to 11
 1  let a$=a$+"V "
 2 next i
 3 input i
 4 for x=1 to i
 5  print left$(a$, i)
 6  let a$=right$(a$, 21)+left$(a$, 1)
 7 next x

First the chess board patters is built in the a$ variable with the shifted (or uppercase) v representing an X.
The user is then asked for an input of a numeric value. This will work with positive Integers with a greater value than zero, though will work also with positive floating point numbers greater or equal to one.
A for/next loop is set up to the Integer value of the number entered, printing out the pattern to the length of the number entered.
The a$ variable is then shuffled one character to ensure the chess board effect in the loop.
Enjoy programming!

K (oK), 19 bytes
Solution:
{x$(x;x+~2!x)#"X "}

Try it online!
Explanation:
Reshape the input with an odd-length so that the X_ wraps to create the checkerboard, and then truncate to the correct width:
{x$(x;x+~2!x)#"X "} / the solution
{                 } / lambda taking implicit input x
              "X "  / string "X "
   ( ;      )#      / reshape to (length;width)
         2!x        / x mod 2
        ~           / not (0=>1, 1=>0)
      x+            / add to x
    x               / length is input
 x$                 / pad width to x

Scala, 84 bytes
for(i<-1 to a;s=Seq.fill((a+1)/2)("X ").mkString)println(if(i%2==1)s else s.reverse)

Try it online!

Think you can drop a couple of the whitespaces for 80 chars... But doesn't look like this works for input of 1

@streetster thanks - this special case cost me 4 bytes;(

Perl 5 + -n -M5.10.0, 35 bytes
eval'say substr"X "x$_,$-++,$_;'x$_

Try it online!

Vyxal, 10 bytes
‛X *½h:(…Ṙ

Try it Online!
A little long...

Haskell 89 74 charaters
main=do n<-readLn;mapM_(putStrLn.take n).take n.cycle$map cycle["X "," X"]

PHP, 88 80 78
for($x=0;$x++<$i=$argv[1];){for($y=0;$y++<$i;)echo($y+$x)%2?" ":"X";echo"\n";}

There is no opening <?php tag, would this still work?

I'm assuming you are running it through the PHP interpreter, not as part of a web-page.

Thanks, an explanation would be nice to add (i.e., how to run this)

cQuents, 17 bytes
|
&"X "Tn/2,Z[1:]

Try it online!
Explanation
|
                     Separate terms on newline
 &                   Given input n, output first n terms in sequence
                     Odd terms equal
  "X "                               "X "
      *              implicit             repeated                  times
      T                                            ceiling of
       n/2                                                    n / 2
          ,          Even terms equal
           Z                          previous term
            [1:]                                    with the first character removed (Python slice notation)

Charcoal, 10 bytes
Ｅθ⭆θ§X ⁺ιλ

Try it online! Link is to verbose version of code.
Explanation
Ｅθ           Map over first input (predefined variable). Since it's a number, maps over 0 to input (excluding upper bound) instead
   ⭆θ        String map over first input
      §  ⁺ιλ  At (cyclic) index i + l (current loop variable for inner and outer loop respectively)
       X      The string "X ". Note there is a space after the "X"

Oracle SQL, 84 bytes
SQL> select rpad(substr(rpad('_',n,'x_'),mod(level,2)+1),n,'_')from t connect by level<=n
  2  /

RPAD(SUBSTR(RPAD('_',N,'X_'),MOD(LEVEL,2)+1),N,'_')
--------------------------------------------------------------------------------
x_x_x_x_x_
_x_x_x_x_x
x_x_x_x_x_
_x_x_x_x_x
x_x_x_x_x_
_x_x_x_x_x
x_x_x_x_x_
_x_x_x_x_x
x_x_x_x_x_
_x_x_x_x_x

10 rows selected.

MUMPS (58 56 88 86 88 bytes)
Assuming you can execute this code in an interpreter:
(ANSI M)
  r v,! f i=1:1:v d  w !
  . f j=1:1:v w $s(i#2:$s(j#2=1:"X",1:" "),1:$s(j#2:" ",1:"X"))

We could bring this down to 82 bytes if we allow a new line at the beginning of the output:
 r v,! f i=1:1:v w ! f j=1:1:v w $s(i#2:$s(j#2=1:"X",1:" "),1:$s(j#2=1:" ",1:"X"))

Bonus
We can take advantage of the fact that M doesn't have any reserved keywords to give further headache:
s s=8 f f=1:1:s w ! f w=1:1:s w $s(f#2:$s(w#2=1:"X",1:" "),1:$s(w#2=1:" ",1:"X"))

Caché ObjectScript (a superset of ANSI M) (83 bytes):
r v,! f i=1:1:v{f j=1:1:v{w $s(i#2:$s(j#2=1:"X",1:" "),1:$s(j#2=1:" ",1:"X"))} w !}

Explanation:
both cases are essentially the same. Accept input "v" from user. While looping from 1 to v, execute an inner loop such that if i#2 isn't zero, write "X" if j#2 isn't zero and " " in all other cases (i.e. when j#2 is zero). if i#2 is zero, do the opposite. After completing the inner loop, start a new line.
dang, realized I forgot to alternate lines
*added another version of ANSI M and an ObjectScript version

How would I run this, for example on this site: https://tio.run/#mumps

I can't figure out how to give user input in that site you mention, but if you want, you can set the size at the beginning:  s v=8 f i=1:1:v w ! f j=1:1:v w $s(i#2:$s(j#2=1:"X",1:" "),1:$s(j#2=1:" ",1:"X"))
Though the ObjectScript version doesn't work on tio.run (proprietary to Intersystems)

Input is given as Stdin in the input box, or passed as an argument. How is your program currently taking input?

In an interactive M session, Stdin is set to be the user's terminal.
Something might be wrong with the setup for tio.run. w $ZIO is the translated I/O device and that throws an error. If I try to explicitly say to use Stdin via u 0 or u $Principal, I also get an error.

output of $ZIO: *** Z function or variable not found in or near line 1
Global arrays closed.
Termination message: 100 Software Error

Stax, 6 bytes
òeφ→α♪

Run and debug it
Unpacked, ungolfed, and commented, it looks like this.
cK      map over the cartesian square of [1..n] * [1..n]
        implicitly output from each row on separate lines
  +     add the coordinates
  .X @  index into string "X "

Run this one

Jelly, 17 bytes
⁾X ẋs2UÐeẋ³ŒHḢƊ€Y

Try it online!
This almost certainly can be golfed further; 17 bytes seems like too many.
Explanation:
⁾X ẋs2UÐeẋ³ŒHḢƊ€Y    Example input: 3
⁾X ẋ                 Repeat the string "X " times the input: "X X X "
    s2               Split it into chunks of length 2: ["X ", "X ", "X "]
      UÐe            Upend (reverse) the even indexes: ["X ", " X", "X "]
              Ɗ€     Apply to each...
         ẋ³          ...repeat each chunk times the input...:  ["X X X ", " X X X", "X X X "]
           ŒH        ...approximately split it into halves...: [["X X", " X "], [" X ", "X X"], ["X X", " X "]]
             Ḣ       ...take the head (first item) of each: ["X X", " X ", "X X"]
              Y      Join with newlines
                     Implicit output

Pip, 25 bytes
Y"X "XaFi,aP(i%2?RVyy)@<a

A simple for loop.
Try it online!

Jelly, 7 bytes
+þị⁾ XY

Try it online! or see the results for \$n = 1, 2, ..., 8\$
How it works
+þị⁾ XY - Main link. Takes n on the left from the command line
 þ      - Yield an n×n matrix where each cell (i,j) is, for 0 ≤ i, j ≤ n:
+       -   i + j
   ⁾ X  - Yield " X"
  ị     - Index modularly into " X". Even numbers are replaced with "X" and odd with " "
      Y - Join by newlines and output

@Bubbler Edited that in

Ly, 60 51 bytes
ns1[p'Xf' f,,0G]ppl2%>l[<&s[pp0]p(10)&o&lr0Irpr>,]>

Try it online!
I thought this would be shorter, but guess I had higher expectations for the approach than was warranted. :)
The high level idea here is to build a X X X ... string on a stack, then iterate as many times as requested.  Each time time through the loop, the code prints the stack then reverses it.
ns1[p'Xf' f,,0G]ppl2%>l[<&s[pp0]p(10)&o&lr0Irpr>,]>

>> First loop, constructs the "X X X ..." pattern on a stack <<
ns1[p'Xf' f,,0G]
ns1                             # Read board size (N), save and push 1 on stack
   [p      ,,0G]                # Loop, decrement N by 2 each time
     'Xf' f                     # Push "X", pull N forward, push " ", pull N

>> Clean-up and prep for second loop <<
>>              ppl2%>
.. pp                           # Delete N and iterator from stack
..   l2%                        # Load N, push "N%2" on stack (N even/odd bool)
        >                       # Switch to "X X ..." stack

>> Second loop, print the pattern and update <<
>> >>                 l[<&s[pp0]p(10)&o&lr0Irpr>,]
.. l[<              >,]         # Loop, decrements N on stack each time
      &s                        # Save "X X ..." stack in the backup cell
        [p 0]p                  # If-then, true if top of stack is not 0
          p                     # Delete one char (means N is even)
              (10)&o            # Push a LF, print the whole stack
                    &l          # Load the "X X ..." stack from the backup cell
                      r         # Reverse the stack
                       0I       # Push copy of entry 0 (even/odd bool)
                         rpr    # Reverse, pop, reverse (pop entry 0)

>> Final clean-up <<
>> >> >>                                          >
.. >                # Switch stacks to avoid auto print
```

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