I’ve got an interesting tiling problem, I have a large square image (size 128k so 131072 squares) with dimensons 256×512… I want to fill this image with certain grain types (a 1×1 tile, a 1×2 strip, a 2×1 strip, and 2×2 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 2×2 square grains are randomly placed until exhaustion. 2) 1×2 and 2×1 grains are randomly placed alternatively until exhaustion 3) the remaining 1×1 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 1×2 and 2×1 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 8×8 or 16×16. 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(2×1)=P(1×2)=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(1×2)=p(2×1)=0.5) the mini-image 16×16 isn’t even iteratively solvable.. So it’s pretty obvious how difficult it is to randomly solve this for anything greater than 8×8 sizes.. So I’d love to hear some ideas. Thanks
2
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.
2