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: 


*

*Each square is used once.

*It is not permitted to rotate or reflect squares.

*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:

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