# 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$... :) – Bjørn Kjos-Hanssen Mar 6 '14 at 22:57
• And then on $2^8 = 16 ^ 2$. – F. C. Mar 7 '14 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? – Timothy Chow Mar 7 '14 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 Mar 8 '14 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. – Zack Wolske Mar 8 '14 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. – The Masked Avenger Mar 7 '14 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 Mar 8 '14 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. – Roland Bacher Mar 10 '14 at 17:57
• Indeed, but tighter bounds arise from coloring interior edges and points. – The Masked Avenger Mar 10 '14 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 Mar 8 '14 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. – Roland Bacher Mar 10 '14 at 14:16