A combinatorial problem - counting the solutions

Question

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:

Answer 1

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.

Answer 2

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.

Answer 3

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).