Take a square. How many ways are there to draw or not draw a line from the center to each of its sides? 16, of course. Here are all the different squares:
Now, how many ways are there to put those squares in a 4x4 square so that all lines meet up (and no lines touch the border)? Of course, rotating the squares is also not allowed. There are 652 solutions (counting in all rotations and reflections). I got that easily with a simple backtracking program. But that's the easy version of the problem. To get the hard one, just add diagonals. Now there are 256 different squares:
How many solutions exist for this one (to clarify: now we're trying to arrange all of them in a 16x16 square)? I'm a CS major, so I tried throwing everything I learned about algorithms at this one. I solved it as an Exact Cover problem, and as a SAT problem (well, #SAT, to be precise). Either way, it's way, way too big for all the software I have available.
My only hope now is that it can be solved mathematically, but I lack the tools and knowledge. Save all that's left of my sanity, please!
Here is an approach that avoids backtracking, but will probably be too slow for the $8 \times 8$ diagonal one. I will describe it for the $4 \times 4$ with diagonals. You can use a $10$ bit binary string to define the lines connecting one column to another-there are four potential horizontal lines and six potential diagonal lines. For each string count the number of legal first columns. There are three more choices (eight possibilities) and the constraint is that all four squares do not have a single active line coming in. The case with all four horizontals active forces all the verticals to be active, so there is just one possibility for that. The case with all ten active allows all eight possibilities in the vertical direction. You finish with a list of the number of ways for each string to represent the line between the first and second columns. Then for each string between the second and third columns, loop over the strings between first and second, count the choices for the verticals in the second column and sum up. This is $2^{20}$ loops, just a million. Keep going, noting that the fourth output must be all zeros. The mantra is forget what you don't need to know-when you get to the third/fourth column joint, you need to know how many ways there are to generate a given string, but not what they look like.
Unfortunately, this would require $(2^{22})^2$ loops for the $8 \times 8$ with diagonals, which is too many for my computer.