Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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×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×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.
share|improve this question
    
I suppose tiles cannot be rotated? –  Martin Büttner Aug 4 at 7:10
    
@MartinBüttner No. You must use the set of 13 tiles provided exactly as they appear. –  Calvin's Hobbies Aug 4 at 7:12
    
Is there a limit to how many times you can use each tile? I see in your example you used one tile twice. –  Teun Pronk Aug 4 at 8:38
    
@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). –  Calvin's Hobbies Aug 4 at 8:39
    
@Calvin'sHobbies Is it safe to assume there is always a possible solution? –  Teun Pronk Aug 4 at 8:40

2 Answers 2

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

share|improve this answer
11  
Neopolitan Minecraft... –  Calvin's Hobbies Aug 4 at 11:26
    
can you add a bigger picture? i'm curious how it would look –  proud haskeller Aug 4 at 13:26
1  
@proudhaskeller Larger image: Imgur. Wallpaper maker: link –  bitpwner Aug 4 at 17:59
1  
This sure looks periodic - what am i missing? –  proud haskeller Aug 4 at 18:14
    
Almost periodic.. example with more contrast here: Imgur –  bitpwner Aug 4 at 18:24

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.