Down to 39:

    1 0 1 0 2 0 2 1 0 2 1 3 3 2 3 3 1
    3 3 0 3 1 2 3 0 0 1 1 1 2 2 2 0 1
    3 2 3 2 2 0 1 0 3 0 3 3 1 1 0 2 1
    0 3 1 2 1 1 2 3 1 0 3 0 0 3 2 0 2
    0 1 1 3 3 3 1 0 1 1 2 2 3 2 0 2 0
    3 1 2 2 3 1 0 1 0 3 0 2 0 3 0 1 2
    1 1 1 2 0 2 3 2 3 3 0 0 1 2 0 0 3
    2 2 0 0 3 1 0 1 3 1 3 0 1 2 1 3 2
    0 0 2 0 0 2 0 3 1 2 1 2 1 3 3 1 3
    3 2 2 1 0 3 0 1 1 0 3 1 2 0 3 2 3
    1 3 3 0 1 3 2 2 1 3 0 2 2 0 1 3 0
    2 3 2 1 2 1 1 2 0 0 1 0 3 0 2 3 3
    1 0 3 3 2 2 1 0 2 3 2 1 0 0 3 1 2
    0 2 1 1 0 3 3 2 0 2 2 3 0 3 1 1 0
    2 1 3 2 3 0 0 3 2 2 1 3 2 1 1 0 0
    0 2 0 1 1 0 3 3 2 3 3 2 3 0 2 1 1
    2 0 0 3 1 2 2 3 3 0 0 1 1 1 3 2 0

I made some tweaks (and a bug fix or two), left it running overnight (four instances, one per CPU core)... They all get down to 12 to 14, but it seems like they stop progressing. Haven't seen 11 yet.

    Score: 12
    2 3 0 1 3 2 1 2 2 3 1 2 0 3 1 3 0
    2 1 1 2 2 1 1 0 3 3 3 3 3 2 0 0 0
    2 2 1 1 0 3 3 3 1 0 2 0 1 3 3 0 2
    3 2 0 1 1 1 0 3 2 1 3 0 2 2 0 3 1
    1 2 1 3 1 0 2 2 0 2 0 0 3 3 1 1 0
    1 1 3 3 0 2 2 0 0 1 3 1 0 2 3 1 2
    3 2 3 0 2 1 0 0 0 0 1 2 1 3 2 1 3
    1 3 3 2 3 1 0 1 2 2 0 3 0 1 2 0 2
    2 0 2 1 3 0 3 1 0 2 3 1 2 0 0 1 3
    3 0 2 0 1 3 1 2 3 3 2 1 1 2 2 0 0
    0 0 2 3 2 3 2 0 2 1 0 3 1 1 1 3 3
    2 0 1 3 3 0 2 3 3 0 1 1 0 1 2 2 1
    0 1 0 2 1 0 2 3 1 3 2 2 2 1 3 0 3
    3 2 2 2 0 2 0 1 1 1 1 3 3 0 3 2 0
    3 3 0 3 2 1 3 2 1 0 0 1 2 0 1 2 2
    1 3 3 0 0 3 1 3 1 2 0 2 3 2 0 2 1
    0 1 3 0 2 2 3 1 3 2 2 0 0 0 1 3 1

Edit: I can't reply to you, so...

http://pastebin.com/m33bccec1

It's not pretty, but I did a few things. Instead of taking the top n candidates and breeding them randomly, I kept all of them (NUM_STATES 200 and KEPT_STATES 200), but weight them according to score. So the best scores have the highest chance of passing their DNA down to the next generation, but the occasional loser gets lucky too.

Mutation is also weighted, so the most likely number of mutations is zero, but it's possible to have up to 4. Increasing this value made the performance go down, but it's also possible that there is no way to get to a solution by incrementally tweaking a decent attempt. Which could explain why I'm stuck at 12.

There are a few optimizations that may or may not make a difference, for instance in the scoring function. I think the pick_best_states function was not actually picking the best states. If you had two states with the same score, the first one is kept, but the next one is not. I fixed this. The stupid thing is, with NUM_STATES and KEPT_STATES at 200, it's basically an n^2 sort now. I never bothered to improve that.

Finally, compiled with -O3 and let 'er rip.

