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:

exactlyone other? orat leastone other? $\endgroup$ – Timothy Chow Mar 7 '14 at 15:1111more comments