Minimal Rook Difference Grids

Question

In the below grid all 18 orthogonal differences are distinct, with a difference of 18 missing.

Could the highest number be 18? The resulting graph would have valence 4, making it an Eulerian Graceful graph with edges(mod 4)=2. Rosa (1967) proved Eulerian Graceful graphs must have edges(mod 4)=0 or 3, so 18 is impossible.

Thus the minimal $3\times3$ rook difference grid has $rdg(3,3)=19$.

For $rdg(1,n)$ see Golomb Ruler.

$rdg(2,3)=9$ and $rdg(2,4)=16$, as shown below.

What are values for larger grids?

Answer 1

I used a depth first search written in C to find the following:

$rdg(3,4)=30$, so the $3\times4$ rook graph is graceful.

\begin{array}{|c|c|c|c|} \hline 0 & 1 & 9 & 30 \\ \hline 16 & 29 & 2 & 19 \\ \hline 22 & 3 & 27 & 7 \\ \hline \end{array}

$rdg(4,4)=48$, so the $4\times4$ rook graph is also graceful.

\begin{array}{|c|c|c|c|} \hline 0 & 1 & 23 & 47 \\ \hline 19 & 44 & 9 & 2 \\ \hline 37 & 42 & 3 & 11 \\ \hline 48 & 4 & 36 & 32 \\ \hline \end{array}

$rdg(3,5)=46$. This is not graceful. Like the $3\times3$, Rosa (1967) shows this is the minimum possible. \begin{array}{|c|c|c|c|c|} \hline 0 & 1 & 10 & 26 & 46 \\ \hline 23 & 45 & 37 & 5 & 8 \\ \hline 42 & 14 & 44 & 38 & 3\\ \hline \end{array}

Misha Lavrov's answer, gives a graceful labeling of the $2\times5$ rook graph, but larger $2\times n$ rook graphs cease being graceful:

$rdg(2,6)=38$. The $2\times6$ rook graph has $36$ edges. \begin{array}{|c|c|c|c|c|c|} \hline 0 & 1 & 10 & 16 & 34 & 38 \\ \hline 35 & 32 & 24 & 37 & 5 & 12\\ \hline \end{array}

$rdg(2,7)=53$. The $2\times7$ rook graph has $49$ edges. \begin{array}{|c|c|c|c|c|c|c|} \hline 0 & 6 & 16 & 24 & 38 & 41 & 53 \\ \hline 31 & 52 & 3 & 51 & 12 & 8 & 1 \\ \hline \end{array}

Answer 2

Here is a graceful labeling of the $2\times 5$ grid, so $rdg(2,5)=25$:

\begin{array}{|c|c|c|c|c|} \hline 0 & 6 & 7 & 21 & 25 \\ \hline 24 & 22 & 19 & 11 & 2 \\ \hline \end{array}

I put together a simulated annealing setup for graceful-labeling type problems after your previous question, and I'll try it at some larger grids next to see if I get anywhere.

For the $3\times 4$ grid, the following labeling proves $rdg(3,4) \in \{30,31\}$ but doesn't quite settle the question:

\begin{array}{|c|c|c|c|} \hline 0 & 3 & 14 & 22 \\ \hline 27 & 9 & 4 & 29 \\ \hline 31 & 18 & 30 & 1 \\ \hline \end{array}

Answer 3

I found a new optimal solution for the $3 \times 5$ rook graph: \begin{array}{|c|c|c|c|c|} \hline 5 & 46 & 45 & 28 & 0 \\ \hline 31 & 7 & 1 & 44 & 11 \\ \hline 40 & 21 & 13 & 6 & 42 \\ \hline \end{array}

Also I investigated the queen graph.

$qdg(2,2)=6$, so the $2 \times 2$ queen graph is graceful: \begin{array}{|c|c|} \hline 6 & 5 \\ \hline 2 & 0 \\ \hline \end{array}

$qdg(2,3)=13$, so the $2 \times 3$ queen graph is graceful: \begin{array}{|c|c|c|} \hline 0 & 13 & 6 \\ \hline 10 & 2 & 1 \\ \hline \end{array}

$qdg(2,4)=22$, so the $2 \times 4$ queen graph is graceful: \begin{array}{|c|c|c|c|} \hline 1 & 13 & 22 & 0 \\ \hline 21 & 3 & 6 & 17 \\ \hline \end{array}

$qdg(2,5) \leq 34$. The $2 \times 5$ queen graph has 33 edges: \begin{array}{|c|c|c|c|c|} \hline 9 & 0 & 20 & 30 & 3 \\ \hline 34 & 32 & 1 & 16 & 8 \\ \hline \end{array}

$qdg(3,3) \leq 29$. The $3 \times 3$ queen graph has 28 edges: \begin{array}{|c|c|c|} \hline 2 & 19 & 5 \\ \hline 28 & 29 & 13 \\ \hline 7 & 0 & 25 \\ \hline \end{array}

And for a bit of fun I found that $qdg(4,4) \leq 97$. The $4 \times 4$ queen graph has 76 edges: \begin{array}{|c|c|c|c|} \hline 2 & 91 & 23 & 47 \\ \hline 58 & 97 & 1 & 88 \\ \hline 5 & 0 & 72 & 84 \\ \hline 78 & 59 & 86 & 36 \\ \hline \end{array}