lets take a smaller case. 1x1 would only have 1 case.

now for 2x2. 1 and 4 must go in the corners, and 2 and 3 can be alternated 2 ways.

now for 3x3. 1 and 9 go in the corners, and then 8 and 7 border the 9, and 2 and 3 border the 1. now you can arrange the 4, 5, and 6 any way you wish, which makes 3! * 2 * 2 ways, or 24.

for 4x4, apply the same logic, and then you will have a diagonal, and two small diagonals. 4, 5, and 6 go in the top diagonal, 13, 12, 11 go in the bottom one, and the rest go in the middle, for 4!*3!*3!*2!*2!, or 3456.

you can now see that it is 1! for 1x1, then 2! for 2x2, then 3!*2!*2! for 3x3, and then 4!*3!*3!*2!*2!. so, if you had a nxn square, then n+1xn+1 square would be (n+1)!*(n!)*(n!)*(n-1)!*....3!*2!*2!*1!*1!, so for nxn square, it would be n!*((n-1)!)^2*((n-2)!)^2*...(3!)^2*(2!)^2*(1!)^2.

i may be wrong, i probably am, but somebody PLEASE check my work.

as for n by n by n, i am comepletely confuzzled O.O

HOPE THIS HELPED!