# Puzzle in 3D grid with black and white boxes, related to shelling

Consider a $n$ by $n$ by $n$ grid represented by the set of $3$-uples $S=\{1,2,\dots, n\}^3$.
A line (resp. slice) of $S$ is a subset of cardinal $n$ (resp. $n^2$) where two components (resp. one component) of the $3$-uples are fixed.

Some boxes of the grid are black (and the remaining ones are white), they are represented by a subset $B \subseteq S$. For a fixed $r \le n$, consider the following assumptions on $B$:

• every line contains exactly $r$ black boxes.
• in every slice, the black boxes can be filled collinearly, i.e. there is an ordering $b_1, b_2, \dots, b_{rn}$ such that for all $i>1$ there is $j<i$ such that $b_i$ and $b_j$ are in a same line.

The examples below, given by the pictures of parallel slices, satisfies the two above assumptions.

For $r=2$ and $n = 3$:

$\substack{ \displaystyle{◻ ◼ ◼} \cr \displaystyle{◼ ◻ ◼} \cr \displaystyle{◼ ◼ ◻} }$ $\substack{ \displaystyle{◼ ◼ ◻} \cr \displaystyle{◻ ◼ ◼} \cr \displaystyle{◼ ◻ ◼} }$ $\substack{ \displaystyle{◼ ◻ ◼} \cr \displaystyle{◼ ◼ ◻} \cr \displaystyle{◻ ◼ ◼} }$

For $r=3$ and $n = 4$:

$\substack{ \displaystyle{◻ ◼ ◼ ◼} \cr \displaystyle{◼ ◻ ◼ ◼} \cr \displaystyle{◼ ◼ ◻ ◼} \cr \displaystyle{◼ ◼ ◼ ◻} }$ $\substack{ \displaystyle{◼ ◼ ◼ ◻} \cr \displaystyle{◻ ◼ ◼ ◼} \cr \displaystyle{◼ ◻ ◼ ◼} \cr \displaystyle{◼ ◼ ◻ ◼} }$ $\substack{ \displaystyle{◼ ◼ ◻ ◼} \cr \displaystyle{◼ ◼ ◼ ◻} \cr \displaystyle{◻ ◼ ◼ ◼} \cr \displaystyle{◼ ◻ ◼ ◼} }$ $\substack{ \displaystyle{◼ ◻ ◼ ◼} \cr \displaystyle{◼ ◼ ◻ ◼} \cr \displaystyle{◼ ◼ ◼ ◻} \cr \displaystyle{◻ ◼ ◼ ◼} }$

An ordering $b_1, b_2, \dots, b_{rn^2}$ of $B$ is Eulerian if for all $i>1$ and for all $j<i$, there is $k<i$ such that $b_i$ and $b_k$ are in a same line $l$, and if $b_i$ and $b_j$ are in a same slice $s$, then $l \subset s$.
The notion of Eulerian ordering is related to the notion of shelling, as explained in this post.

If $r=n$ then the grid contains black boxes only and the lexicographic ordering is Eulerian.
If $r=n-1$ then both cases are possible:
The above example with $(r,n) = (2,3)$ has no Eulerian ordering, as shown by brute-force search below, and any partial Eulerian ordering has length at most $8$:

The above example with $(r,n) = (3,4)$ has an Eulerian ordering: Question: Do the two above assumptions imply the existence of an Eulerian ordering if $r \ge 3$?

Remark: I don't know whether the following examples, with $(r,n) = (3,7)$, have an Eulerian ordering (the second is a 90° rotation of the first). Brute-force search with SAGE

Computation:

sage: %attach SAGE/EulerianGrid.spyx
Compiling ./SAGE/EulerianGrid.spyx...
sage: S=[[1,1,1],[1,1,2],[1,2,1],[1,2,3],[1,3,2],[1,3,3],[2,1,1],[2,1,3],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,3,1],[3,3,3]]
sage: %time PartialOrdering(S,[],8)
CPU times: user 10.4 s, sys: 15 ms, total: 10.4 s
Wall time: 10.5 s


Code:

# %attach SAGE/EulerianGrid.spyx

from sage.all import *

cpdef JoinDegree(list L1, list L2):
cdef int i,c
c=0
for i in range(3):
if L1[i]==L2[i]:
c+=1
return c

cpdef IsCollinearList(list l, list L):
cdef list i
if L==[]:
return True
for i in L:
if JoinDegree(l,i)==2:
return True
return False

cpdef PartialOrdering(list L, list P, int A):
cdef int c,cc
cdef list i,j,k,t,LL,PP
if len(P)>A:
print(P)
if L<>[]:
for i in L:
if IsCollinearList(i,P):
cc=0
for j in P:
if JoinDegree(i,j)==1:
c=0
for k in P:
if JoinDegree(i,k)==2 and JoinDegree(j,k)>=1:
c=1
break
if c==0:
cc=1
if cc==0:
LL=[t for t in L]
PP=[t for t in P]
LL.remove(i)
PP.append(i)
if LL<>[]:
PartialOrdering(LL,PP,A)
else:
return PP

• This is different from collinear ordering, right? Because I see a (level by level) collinear ordering of your 4 by 4 by 4 example. Gerhard "Which Makes A Nice Puzzle" Paseman, 2018.05.30. – Gerhard Paseman May 30 '18 at 19:41
• @GerhardPaseman: Yes, for an ordering "Eulerian" is stronger than "collinear". The collinear condition is of the form "$\forall i>1, \exists j<i$...", whereas the Eulerian condition is of the form "$\forall i>1, \forall j<i, \exists k<i$...". For a 2D grid, these two conditions are the same, but it is no more true for a 3D grid (and beyond). – Sebastien Palcoux May 30 '18 at 21:10
• The example without Eulerian ordering (considered in the two above comments) was replaced by a 3 by 3 by 3 example. We also added a new 4 by 4 by 4 example having an Eulerian ordering. – Sebastien Palcoux Jul 29 '18 at 10:43