This is not an answer, but a braindump of things that came up today (mainly focussing on the two-dimensional case, but most of it generalises to higher dimensions):
- In a random configuration approximately $\frac{6}{\pi^2} \approx 0.61\%$ of the adjacent cubes are coprime.
One can consider groups that naturally act on the set $C$ of configurations (such that they respect the property of a configuration being correct).
- Obviously the symmetry group of the square ($D_{4}$) acts on this set $C$.
- If $P$ denotes the set of primes $p$ such that $\frac{1}{2}n^{2} < p < n^{2}$, then $\mathrm{Sym}(P \cup \{1\})$ acts on $C$. (All numbers $1, \ldots, n^{2}$ are coprime to elements of $P \cup \{1\}$; hence we can permute this elements in a given solution.)
- Let $\mathrm{rad} \colon \{1, \ldots, N\} \to \mathbb{N}$ denote the radical function, taking $\prod_{i} p_{i}^{e_{i}}$ to $\prod_{i: e_{i}>0} p_{i}$. This function defines a partition on $\{1, \ldots, N\}$. Let $\mathrm{R}^N_{r} = \mathrm{rad}^{-1}(r)$ denote such a partition. Then $\mathrm{Sym}(\mathrm{R}^{n^2}_{r})$ acts on $C$. (This is because to numbers are coprime iff their radicals are coprime.)
I do not know a good way of estimating the size of $\mathrm{R}^{N}_{r}$, or more precisely:
Given $N$, what is (approximately) the size of the largest $\mathrm{R}^{N}_{r}$?
These groups show that there is essentially a unique solution for the $3 \times 3$ problem. One has:
- $P \cup \{1\} = \{1,5,7\}$
- $\mathrm{R}_{2} = \{2,4,8\}$
- $\mathrm{3}_{3} = \{3,9\}$.
By the parity condition mentioned in the comments, $6$ has to be at the middle of an edge, and by the $D_{4}$-action, it does not matter which edge we choose. Next, we place $2,4,8$ on the other middles of edges. Then, $3,9$ go in the corners not adjacent to $6$. Finally $P \cup \{1\}$ is placed in the remaining squares.
Ok, got to leave now. Hope this helps someone.