Rotation-safe Latin squares
Pyth - 29 bytes
Brute force.
hf&amp;!@JsCBTsm.&gt;RdJStQ.A{IMJ^.p

Does not finish online even for n=4, but you can try it out locally, or run this modified version online for one more byte.