Fill the Screen with Wang Tiles
Python (565 - 150 = 415)

Btw... it seems that we can't naively just decide the next tile by the its left and top tile. There's some combination of tiles that will fit each other.
This solution fills in left->right, top->down brute forces through all possible combinations and backtracks if a tile cannot fit in. 

For more info about the 13 tile proof: An aperiodic set of 13 Wang tiles 

Width and Height are specified by W and H

Red, Green, Blue, Yellow and Noir specified by R, G, B, Y and N

import Image,sys
W,H=map(int,sys.argv[1:])
R=99
G=R&lt;&lt;8
B=G&lt;&lt;8
Y=G+R
N=0
s="RGB";u=32;g=[[0,0]]*W*H;k=f=0
def t(c):i=Image.new(s,(2,2));k=i.load();q=16;k[1,0],k[1,1],k[0,1],k[0,0]=c;return i.resize([64]*2).rotate(45).crop((q,q,q+u,q+u))
while k&lt;H*W:
 z=g[k][1];v=-1;j=k/W;i=k%W
 while z&lt;13:
    l=map(eval,"GGGRRRYBGGYBGGBBRRGYYNNNNYBGBGBGRGRYRGGRRGGBBYYYYNNN"[z::13])
    if(j&lt;1or g[(j-1)*W+i][0][2]==l[0])and(i&lt;1or g[j*W+i-1][0][1]==l[3]):g[k]=[l,z+1];v=1;z=99
    z+=1
 g[k][1]*=(v&gt;0);k+=v
m=Image.new(s,(W*u,H*u))
for e in g:m.paste(t(e[0]),(f%W*u,(f/W)*u));f+=1
m.show()


Output. Not the actual color scheme... cuz too glaring. This might make some interesting interior decor patterns...: