# A combinatorial problem - counting the solutions

Consider a square. There are 16 ways to paint its sides with two colors. For convenience, we will represent one color with a blank side, and the other - with a line drawn from the squares' center to the middle of the side.

Here are the 16 possible squares:

The problem is to count the ways to put them together in a 4x4 square, such that:

1. Each square is used once.
2. It is not permitted to rotate or reflect squares.
3. Each outgoing line must join another line.
• Of course, it means no line is allowed to touch the square's border.

Here is an example of a valid solution:

I know, from a simple backtracker program I've written, that the number of valid solutions is 652. But can it be proven mathematically?

Actually, the problem I described is a "toy" version of the real problem: in addition to the sides of the square, consider also the diagonals. Here are the 256 possible squares:

How many solutions exist? Here, of course, we need to place all the squares in a 16x16 square, with limitations as above. I managed to get a not very tight upper bound of about $3.29 \times 10^{272}$, but I have no idea how to get the actual number.

Edit: Here is an example solution of the hard problem:

• The construction of the problem seems to rely heavily on the "coincidence" $2^4=4^2$... :) Commented Mar 6, 2014 at 22:57
• And then on $2^8 = 16 ^ 2$. Commented Mar 7, 2014 at 8:02
• What exactly is the condition on the diagonals? Each outgoing red line must touch exactly one other? or at least one other? Commented Mar 7, 2014 at 15:11
• @Timothy, diagonals must continue to the next square. For example, a NW diagonal must meet a SE diagonal. Whether it has a SW or NE diagonal meeting it is absolutely unimportant (but the other diagonal must, of course, meet its match too).
– Alda
Commented Mar 8, 2014 at 9:21
• Do you have a solution to the intermediate problem coming from $2^6 = 4^3$? i.e. paint the sides of cubes with two colours, then arrange the $64$ distinct cubes into one large cube with all outer faces the same colour. Commented Mar 8, 2014 at 18:00

The 4x4 problem is similar to labelling 16 of the interior 24 edges black with some constraints: the top 3 edges must have at least one black edge, and the top 7 edges have at most 68 admissible colorings. I can't see a quick way to get 652, but showing an upper bound of half a million follows from the observations above.

Using a similar analysis on the larger puzzle gives an upper bound of edge configurations of $\binom{480}{256}$ which is less than $10^{150}$. Another analysis of the corners gives $\binom{225}{128}$; multiplying these together gives an improved upper bound which is still weak. It may be possible to improve these bounds to below a googol, but I don't see how yet.

• The corner analysis assumes that a correct tiling induces a set of 128 vertices with four red corner lines emanating from each vertex. The rules do not say whether other diagonal line configurations are allowed. Commented Mar 7, 2014 at 17:51
• You can also have only two diagonals meeting at a corner - look at the example solution I added. My estimation went as follows: there are exactly 128 horizontal connections: pairs of tiles joined by a horizontal line. There are 240 places for such a connection, so $\binom {240} {128}$ possibilities. Same for verticals. For diagonals, again 128 for each of the two orientations, with 225 possible positions, $\binom {225} {128}$ possibilities. Multiply them all together and you get $3.29\times 10^{272}$.
– Alda
Commented Mar 8, 2014 at 10:15
• Another approach for an upper bound is by a transfer-matrix method: Dropping the condition that all squares are different, one gets an upper bound $2^{24}$ for the baby case and $2^{930}$ for the hard case. Commented Mar 10, 2014 at 17:57
• Indeed, but tighter bounds arise from coloring interior edges and points. Commented Mar 10, 2014 at 18:11

This suggests a different approach to bounding the number of configurations.

E.umerate a sequence of partial configurations. Note that there are 32 choices to place a block in the upper left corner. When that block is placed, there will be 31 or 32 possibilities for a block directly below, giving some number between 1020 and 990 for placing two blocks. If we use this to count configurations which have a third block placed just to the right of the first block, there will be roughly 31,000 possibilities, and definitely less than 2^15 possibilities. Using computers, it should be possible within a day to compute a sequence that counts the number of partial configurations confined to an upper left triangular region of i blocks, for i ranging from 1 to 7 or 8. With that sequence, bolstered by a random sampling of configurations and continuing a count starting from those, one should be able to project a solution count that is closer to actual than the simple bounds given above. It can be shown that an upper bound is 32^i for i up to 8, and the hope is to establish a better approximation through limited use of computational brute force.

• Actually, there are only 8 choices for the upper-left corner, since the only lines permitted are Right, Down-Right and Down; the rest would touch the border and so are required to be empty. Interesting approach...
– Alda
Commented Mar 8, 2014 at 10:21

Not an answer but similar examples for sharpening tools:

Consider all $2^6=64$ possible decorated regular triangles where a decoration is a set of segments joining the center to some vertices or to midpoints of some edges. Identifying such a triangle with its
opposite (through a central symmetry), one can try to tile the regular triangle obtained by inflating a standard regular triangle by a factor $8$ with all $8^2=64$ possible forms (up to translation and central symmetry). The obvious compatibility requirement is: each decorating segment continues in a straight way at a vertex or at a midpoint.

I ignore whether there are solutions and how many but the complexity of this problem is exactly between the original baby version (with $16$ squares) and the hard version (with $256$ squares).

Another intermediate problem is given by considering regular cubes: joining the midpoint (barycenter) by segments to midpoints of a subset of faces one has again $2^6=64$ different decorated cubes and one can ask for tilings of the $4\times 4\times 4$ cube using all $64$ possible decorated cubes. (This non-planar version is of course more difficult to visualize.)

This example can of course be generalized to higher dimensions: The next case involves $256=4^4$ different decorated hypercubes of dimension $4$. In the general case, we have $2^{2d}=4^d$ possible decorated $d-$dimensional hypercubes and we want to tile a $4\times 4\times\cdots \times 4$ hypercube of dimension $d$ using all possible decorated hypercubes in a consistent way (all decorations go on at midpoints of facets).

• Sorry, I did not read all comments: The second suggestion is mainly Zack Wolske's comment. Commented Mar 10, 2014 at 14:16