Does anyone have any ideas about ways to count the number of ways an n x m grid of squares could be dissected into...

does anyone have any ideas about ways to count the number of ways an n x m grid of squares could be dissected into (1x1), (1x2), & (2x2) rectangular tiles?

I was considering trying a computer program to model it, but I'm not even sure how to start.

This is a question that comes into my head a lot when I'm in my bathroom, looking down at the pattern of tiles on the floor. (it's called a variegated pattern apparently.)

For easier version: just use (1x1) and (2x1) tiles.

Other urls found in this thread:

en.wikipedia.org/wiki/Domino_tiling.
en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity
twitter.com/NSFWRedditVideo

for starters, I know that if the total area consists of A = n x m places, the number of patterns must be less than A^A / A!,
based on the idea of there being up to A 'belongingship' categories, with each tile being one of those at random.
this does not yet restrict a category to be constrained to including only cells next to each other, or to having certain shapes.

you could probably also make graphs that connect every configuration by operations that either:
> connect two adjacent 1x1 squares into a 2x1
> split a 2x1 into two 1x1 squares
> connect two long-edge adjacent 2x1 tiles into a 2x2 tile
> split a 2x2 into two 2x1 tiles (two ways to do this)

then you maybe could analyze the topology of that graph - there would be a structure based on values that tell you a) the number of 2x1 tiles b) the number of 2x2 tiles

for 2xn, I get a result that says add the numbers in the vector that results from multiplying a vector
[1 0 0] by the matrix [[1 0 1][1 1 1][2 2 1]] raised to the nth power.

I have a bit of an idea user:
think in columns. you go from left columns to right columns.
you fill each column with numbers.
if a cell is filled you put in a 1
if a cell is filled and fills the cell in the next column in the same row (like a 2x1) block you put in a 3
if a cell is filled by a 3 from rhe column before you put in a 2
so you get a grid like this:
111132
321111
111111
132132
2 always follows 3 obviously.
this accounts for horizontsl 2x1blocks. you need an algorithm that computes all possible configurations of such a grid (watch the borders left and right).
that should be possible.
now for each configuration you need to compute replacements.
two 1s in a column next to eachother could be 2 1x1 blocks or a vertical 2x1.
two 32s over eachother could be two horizontal 2x1s or a 2x2.
now you need an algorithm for how many possibilities of replacements a 123 map configuration has and use it on all configurations.
and add all that up?
makes sense? its not elegant but seems doable

Would calculating the possible combinations for a small area and then factoring to scale work? You'd have to create 3 categories (center, side, corner).

in matlab, that'd be

mat = [1 0 1; 1 1 1; 2 2 1]
init = [1 0 0]
sum(init * mat^3)
>returns answer for a (2xn) matrix)

theoretically, I should be able to do this for any number of rows, finding a matrix that has dimensions of 2^m x 2^m

anorher thing about calculating the replacement possibilities:
you have to watch out if a replacement makes another one impossible
1 a b
1 a a
1 b a
(same letter = same block) these two replacements can not happen at the same time.
with 1x1 or 2x1 replacements ts easy because you can watch one column isolated.
imagine it like a narrow path where 2s and 3s are obstructions. so you can also view each area seperated by 2s isolated!
23
23 replacements are a bit harder because they span multiple columns

that seems good, I wonder if I could do that with matlab.

It doesn't seem like there will be any kind of real general formula though.

for 23 replacements, those can be done independent of the others (and then multiplied to get a product of possibilities), in which case, you would only have to look at repetitions of 2's, and apply the same algorithm as you did with the 1's to get the number of permutations.

during the within-column step, each column operation would give an independent number of possibilities, so you could just do a multiplication of the calculated values for each column.

so you mean if you have stacked 23's where 2x2 replacements interfere you just use the same algorithm for stacked 1x1s... makes sense.
this might actually be viable. but Im too lazy to try

about the act of multiplying things up:
if you work column wise because the columns interfere with eachother makes it necessary to have 32 stacks as special cases.
I think the best method for computing the total number of different layouts for one 123 map is to split the map into sections. a section is an area which can be viewed isolated when computing replacements.
this has basically been said before but then a section is either a verticaƶ stack of 32s or a vertical part of a column spanning from a non
t 1 to another not 1.
this nicely splitd the map into parcels which each can use basically the same algorithm to compute replacements which then can be multiplied up!

I'm pretty sure there is no easy formula. Even just tiling with dominoes results in a pretty nasty expression: en.wikipedia.org/wiki/Domino_tiling.
If the number of rows is small however, we are able to compute the result using row-by-row dynamic programming. People above have already done this with n = 2, but it can also be scaled up to reasonable values of n, say 20.

generating 132 setups would be n cases of generating a row --

