whuts-solver

Code to find solutions for tiling the space by multidimensional polyominos.

Originally inspired by Matt Parker's video https://www.youtube.com/watch?v=Yq3P-LhlcQo to find a space filling tiling for each of the 261 unfoldings of a 4d hypercube.

Work was generalized motivated by these questions in stackexchange:

https://math.stackexchange.com/questions/4142544/smallest-non-space-filling-polycube

https://math.stackexchange.com/questions/4156024/smallest-non-4-space-filling-polytesseract

Original code is in src/whuts.py and can generate a tiling given a 3d polyomino as json.

Generalized code for higher dimensions was initially in src/polytiling_multidim.py but was too slow for processing higher order polyominos.

Code was rewritten in C and optimized in src/polytiling_multidim.c (input is simple list of numbers instead of json to avoid json parsing and depending on external libraries).

There are some additional helper scripts to generate polominos and verify a solution.

Algorithm Description

The code tries to find symmetric tilings, that can be generated by a basic pattern, repeated infinitely in DIM directions in space, where DIM is the dimension we want to fill.

If we start with DIM vectors in general position, it will be only possible to find a tiling if the vectors span a parallelepiped with volume a multiple of the size of the polyomino we are trying to find a tiling for (call this size N). This is a necessary (but of course not sufficient) condition. Basically that means the determinant of the matrix containing the DIM offset vectors has to be a multiple of N. We start be generating some matrices with determinant N, then continue with some with determinant 2N, and so on until we find a solution.

Every time we have defined an offset matrix, we do a backtracking algorithm by placing some rotation/translation of the unfolding and checking if it fits, backtracking if not. There is some preprocessing for precomputing which cells are covered by each rotation/translation to optimize the backtracking search.

In the later optimization the backtracking was replaced by the more efficient Knuth's Algorithm X: https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

Update

After some discussion with Glen Whitney based on his question on stackexchange: https://math.stackexchange.com/questions/4142544/smallest-non-space-filling-polycube I have now generalized the code to generate tilings for poly-hypercubes in higher dimensions. I did some optimizations in the code and rewrote in C (called it poly_tiling_multidim and have both a C and a Python version in src), in C I am using now Knuth's Algorithm X which is more efficient, but also a lot of low level optimizations make the C code much more efficient than the Python code (in which I avoided making these optimizations and tried to keep the code clean).

After running this on polytesseracts, it could find tilings for all up to and including all nonotesseracts (to be exact I run it only up to 4 polytesseracts in the main pattern, and so far it could not find anything for 2 nonotesseracts, but after checking these manually, these are flat and they have already a solution in 3d requiring 6 polycubes, so this can be obviously extended to 4d).

For running the C code, you need an input file that has first the dimension N, second the size of the polycube (e.g. "4 8" for octotesseracts), followed by a list of coordinates, all separated by whitespace.

Algorithm Description

The code tries to find symmetric tilings, that can be generated by a basic pattern, repeated infinitely in 3 directions in space.

If we start with 3 vectors in general position, it will be only possible to find a tiling if the vectors span a parallelepiped with volume a multiple of 8 (since the unfoldings we start with have a volume 8). This is a necessary (but of course not sufficient) condition. Basically that means the determinant of the matrix containing the 3 offset vectors has to be a multiple of 8. We start be generating some matrices with determinant 8, then continue with some with determinant 16, and so on until we find a solution.

Every time we have defined an offset matrix, we do a backtracking algorithm by placing some rotation/translation of the unfolding and checking if it fits, backtracking if not. There is some preprocessing for precomputing which cells are covered by each rotation/translation to optimize the backtracking search.

For generating all possible matrices with a given determinant, we first generate all diagonal matrices with the given volume, and then iterate over all possible values for generationg a tringular matrix. It turns out, there is a limited value for each position of the matrix, before we start generating matrices that define the same grid in DIM-space (see https://oeis.org/A001001 for a description in 3d, which can be easily generalized for higher dimensions).

There is the problem of how to find all matrices with a given determinant that generate distinct grids of points (e.g. in 2d the matrices ((1,1), (1,-1)) and ((1,1),(3,7)) will generate the same grid of points if repeated infinitely in all directions. I couldn't find a simple answer to this (I am sure there is one out there), so initially (not in this code) I tried some random matrices and keeping the ones with determinant n*8 and checking if some generate the same grid to keep one of them. For this code I thought (not sure how I came up with that thought) that I could generate all possible distinct ways by using vectors (v, 0, 0), (a, 1, 0), (b, 0, 1) for a and b between 0 and v-1. I now realized that this is wrong (my older code found a solution for octocube 1325 with basic pattern volume 32, in contrast the smallest one that this code could find had volume 48).

Usage Example

echo '[[0,0,0],[0,0,-1],[0,-1,-1],[0,-1,-2],[-1,-1,-2],[1,0,0],[1,0,1],[1,1,1]]' | python3 whuts.py

echo '[[0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,1,0],[0,0,1,1],[0,1,0,2],[0,1,0,3],[1,1,0,3]]' | python3 src/poly_tiling_multidim.py

gcc -O4 -o poly_tiling_multidim src/poly_tiling_multidim.c

echo 4 8 0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 1 1 0 1 0 2 0 1 0 3 1 1 0 3 | poly_tiling_multidim

In the last example, the first number in the input is the dimension DIM, the second the size of the polyomino N, then follow DIM * N numbers defining the polyomino.

Results

I run the code for all possible octocubes (octominoes in 3d?). The octocubes are generated by the file generate_octocubes.py. The program could find solutions for all but 3 octocubes (the first version of the program that was not trying all possible offsets for a given volume). The fixed version could find solutions for all octocubes except this one:

    ###
    #.#
    ###

Due to the very restrictive nature of this one (two of these have to be pairwise connected, so it reduces to finding a tiling of space using the 16-cube containing two of these instances connected together), I tried writing more optimized C code, but still didn't get any results. I will update here if something is found.

Out of the 3811 octocubes:

After running the fixed code also with all hypercube unfoldings again, these are the stats:

Out of the 261 hypercube unfoldings:

So basically, 145 of them can tile the space just by repeating at some directions without any rotations (and for the rest we just need to build a pattern made out of just two rotated instances and continue in three directions)!

Apart from the ring-octocube that seems to have no 3d-space filling tiling, there are 5 nonocubes for which the code also didn't give any result after running a couple days.

For 4d, the code was able to generate 4d-filling tilings for all polytesseracts up to and including decatesseracts (DIM=4, N=10), which makes the smallest non filling polytesseract being either an undecatesseract (N=11) or dodecatesseract(N=12) (since there is definitely at least one dodecatesseract that can not tile 4d-space, see my answer in https://math.stackexchange.com/questions/4156024/smallest-non-4-space-filling-polytesseract for an image).