Answer to Q1: All of the 261.
I looked at this question because of a video of Matt Parker and wrote an algorithm to find solutions. See here for an example of how a solution would look like. I dumped all solutions on github. For some cases I list multiple solutions. The files start with a number followed by an underscore and the number is between 0 and 260 corresponding to one of the unfoldings in this list.
129 <--- Number of unfolding (this time 0-indexed)
[[-2, -2, 0], [1, 1, 1]] <---- the box, we put it in
Boolean Program (maximization, 1152 variables, 428 constraints) <---
some information to ignore
32.0 <--- How many of the voxels in the cube are covered (here it
happens to be all of them)
[(-2, -2, 0), (-1, -2, 0), (-1, -2, 1), (-1, -1, 0), (-1, 0, 0), (-1,
1, 0), (0, -2, 1), (1, -2, 1)]
[(-2, -2, 1), (-2, -1, 0), (-2, -1, 1), (-2, 0, 0), (-2, 1, 0), (-1,
-1, 1), (0, -1, 1), (1, -1, 1)]
[(-2, 0, 1), (-1, 0, 1), (0, 0, 1), (1, -2, 0), (1, -1, 0), (1, 0, 0),
(1, 0, 1), (1, 1, 1)]
[(-2, 1, 1), (-1, 1, 1), (0, -2, 0), (0, -1, 0), (0, 0, 0), (0, 1, 0),
(0, 1, 1), (1, 1, 0)]
(the last rows are then the coordinates of the copies of the
unfolding, whatever sticks out of the box fits in another one..)
Here is an example of one of the two one that fit in a 4x4x2 box ( in an exploded view, you can shift them together and they neatly fit into a 4x4x2 box, which can then be stacked to obtain a tiling.:
Answer to Q2: One way is to use integer programming.
The basic idea is to take a box with volume divisible by 8 as a fundamental domain and to cover it as much as possible with non-overlapping copies of an unfolding and make sure that the stuff that sticks out of the bottom actually fits into gaps at the top and so on.
Here's a two-dimensional example:
The tile:
A 5x6 box filled with copies of that tile:
A tiling produced from this:
This can be formulated a as an integer program and it turns out that those 261 unfoldings all have feasible solution for some smallish box (for most 4x4x4 is enough).
Setting up the integer program is just a few lines of sage:
from sage.combinat.tiling import Polyomino
import itertools
def get_mod_points(point, diff):
for coeffs in itertools.product([-1, 0, 1], repeat=diff.length()):
yield vector([diff[i]*coeffs[i] + point[i] for i in range(diff.length())])
def milp_mod_box(tile, inner_box, outer_box, solver=None):
# tile, inner_box and outer_box are `Polyomino`.
begin, end = inner_box.bounding_box()
diff = vector(end) - vector(begin)
diff += vector([1]*diff.length())
tiles = [Q for Q in tile.isometric_copies(outer_box)]
p = MixedIntegerLinearProgram(solver=solver, maximization=True)
x = p.new_variable(binary=True)
for i in inner_box:
cons = p.sum(sum([int(j in T) for j in get_mod_points(i, diff)])*x[T] for T in tiles) == 1
p.add_constraint(cons)
for i in outer_box:
p.add_constraint(p.sum(x[T] for T in tiles if i in T) <= 1)
p.set_objective(p.sum(x[T] for i in inner_box for T in tiles if i in T))
return p, x
Here we optimize for having as much voxels filled in the box as possible, but only so that the solutions look nicer, it would give valid tilings even without setting that objective.
A similar integer programming approach could be used to prove that a certain polyomino is not a space filler: We can check for larger and larger boxes that if it is not possible to cover them completely with non-overlapping copies of the original polyomino, but this wasn't necessary.
Update:
I added 3d-plots of all solutions to 3d-renderings of all 261 unfoldings page. When you click on the number of each one you get a 3d-rending of copies of that unfolding mostly in a box (drawn in grey), which then can be used to tile the plane.
Note this is a different order than the one above (and it starts indexing with $1$.
#213 is the Dalí-unfolding, needs 8 pieces in the prototile.
#3 is the only one that only needs 3 pieces (in a 4x3x2 box) (what a coincidence..)
#72 and #159 are the ones that perfectly fit in a 4x4x2 box.
#139 needs a long 8x2x2 box.
Best Answer
Linear unfoldings
A category of unfoldings that can always be tiled are the linear ones. Let's say an unfolding is branching if there is a (d-1)-hypercube with at least 3 adjacent hypercubes. I then define linear unfoldings as those that don't branch.
Examples:
Here is a table of how many unfoldings are linear
Now we can use some results of the article in CCCG you linked. In particular lemma 2, which states:
Because I have restricted to linear unfoldings, the tree $T$ is linear. Therefore there is a path trough all vertices in $T$. From the lemma it then follows: if we follow the unfolding from one end to another, we will only move in one direction of each dimension. Let's call these directions the positive direction of each dimension in (d-1)-space. Now lets associate each (hyper-)cube with a point in $\mathbb Z^{d-1}$. fix the start cube at $(0, 0, \ldots, 0)$, we can give the others coordinates as well. For the first example this will look like this:
$$(0,0,0),(0,1,0),(1,1,0),(1,1,1),(2,1,1),(2,2,1),(3,2,1),(3,2,2)$$
Notice that between adjacent cubes exactly one coordinate increases by 1. Because of this the sum of the coordinates also increases by one each step. Now suppose we place a copy of the unfolding with it's start cube at $(0,1,-1)$:
$$(0,1,-1),(0,2,-1),(1,2,-1),(1,2,0),(2,2,0),(2,3,0),(3,3,0),(3,3,1)$$
There cannot be any overlap with the other one. Suppose otherwise, there is a cube in common. Let's label the cubes of the unfolding from $0$ to $2d-1$, from start to finish. Now suppose the conflicting cube has label $i$ in the original unfolding, and $j$ in the copy. Then the sum of coordinates of that cube is $(0+0+0)+i=(0+1+-1)+j$, which gives $i=j$. That would imply all cubes of the unfolding conflict. But then we get $(0,0,0)=(0,1,-1)$ for the start cube, a contradiction.
We get a space-filling tiling if we place copies at each point where the sum of coordinates is a multiple of $2d$.
There is no overlap, by the argument as before. If two (hyper-)cubes of two different foldings conflict, they have the same coordinate sum modulo $2d$. This implies they have the same index in the unfolding, which implies the start cubes of both overlap leading to a contradiction.
There is also no empty spaces. By definition each spot where the sum of coordinates is a multiple of $2d$ is filled by all start cubes. All spots with remainder $i$ modulo $2d$ then get filled with the cubes at index $i$.
Expanding the method
I have added this section to expand on my comments. It demonstrates how the method described can be expanded to proof more unfoldings tileable. As a running example I will use the class of crosses.
A multi-dimensional cross is an unfolding of the $d$-cube, which has $2d$ dimension-$(d-1)$ cubes at the following coordinates:
$$\begin{align}\{&(0,0,\ldots,0);& &(-1,0,\ldots,0);& &(0,-1,0,\ldots,0);& &\ldots;& &(0,0,\ldots,-1);&\\ &(2,0,\ldots,0);& &(\quad 1,0,\ldots,0);& &(0,\quad 1,0,\dots,0);& &\ldots;& &(0,0,\ldots,\quad 1)\}& \end{align}$$
If you tried to tile a cross without rotation/reflection, you will get stuck. This means we can't simply use the mod $2d$ method above. Therefore we need to expand the method to fit multiple orientations of an unfolding. For the cross it is sufficient to use two orientations, the original and the one with the long end the other way. I will show that these together tile the plane by an injective mapping of their cubes onto $0, \ldots, 4d-1$.
This mapping will be a linear equation of the coordinates, modulo $4d$. For the cross I will use the following mapping: $f(x_1, x_2, \ldots, x_{d-1}) = 1\cdot x_1 + 3\cdot x_2 + 5 \cdot x_3 + \ldots + (2d-3)\cdot x_{d-1} \mod 4d$.
So what will a cross look like after applying this mapping. Obviously the center cube, $(0,\ldots,0)$ is mapped to $0$. The extra cube $(2,0,\ldots,0)$ is mapped to $2$. All the other cubes will be mapped to $\pm (2i+1) \mod 4d$ for $i=0$ to $d-1$. The image of the mapping will look as follows (for d=5):
Now we do the same for the rotated cross. Note that inverting an even number of axes is equivalent to an 180° rotation. We say that the rotated cross is formed by inverting the cross along $x_1$ and $x_2$. The inversion along $x_2$ swaps the cubes at $(0,1,0,\ldots,0)$ and $(0,-1,0,\ldots,0)$; but that still gives the same shape. Similarly the inversion along $x_1$ swaps $(1,0,\ldots,0)$ and $(-1,0,\ldots,0)$, but it also moves $(2,0,\ldots,0)$ to $(-2,0,\ldots,0)$. If we apply the mapping to the rotated cross, the image will be mostly the same. There is only one difference, corresponding to the move of the extra cube.
If we then move the rotated cross in $(d-1)$-space, the image after mapping gets rotated. If we move the rotated cross in the right way (rotate 11), we can get the image to look as follows:
which perfectly fills the gaps the original cross left behind. This implies we can fill space by placing a cross at each position where $f(x_1,\ldots, x_{d-1})=0$, and a rotated cross at each position where $f(x_1,\ldots, x_{d-1})=2d+1$.
This method allows us to show that 248 / 261 hypercube unfoldings tile the plane with at most one extra unfolding rotated 180° from the original. I have not yet tried the 90° rotations as those are harder to implement. Instead I relaxed the "even number of axes reversed" to "any number of axes reversed", which then could show that all 261/261 unfoldings tile 3D space with at most one extra rotated/reflected piece.
I have now run the method on all 5-cube unfoldings. They all (9694/9694) tile 4D space, using only a single extra rotated version, no reflections were needed. For every of those foldings it was tileable with the all-axis-flip rotation.