the algorithm for generating a row would be essentially the same as for generating all the column connections in a column of 1s
(although, for the column connection part, all I needed to do was count the number of possibilities - here i need to generate a row)

I'm going to try to figure out that part of the algorithm

yeah, I figured out how to express the answer for n=2 using matrices, and can see how using 2^n x 2^n matrices I could make similar column-by-column matrix power solutions for larger numbers of rows

also, when doing the column thing, the sequence of the column would be parsed into sub-lengths by 2s and 3s, which each get processed independently within the column (grey parts in illustration - represent column stretches longer than 2 squares)

and if you're only doing counting, the number of permutations possible with a stretch of n 1s (or 2s, etc) is a Fibonacci sequence with
C(0) = 1, C(1) = 1, C(2) = 2, ... C(5) = 8, C(6) = 13, etc.

These kinds of problems are often solved inductively. Try thinking of a case with one square, then consider how the number of possibilities increases as you add square to form a line (1x2, 1x3, 1xn for all n>1), then consider how they increase as you add rows (2xn, 3xn, mxn for all m>1). This is a two step induction problem since you have two dimensions to consider, although you could probably formulate it in a clever single recurrence.

The main benefit of inductive solutions is that they break the problem up. Thinking of the whole plane at once can be pretty cumbersome.

Kek

It would just be (nm)!

Something tells me this is similar to a whole class of packing problems that are NP-complete, like the knapsack problem.

en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity

I think you will have to settle with either small solutions or approximate larger ones.

isnt this similar to that iphone game where you move a redblock out of an arrangement of brown blocks?

Is this a solved thing or no?

(2*2)! = 4! = 24

only 4 of those are rotationally unique

I know. I don't think OP mention whether the arrangements had to be rotationally unique or not. And an equation describing only the rotationally unique arrangements would likely be more complicated than not. Also having all the arrangements to configure could make it easier to recognize patterns within it and possibly inspire solutions.
(I'm trying to avoid the word intuition so's not to trigger Veeky Forumstards.)

ok so here's a method how you can generate all 132 maps:
first you figure out the ways to map a single row.
ill use 0 for 1 and 11 for 32 now because binary numbers. 3232 would be 1111. you dont lose information
you go through all binary numberd with n length where n is your width.
and each number you do a check: if each 1 which does not follow a 1 is followed by a 1 the number is fine.
(you can do this by going right to left through the number and having an expectation state so if you get 1 you expect 1. after that you expect 1 or 0 again. meeting the end means you get a 0)
so each number thats fine is added into a list. thid lidt will have like a million numbers whatever.
now you generate base million numbers with the length of your height. each row is a assigned a number between 0 and the length of the list. that is the index for the list entry which determined its layout.
now you have all 132 maps!
now just identify 1 stacks and 32 stacks, fibonbaci of their height (if I underdtood that correctly; I didnt think about it but if it doesnt work like that you can do other stuff) multiply every stacks permutations up and add all maps permutations up.
and you're done

bump for interest
this is a proper thread and not some popsci shit

yes, finding all rotationally unique solutions would be more complicated - you would have to compute the symmetry of your final answer in order to only partially add to the total. and that would add a lot of computational difficulty, if you're doing it computationally.

I made a simple bruteforce algorithm which calculates possible permutations and combinations...
Let w x h --> {permutations, combinations}, then:

1x1 --> {1, 1}
1x2 --> {3, 2}
2x2 --> {39, 5}
2x3 --> {1308, 11}
3x3 --> {674880, 39}
3x4 --> {968118096, 233}

Can't compute 4x4 within reasonable amount of time

Sorry I'm stupid, didnt realize 1x2 may be rotated. If 1x2 may be rotated the list is as follows:

1x1 --> {1, 1}
1x2 --> {3, 2}
2x2 --> {53, 8}
2x3 --> {1858, 26}
3x3 --> {1116048, 163}
3x4 --> {1642298496, 1125}

is there a pattern here?
If we looked at just the values given 1x1 and 1x2, we would get something that might be calculateable based on the matrices derived from the method in
also, I'm not sure how you define permutations - does that mean that each 1x1 is independent, each 2x1 is independent, each 2x1's orientation matters?
Does it have something to do with the method considered in

I tried to find a pattern but I have no formal education in pattern finding, if there's such a thing, so I did not manage.

With permutation I mean that, if "x" corresponds to an unique 1x1 square, "y" is another unique 1x1 square, "zz" is another unique 1x2 rectangle, we have the possible arrangements:

xy, yx, zz

which are the three permutations for a 1x2 grid. If counting combinations xy = yx and as such only 2 combinations exist, xy and zz.

I think only combinations matter in this case, the definition of permutations is kind of arbitrary.