I'm not sure minimizing the score (at least, until you get to 0) is interesting, but anyway, I wrote a simple hill-climbing-with-random-perturbation routine and let it run over and over for the last couple of days. So far my best has a score of 10:

12032213310013002 21301001102213023 30120303220111321 03330220131122010 22313133001012230 03123321011233102 20313010123321102 03022111302120233 31232100023232131 03201103213001212 11000232021331223 20221213031300031 13130132102302302 31103210230220313 12310021322030311 21012022213103330 12201332333120100

Something that might help would be to have the grids in some sort of canonical form: as swapping rows and columns doesn't change the score, for every configuration there is a reordering such that the whole grid value is minimal (i.e. if we read out as a 279 digit number). Intuition says that if grids were brought in such a canonical form, recombination might work better.

Link to a diff of your fixes/tweaks?

I've only got to 30 here running 8 instances of mine.

(Also, I imagine this could probably benefit from a really fast PRNG, like an LCG.)

34 here (after some tweaks):

  0 0 0 0 0 1 1 1 2 2 2 2 2 3 3 3 3
  0 1 1 3 3 0 1 2 0 1 2 3 3 0 2 2 3
  0 1 2 2 3 0 0 0 3 3 3 1 2 1 1 2 1
  0 2 3 3 2 1 3 3 1 1 0 0 0 2 3 2 1
  0 3 0 1 1 3 2 3 1 2 1 1 3 3 0 0 2
  1 1 3 2 0 3 0 1 3 0 1 2 3 2 2 0 2
  1 2 0 2 1 0 2 3 3 0 2 3 0 1 3 1 0
  1 3 0 2 2 2 3 0 2 1 0 1 1 0 1 3 3
  2 0 1 2 1 0 3 1 3 2 3 0 1 3 2 0 1
  2 0 3 1 0 2 2 1 0 1 3 2 0 1 0 2 3
  2 1 3 1 0 3 2 0 2 3 2 3 1 2 0 3 0
  2 3 1 3 2 1 0 2 3 3 0 1 2 0 0 1 2
  3 0 2 3 2 3 0 1 1 2 3 0 1 0 2 1 0
  3 1 2 0 1 1 3 2 0 3 0 2 3 2 3 0 0
  3 2 2 0 3 1 1 3 2 0 1 0 1 1 0 3 2
  3 2 3 1 3 2 1 0 0 0 1 0 2 3 2 1 1
  3 3 2 0 1 2 1 0 1 2 2 3 0 0 1 0 3

I think about 51, I haven't been saving the best so far. I'll tee it to a file from now on.

Edit: Oops, my random-restart code had an obvious bug. It's probably not very useful anyways, so I removed it.

http://pastebin.com/m63191b11

Try just placing 73 1's. You need to be able to place that many, but I can't get more than 65.

I've got 67 just using random placements with heuristics, programmed in Python. Apparently they've got 73 (which is 289/4 rounded up), and that's why they think this might be possible.

I've placed 74 using an IP solver

      1 1 . . . . . 1 1 . . . . . 1 . .
      . 1 1 1 1 . . . . . . . . . . . .
      1 . 1 . . 1 . . . . . 1 . . . . 1
      1 . . 1 . . 1 . . . 1 . . . . 1 .
      1 . . . 1 . . . . 1 . . . 1 . . .
      . . . 1 . 1 . 1 . . . . . 1 . . .
      . 1 . . . 1 1 . . 1 . . . . . . .
      . . 1 . . . 1 1 . . . . 1 . . . .
      . . . . 1 1 . . 1 . . . 1 . . 1 .
      . . 1 . . . . . 1 1 1 . . . . . .
      . . . . 1 . . 1 . . 1 1 . . . . .
      . . . . . . 1 . 1 . . 1 . 1 . . .
      . . . 1 . . . . . 1 . 1 1 . 1 . .
      . 1 . . . . . . . . 1 . 1 1 . . 1
      . . 1 . . . . . . . . . . 1 1 1 .
      . . . . 1 . 1 . . . . . . . 1 . 1
      . . . . . . . 1 . 1 . . . . . 1 1

The solver chokes on anything larger than a 6x6 grid, but I've had good luck adding one row at a time to a smaller solution.

http://pastebin.com/m4c4696af

edit: He mentions that he already found a size 74 set in one of the linked pdfs. http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17.pdf