Question: Do the two above assumptions imply the existence of an Eulerian ordering if $r \ge 3$?
QuestionRemark: Do the two above assumptions implyI don't know whether the existence offollowing examples, with $(r,n) = (3,7)$, have an Eulerian ordering if $r \ge 3$?(the second is a 90° rotation of the first).
Question: Do the two above assumptions imply the existence of an Eulerian ordering if $r \ge 3$?
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).
Example: For $r=2$ and $n = 4$ The examples below, the following combination (givengiven by the pictures of $4$ parallel slices), satisfies the two above assumptions.
$\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{◼ ◻ ◼ ◻} } $ 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$.
Note that theThe notion of Eulerian ordering is related to the notion of shelling, as explained in this post.
Remark: If $r=n$ then the grid contains black boxes only and the lexicographic ordering is Eulerian.
Question: Has $B$ (satisfying the two above assumptions) an Eulerian ordering if
If $r \ge 3$?
Remark$r=n-1$ then both cases are possible: The
The above combination (with $r=2$ andexample with $n = 4$) admits$(r,n) = (2,3)$ has no Eulerian ordering (proved below, as shown by brute brute-force search; a conceptual proof would be useful). Note thatsearch below, and any partial Eulerian ordering of it has length at most $11$, see an$8$:
The above example belowwith $(r,n) = (3,4)$ has an Eulerian ordering:
Note thatQuestion: Do the black box marked "?" cannot be added because it shares a slice withtwo above assumptions imply the black box n°7 whereas there is no marked black box in this slice which shares a line with "?"existence of an Eulerian ordering if (idem for every unmarked black box).$r \ge 3$?
sage: %attach SAGE/EulerianGrid.spyx
Compiling ./SAGE/EulerianGrid.spyx...
sage: B=[[1S=[[1,1,2]1],[1,1,4]2],[1,2,1],[1,2,3],[1,3,1],[1,3,2],[1,43,3],[1,4,4],[2,1,1],[2,1,4]3],[2,2,2],[2,2,4]3],[2,3,1],[2,3,3],[2,4,2],[2,4,3],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,3,3],[3,3,4],[3,4,1],[3,4,4],[4,1,1],[4,1,3],[4,2,3],[4,2,4],[4,3,2],[4,3,4],[4,4,1],[4,4,2]]3]]
sage: %time PartialOrdering(BS,[],118)
CPU times: user 55min10.4 s, sys: 3.4915 sms, total: 55min10.4 4ss
Wall time: 56min10.5 52ss
Example: For $r=2$ and $n = 4$, the following combination (given by the pictures of $4$ parallel slices) satisfies the two above assumptions.
$\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$.
Note that the notion of Eulerian ordering is related to the notion of shelling, as explained in this post.
Remark: If $r=n$ then the grid contains black boxes only and the lexicographic ordering is Eulerian.
Question: Has $B$ (satisfying the two above assumptions) an Eulerian ordering if $r \ge 3$?
Remark: The above combination (with $r=2$ and $n = 4$) admits no Eulerian ordering (proved below by brute-force search; a conceptual proof would be useful). Note that any partial Eulerian ordering of it has length at most $11$, see an example below:
Note that the black box marked "?" cannot be added because it shares a slice with the black box n°7 whereas there is no marked black box in this slice which shares a line with "?" (idem for every unmarked black box).
sage: %attach SAGE/EulerianGrid.spyx
Compiling ./SAGE/EulerianGrid.spyx...
sage: B=[[1,1,2],[1,1,4],[1,2,1],[1,2,3],[1,3,1],[1,3,2],[1,4,3],[1,4,4],[2,1,1],[2,1,4],[2,2,2],[2,2,4],[2,3,1],[2,3,3],[2,4,2],[2,4,3],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,3,3],[3,3,4],[3,4,1],[3,4,4],[4,1,1],[4,1,3],[4,2,3],[4,2,4],[4,3,2],[4,3,4],[4,4,1],[4,4,2]]
sage: %time PartialOrdering(B,[],11)
CPU times: user 55min, sys: 3.49 s, total: 55min 4s
Wall time: 56min 52s
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$?
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