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? 

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}
