The Rook Conjecture: arrangement of $p$ primes being distinct $\pmod{p}$ through $p^2$ For any prime $p$, divide $[1,p^2]$ into $p$ equal intervals of length $p$, so that the first interval is $[1,p]$, the next $[p+1,2p]$, and so on. It is definitely unproven but seems likely that there will always be a prime in every one of these intervals. It is even probably true when you substitute any natural $n$ in place of the prime $p$ above.
I've noticed a stricter condition that seems to hold. If you divide $p^2$ as described above, not only will there be a prime in every interval of length $p$, but there will always be at least one way to select those primes such that no value is repeated $\bmod{p}$.
A good name for this might be the Rook Conjecture, as this is equivalent to saying that if you number the squares of a $p\times p$ sized chessboard, there is always at least one way to place $p$ rooks on prime-numbered squares yet have no rooks share a rank or file.
Examples
$p=3,\qquad S=\{3,5,7\}\equiv\{0,2,1\} \pmod{3}$
$p=5,\qquad S=\{5,7,11,19,23\}\equiv\{0,2,1,4,3\} \pmod{5}$
etc.
I've verified this for $p\leq 1000$. As usual, I am curious whether this is a known result and/or where to look for related work, and of course any counterexamples should they exist. I'm also curious whether this result seems to others to be surprising, or expected; I'm having a hard time deciding the answer for myself.
 A: The GRH neither implies that there is a prime in $[p^2-p,p^2]$ nor that the least prime $\equiv a\bmod p$ is $\le p^2$. Thus your conjecture is very strong and there is no fear to use the random model for the primes. 
You are saying that for some permutation $\sigma$ of $[1,p-1]$, all the $np+\sigma(n),n\in [1,p-1]$ are primes. 
The probability that they are all primes is  $$\approx\prod_{n=1}^{p-1}\frac1{\log( np+\sigma(n))} \approx \frac{C}{\log^{p-1} p}$$ the probability that no permutation works is $$\approx (1-\frac{C}{\log^{p-1} p})^{(p-1)!}\approx \exp(- \frac{C (p-1)!}{\log^{p-1-\epsilon} p}) $$
The probability that no permutation works for some $p\ge k$ is $$f(k)\le \sum_{p\ge k}\exp(- \frac{C (p-1)!}{\log^{p-1-\epsilon} p})$$
Since the series converges and $$\lim_{k\to \infty} f(k)=0$$
then the random model predicts that your conjecture holds for $p$ large enough.
(Why did I use the $\approx$ symbol ? Because the random model is case specific : we can and we should take in account the "congruences constraints" before assuming all the implied random variables are independent, which is what we need to simplify everything. Here I don't have any good argument for why this computation does take in account the relevant congruence constraints.)
