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:

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

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

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

Hard solution

  • 1
    $\begingroup$ The construction of the problem seems to rely heavily on the "coincidence" $2^4=4^2$... :) $\endgroup$ – Bjørn Kjos-Hanssen Mar 6 '14 at 22:57
  • $\begingroup$ And then on $2^8 = 16 ^ 2$. $\endgroup$ – F. C. Mar 7 '14 at 8:02
  • $\begingroup$ What exactly is the condition on the diagonals? Each outgoing red line must touch exactly one other? or at least one other? $\endgroup$ – Timothy Chow Mar 7 '14 at 15:11
  • 1
    $\begingroup$ @Timothy, diagonals must continue to the next square. For example, a NW diagonal must meet a SE diagonal. Whether it has a SW or NE diagonal meeting it is absolutely unimportant (but the other diagonal must, of course, meet its match too). $\endgroup$ – Alda Mar 8 '14 at 9:21
  • 1
    $\begingroup$ Do you have a solution to the intermediate problem coming from $2^6 = 4^3$? i.e. paint the sides of cubes with two colours, then arrange the $64$ distinct cubes into one large cube with all outer faces the same colour. $\endgroup$ – Zack Wolske Mar 8 '14 at 18:00

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.

  • $\begingroup$ The corner analysis assumes that a correct tiling induces a set of 128 vertices with four red corner lines emanating from each vertex. The rules do not say whether other diagonal line configurations are allowed. $\endgroup$ – The Masked Avenger Mar 7 '14 at 17:51
  • $\begingroup$ You can also have only two diagonals meeting at a corner - look at the example solution I added. My estimation went as follows: there are exactly 128 horizontal connections: pairs of tiles joined by a horizontal line. There are 240 places for such a connection, so $\binom {240} {128}$ possibilities. Same for verticals. For diagonals, again 128 for each of the two orientations, with 225 possible positions, $\binom {225} {128}$ possibilities. Multiply them all together and you get $3.29\times 10^{272}$. $\endgroup$ – Alda Mar 8 '14 at 10:15
  • $\begingroup$ Another approach for an upper bound is by a transfer-matrix method: Dropping the condition that all squares are different, one gets an upper bound $2^{24}$ for the baby case and $2^{930}$ for the hard case. $\endgroup$ – Roland Bacher Mar 10 '14 at 17:57
  • $\begingroup$ Indeed, but tighter bounds arise from coloring interior edges and points. $\endgroup$ – The Masked Avenger Mar 10 '14 at 18:11

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.

  • $\begingroup$ Actually, there are only 8 choices for the upper-left corner, since the only lines permitted are Right, Down-Right and Down; the rest would touch the border and so are required to be empty. Interesting approach... $\endgroup$ – Alda Mar 8 '14 at 10:21

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

  • $\begingroup$ Sorry, I did not read all comments: The second suggestion is mainly Zack Wolske's comment. $\endgroup$ – Roland Bacher Mar 10 '14 at 14:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.