Exact coverability of $\mathbb{Z}_n$ by cyclic shifts of a given set -- easy? NP-complete?

Recently Ernest Davis asked me about the following computational problem: we're given as input a composite integer $$n$$, a divisor $$k$$ of $$n$$, and a subset $$S \subset \mathbb{Z}_n$$ of size k. The problem is to decide whether $$\mathbb{Z}_n$$ can be covered with $$n/k$$ cyclic translations of $$S$$, i.e. sets of the form $$S+a_i$$ for various $$a_i \in \mathbb{Z}_n$$. This is simply a special case of the NP-complete EXACT COVER problem---namely, where the available sets are all cyclic shifts of each other, and where all cyclic shifts are available. My suspicion is that the special case is already NP-complete, while Ernest suspects that an $$n^{O(1)}$$ time algorithm exists. I searched Google (and Garey&Johnson) and couldn't find leads -- would appreciate any thoughts or references!

Here are a few references; the right keywords seem to be "tiling by translation" or a "factorization of a group":

Mihail N. Kolountzakis and Máté Matolcsi, Algorithms for translational tiling, Journal of Mathematics and Music, 3:2 (2009), 85-97, https://doi.org/10.1080/17459730903040899

Mihail N. Kolountzakis and Mate Matolcsi, Tilings by translation (2010), https://arxiv.org/abs/1009.3799

A couple of more simple observations about this plus a conjecture. First, it's symmetric in $$S$$ and the set of shifts; you can rephrase it, "Given $$n$$ and $$S$$, find $$A \subset \mathbb{Z}_{n}$$ such that $$|A|=n/|S|$$ and $$\{ s+a \: | \: s \in S, a \in A \} = \mathbb{Z}_{n}$$." Second, for concreteness, to illustrate the kinds of things that can happen, with $$S=\{ 0, 6,7,8, 13, 14\}$$, $$n=24$$, a solution is $$A = \{0,3,12,15\}$$. Third, there are some invariants: if $$\langle S,A \rangle$$ is a solution, then so is $$\langle d \cdot S+b, d\cdot A+c \rangle$$ for constants $$b,c,d$$.

There is also a more complex invariant: Suppose that all the elements of $$A$$ are divisible by $$b$$. It is easily shown that $$|S|$$ is divisible by $$b$$. Let $$j$$ be a value in $$0..b-1$$ and let $$Q_{j}=\{ s \in S \: | \: s \mod b = j \}$$. Then you can replace $$Q_{j}$$ by $$Q_{j}+cb$$ in $$S$$. In the above example $$b=3$$. For $$j=1$$ we have $$Q_{1}=\{7,13\}$$. So we can replace $$Q$$ by $$Q+3$$ in $$S$$, giving us the pair $$S=\{ 0,6,8,10,14,16\}, A=\{ 0,3,12,15 \}$$.

I conjecture that the following may be true: Let $$S_{i} = \{ s \in S \: | \: s \mod |S| = i \}$$. If there is a solution, then all the non-empty $$S_{i}$$ have the same size. E.g. in the above example, $$|S|=6$$; $$S_{0}=\{ 0,6\}; S_{1}=\{7,13\}; S_{2}=\{8,14\}$$. If this is true, then I think I have a polynomial-time algorithm.

E.D., I think the conjecture is not true. If one tries it on the smallest non-periodic tiling (see below) it fails. The example is from N.G. de Bruijn, On the factorization of cyclic groups, Indag. Math. 15, 4, 1953.

The following Python program

# A + B is a tiling of Z mod 72
A = [0, 8, 16, 18, 26, 34]
B = [18, 54, 24, 60, 48, 12, 17, 41, 65, 45, 69, 21]
m = len(A)*len(B)

# Cheking tiling
S = m*[0]
for x in A:
for y in B:
S[(x+y) % m] += 1
if S == m*[1]: print("Yes, they tile")

L = [x % len(B) for x in B] # The elements of B mod len(B)

H = len(L)*[0] # Compute the histogram of L
for x in L: H[x] += 1

print(f"Frequencies of B mod {len(B)}: {H}")


prints

Yes, they tile
Frequencies of B mod 12: [4, 0, 0, 0, 0, 3, 2, 0, 0, 3, 0, 0]


I also believe the problem is polynomial. I do not even know if it is in co-NP (are there certificates for non-tiling?).