<s>[INST] Minimal Rook Difference Grids 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? 
 [/INST] 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}
</s>