Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've got an interesting tiling problem, I have a large square image (size 128k so 131072 squares) with dimensons 256x512... I want to fill this image with certain grain types (a 1x1 tile, a 1x2 strip, a 2x1 strip, and 2x2 square) and have no overlap, no holes, and no extension past the image boundary. Given some probability for each of these grain types, a list of the number required to be placed is generated for each.

Obviously an iterative/brute force method doesn't work well here if we just randomly place the pieces, instead a certain algorithm is required. 1) all 2x2 square grains are randomly placed until exhaustion. 2) 1x2 and 2x1 grains are randomly placed alternatively until exhaustion 3) the remaining 1x1 tiles are placed to fill in all holes.

It turns out this algorithm works pretty well for some cases and has no problem filling the entire image, however as you might guess, increasing the probability (and thus number) of 1x2 and 2x1 grains eventually causes the placement to stall (since there are too many holes created by the strips and not all them can be placed).

My approach to this solution has been as follows: 1) Create a mini-image of size 8x8 or 16x16. 2) Fill this image randomly and following the algorithm specified above so that the desired probability of the entire image is realized in the mini-image. 3) Create N of these mini-images and then randomly successively place them in the large image.

Unfortunately there are some downfalls to this simplification. 1) given the small size of the mini-images, nailing an exact probability for the entire image is not possible. Example if I want p(2x1)=P(1x2)=0.4, the mini image may only give 0.41 as the closes probability. 2) The mini-images create a pseudo boundary where no overlaps occur which isn't really descriptive of the model this is being used for. 3) There is only a fixed number of mini-images so i'm not sure how random this really is.

I'm really just looking to brainstorm about possible solutions to this. My main concern is really to nail down closer probabilities, now one might suggest I just increase the mini-image size. Well I have, and it turns out that in certain cases(p(1x2)=p(2x1)=0.5) the mini-image 16x16 isn't even iteratively solvable.. So it's pretty obvious how difficult it is to randomly solve this for anything greater than 8x8 sizes.. So I'd love to hear some ideas. Thanks

share|improve this question
    
16x16 with half 1x2 and 2x1 is trivially solvable, just tile each half with one style of block. –  NovaDenizen Oct 6 '12 at 21:36
    
While I agree that is very simply solvable, the constraint of his particular problem requires a random distribution of the grains, so unfortunately a simplification like that would not work. –  user67081 Oct 6 '12 at 23:12
add comment

1 Answer

up vote 0 down vote accepted

I had a similar problem recently, trying to find polyimino patterns that would fill a board. A simple backgracking program worked quite well. Just place random tiles and backtrack when you cannot place and have not met the constraints.

share|improve this answer
    
I actually just discussed my problem quite a bit with someone and we agreed backtracking may be the only way to hit the desired probabilities while retaining a random distribution of the grains. My thought is, following the placement algorithm described above, when the (1x2) and (2x1) grains become difficult/impossible to place in the remaining spots, I will attempt to re-order the problem neighbor grains to a certain degree. I'll have to try it but I think it might work. Thanks! –  user67081 Oct 6 '12 at 22:30
    
A greedy annealing solution might work too. Start by stamping random grains all over the image. Greedily try clumps of random stamps, and only retain the changes that make your statistics more closely fit the target. –  NovaDenizen Oct 8 '12 at 17:33
add comment

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.