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? 
 A: 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}
A: 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}
A: 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}
