Fill the Screen with Wang Tiles

Question

It has been proven that the following 13 square Wang tiles always tile the plane aperiodically. This means that when the squares are arranged in a grid with all neighboring sides the same color, a translation of the pattern will never match up with itself.

Wang tiles

We'll represent each tile textually by a ×ばつ3 grid filled with spaces at the center and corners, and the numbers 1 through 5 instead of the colors red, green, blue, yellow, grey, at the edges:

 2 2 2 1 1 1 4 3 2 2 4 3 2
1 2 1 3 2 3 2 1 3 1 3 2 4 4 4 4 4 5 4 5 5 5 5 5 5 4
 3 2 3 2 3 2 1 2 1 4 1 2 2

Goal

Your task is to write a program that takes in a width and height and outputs a valid Wang tile grid with those dimensions. A valid tiling is one in which all the adjacent tile edges have the same color (or number). The smallest program in bytes wins.

Your input should come from stdin or command line arguments and output should go to stdout. The exact input format can be anything reasonably obvious, like >>> wangtiler 3 2. The width and height are always positive integers.

Example (width = 3, height = 2)

Notice that when we layout the textual tiles the neighboring edges form necessary redundant pairs of digits:

 1 2 1 
2 11 22 1
 2 3 2 
 2 3 2 
4 55 55 4
 1 2 2 

^{(This is NOT the proper output format.)}

We can compress these horizontally and vertically to get:

 1 2 1 
2 1 2 1
 2 3 2 
4 5 5 4
 1 2 2 

This compressed format is the proper output format you must use. The odd numbered lines must include their trailing space.

Graphical Bonus

Instead of having any textual output, your program may output an image of the tiled grid. The graphical tiles must be made up of four 45-45-90 triangles arranged in a square and use five easily distinguishable colors like the tiles above. The black borders are not required. The graphical tiles must be at least ×ばつ32 pixels in size. No "compression" is applied to them.

Example bonus image: (same grid as example above)

bonus example

The bonus is worth minus 150 bytes.

Notes

• You must use this set of 13 tiles.
• Tiles may not be rotated.
• Tiles may appear any number of times (including none at all).
• You may assume a valid tiling with any dimensions is possible.

• Martin Ender: I suppose tiles cannot be rotated?
• Calvin's Hobbies: @MartinBüttner No. You must use the set of 13 tiles provided exactly as they appear.
• Teun Pronk: Is there a limit to how many times you can use each tile? I see in your example you used one tile twice.
• Calvin's Hobbies: @TeunPronk Nope. Use them however many times you want (of course you may be forced to use more of some to properly match the edges).
• Teun Pronk: @Calvin'sHobbies Is it safe to assume there is always a possible solution?

Answer 1

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<<8
B=G<<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<H*W:
 z=g[k][1];v=-1;j=k/W;i=k%W
 while z<13:
 l=map(eval,"GGGRRRYBGGYBGGBBRRGYYNNNNYBGBGBGRGRYRGGRRGGBBYYYYNNN"[z::13])
 if(j<1or g[(j-1)*W+i][0][2]==l[0])and(i<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>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...:

enter image description here

• Calvin's Hobbies: Neopolitan Minecraft...
• proud haskeller: can you add a bigger picture? i'm curious how it would look
• Vectorized: @proudhaskeller Larger image: Imgur. Wallpaper maker: link
• proud haskeller: This sure looks periodic - what am i missing?
• Vectorized: Almost periodic.. example with more contrast here: Imgur

Answer 2

GolfScript, 200 characters

~\:W*):R;1,{)\:C"=QCy_~{MTKAis]?OyJE?~WvM"[64 2400]{base}/@{>}+,{:T;[C,W<!{C W~)=T 64/^8/8%}*C,W%0>{C-1=64/T^8%}*]0-!},1<.!!{1,+}*+.,R<}do);W/.0={' '512円/8%`}%n@{.[.0=8%\{' '64円/8%}/n]\{' '8円/8%`}%n}/

ASCII version with no graphic output. Give the input on STDIN - try here. The code uses a plain backtracking approach and fills the space line by line.

Examples:

> 3 2
 1 2 1
2 1 2 1
 2 3 2
5 4 4 5
 2 2 1
> 8 5
 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2
 2 3 2 3 2 3 2 3
5 4 4 5 5 4 4 5 5
 2 2 4 2 2 2 4 2
5 4 5 5 4 5 4 4 5
 2 1 1 2 1 2 1 1
1 3 2 1 2 1 3 2 1
 2 2 2 3 2 2 2 2
5 4 5 4 4 5 4 5 4
 2 1 2 2 1 2 1 2

Graphical Bonus, score 122, 272 characters - 150 bonus

~\:W*):R;1,{)\:C"=QCy_~{MTKAis]?OyJE?~WvM"[64 2400]{base}/@{>}+,{:T;[C,W<!{C W~)=T 64/^8/8%}*C,W%0>{C-1=64/T^8%}*]0-!},1<.!!{1,+}*+.,R<}do);W["P3\n"32W*" "3,32ドル*n 1n]\{{:^;512:X;16,{[^8%]1$*[^X/8%]31*@.+>[^64/8%]31*++32<}:F%8:X;16,-1%{F}%+}%zip{{+}*{8+2base(;~}%' '*n}/}/

Same basic code with a different output formatter. The output is an image in PPM format (i.e. simply redirect the output to a file image.ppm). The colors are slightly different than the tiles in the question, but clearly distinguishable (1->blue, 2->green, 3->cyan, 4->red, 5->magenta).

16x12 example:

16x12 wang example

Answer 3

Haskell, 208 bytes

p x|x<2/3=(3!x)3"3212"3
p x=(0.5!x)1"45423"2
f=floor
(k!x)l s m=do{i<-[0,x..];[' ',s!!(2+f(i+x)-f i)]}:do{i<-[0,l*x..];s!!mod(f i)m:" "}:p(k*x)
t n=take2ドル*n+1
main=do(w,h)<-readLn;putStr.unlines.t h$t w<$>p 1

No searching, just math. Example run: given (8,5) on stdin, outputs

 2 2 2 2 2 2 2 2 
4 5 4 5 4 5 4 5 4
 1 2 1 2 1 2 1 2 
3 2 3 2 3 2 3 2 3
 2 3 2 3 2 3 2 3 
4 5 5 4 4 5 5 4 4
 4 2 2 2 4 2 2 2 
4 4 5 4 5 5 4 5 4
 1 1 2 1 1 2 1 2 
3 2 1 3 2 1 3 2 3
 2 2 2 2 2 2 2 3 

Run online at Ideone

• emanresu A: If you ported this to something golfier like Perl, it might beat golfscript, which would be funny.