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.

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:

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

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.