Latest (and likely final) edit: Fixing a typo, rewording the introduction

Multiples of $2$ are placed in a checkerboard fashion: This is the parity condition, and is essential if there are an even number of total lattice sites. This answer sketches a proof that it is possible to place multiples of $3$ in all rectangular arrays in arbitrary dimension, with the exception of $2^4$ and $2^6$, and argues that higher primes can also be incorporated. Thus I conjecture that these two examples are the only cases where a solution is impossible. For lower dimensions there are many explicit solutions.

**2D:** All $(k,l)$ with $kl\leq 50$. These are from a numerical search (using parity but no other symmetries), except for $(21,2)$ and $(24,2)$ for which Masked Avenger (MA) found a Hamiltonian path in the comments below (in "first three exceptions" of previous version).

All squares up to 25 numerically, except for 24. nsrt's answer gives an example for all odd primes.

**3D:** All $(k,l,m)$ with $klm\leq 50$ with $m=2$, numerically except for MA's final "exception" $(12,2,2)$. Explicit non-Hamiltonian solution for $(3,3,3)$:

$\left(\begin{array}{ccc}27&10&9\\20&3&8\\21&4&15\end{array}\right)
\left(\begin{array}{ccc}14&13&22\\11&2&1\\16&7&26\end{array}\right)
\left(\begin{array}{ccc}5&6&23\\12&25&24\\17&18&19\end{array}\right)$

A numerical solution for $(4,4,3)$. Peter Mueller's answer gives solutions for $(4,3,3)$, $(5,3,3)$ and $(4,4,4)$.

**4D:** $(2,2,2,2)$ is impossible as per Zack Wolske's comment. $(3,2,2,2)$ has a solution:
$\left(\begin{array}{ccc}1&6&13\\8&11&24\end{array}\right)
\left(\begin{array}{ccc}4&7&8\\21&10&23\end{array}\right)$

$\left(\begin{array}{ccc}2&5&12\\15&14&19\end{array}\right)
\left(\begin{array}{ccc}3&22&17\\16&9&20\end{array}\right)$

**5D:** $(2,2,2,2,2)$ has a solution:

$\left(\begin{array}{cc}23&14\\24&19\end{array}\right)
\left(\begin{array}{cc}28&3\\25&4\end{array}\right)\qquad
\left(\begin{array}{cc}22&15\\7&16\end{array}\right)
\left(\begin{array}{cc}27&32\\26&21\end{array}\right)$

$\left(\begin{array}{cc}12&5\\1&6\end{array}\right)
\left(\begin{array}{cc}17&2\\18&11\end{array}\right)\qquad
\left(\begin{array}{cc}29&8\\30&13\end{array}\right)
\left(\begin{array}{cc}20&9\\31&10\end{array}\right)$

**6D:** $(2,2,2,2,2,2)$ is impossible, also due to placing multiples of $3$. There are $11$ odd multiples and $10$ even multiples to place. So if the domain is split in half, at least one half must have $11$ or more multiples of $3$. Now for a 5D domain: either (a) there are none of a given parity, in which case there can be up to $16$ of the other, or (b) there is one of a given parity, which has $5$ neighbours, hence restricting the other parity to $11$, or (c) the total of both parities is restricted to $10$ or less (by detailed checking). Thus for each of the six ways in which the 6D domain can be split, there are are zero or one of one parity and $10$ or more of the other. Losing at most one site at each of the remaining five splittings, we find at least $5$ in the intersection of the halves, a single site, which is a contradiction.

**General idea:** For the remaining lattices, if one of the lengths is at least $3$ use checkerboard arrangements for all odd and even multiples of $3$ on opposite sides, as in the $(3,3,3)$ example above. For larger examples, these fill several layers on each side (total filling $2/3$ of the volume). If multiples of $15$ are placed as close together as possible, the remaining $13/15$ of the volume is available for other multiples of $5$, amongst the multiples of $3$ or in the empty space in the middle. Similarly with $7$ and higher primes, which become increasingly easy to add. So I conjecture that the only impossible cases are of the form $2^d$.

But which $d$? Rather than opposite faces we now concentrate on corners. If we place odd multiples of 3 at distances $\{o_i\}$ from a specified corner and even multiples of 3 at distances $\{e_i\}$ from that corner, such that all $\{o_i\}$ are odd and all $\{e_i\}$ are even, it is possible to ensure that none are adjacent if $d\not\in\{4,6,8,10,12\}$. For example, the solution for $d=14$ is $o_i=1,3,5,11,13$ with a total of (binomial coefficients) $14+364+2002+364+14=2758$ locations, and $e_i=8$ with $3003$ locations. In this case we need $2731$ (roughly $2^{14}/6$) odd and $2730$ even.

The remaining cases $8,10,12$ can be filled with multiples of 3 using the following construction: Choose a $2\times 2$ block, then odd multiples of 3 are at odd locations (required by parity) a distance $\delta=0,1,\ldots (d/2)-2$ from this block, and even multiples of 3 are at even locations at distances $\delta=(d/2),(d/2)+1,\ldots,d-2$. In each case the number of such locations is

$2\sum_{\delta=0}^{d/2-2} \left(\begin{array}{c}d-2\\\delta\end{array}\right)$

so for example for $d=8$ we have $2+12+30=44$ for $\delta=0,1,2$ which is slightly more than sufficient as we need to place $43$ odd multiples of $3$ and $42$ even multiples. Thus, assuming that multiples of higher primes can be incorporated as above, the only counterexamples are $2^4$ and $2^6$.

7more comments