Number of $n^2\times n^2$ permutation matrices with a 1 in each $n\times n$ subgrid

Well, in a $2^2 \times 2^2$ grid there are are 4 choices for the top left sub grid, then as the representative for the top right subgrid can't be in the same row, there are 2 choices. As the bottom left rep can't be in the same column as the top rep the there are 2 choices. There is only one choice left for the bottom right sub grid.

In total there are 4*2*2*1 = 16 options. Or $[2*2][(2 - 1)2]\times[2*(2-1)][(2-1)(2-1)]$ or in general $\prod_{i=1}^n\prod_{k=1}^n ik$.

This is the same argrument in the top row of sub grids there $n^2$ choices for the first subgrid. $(n-1)n$ for the second and so on. This is $\prod_{k=1}^n n*k$. For the second to top row (n-1 from the bottom) of of subgrids there are $n(n-1)$ choices for the first subgrid, $(n-1)(n -1)$ for the second and so on. This is $\prod_{k=1}^n (n-1)k$. For all the lth row of sub grids there are $n(n-l)$ choices for the first subgrid, $(n -1)(n -l)$ for the second and so on. This is $\prod_{k=1}^n (n -l)k$. The total product for all rows of subgrids is $\prod_{i=1}^n\prod_{k=1}^n ik$.

====

Hmmm, when I first posted I really should have continued:

$\prod_{i=1}^n(\prod_{k=1}^n ik)=$

$\prod_{i=1}^n(i^n n!)=$

$(n!)^n (n!^n) = n!^{2n}$

So for a $2^2 \times 2^2$ grid it is $(2!)^{2*2} = 2^4 =16$.

For the $3^2 \times 3^2$ grid it is $3!^{2*3} = 6^6 = 46,656$.

(Which I figure should be $(9*6*3)*(6*4*2)*(3*2*1) = (3^4*2)(3*2^4)(3*2) = 3^6*2^6 = 6^6$. Yep, seems to fit.)

I imagine 16 x 16 will be a monster! $(4!)^{2*4} = 24^8 = 110,075,314,176.$ Wow!

By hand it is $(16*12*8*4)(12*9*6*3)(8*6*4*2)(4*3*2*1)=(4^4*4!)(3^4*4!)(2^4*4!)(4!) = (4!)^4(4!)^4 = 4!^{2*4}$ which.. yeah...

Using the counting system outlined in the comments, we can associate to each subgrid a positive integer: the number of choices in that subgrid. It's fairly clear that the number is invariant of the exact method of getting to that subgrid: however you do it, subgrid $(i,j)$ (in the usual matrix suffix notation) has associated with it $(n+1-i)(n+1-j)$ choices. Now the matrices go as follows: \begin{eqnarray*} n=1 &\mapsto& \begin{pmatrix}1\end{pmatrix}\\ n=2 &\mapsto& \begin{pmatrix}4&2\\2&1\end{pmatrix}\\ n=3 &\mapsto& \begin{pmatrix}9&6&3\\6&4&2\\3&2&1\end{pmatrix}\\ &\vdots&\\ n=k&\mapsto& \begin{pmatrix} k^{2} & k(k-1) & k(k-2) & \ldots & 2k & k\\ k(k-1) & (k-1)^{2} & (k-1)(k-2) & \ldots & 2(k-1) & k-1\\ k(k-2) & (k-1)(k-2) & (k-2)^{2} & \ldots & 2(k-2) & k-2\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 2k & 2(k-1) & 2(k-2) & \ldots & 4 & 2\\ k & k-1 & k-2 & \ldots & 2 & 1 \end{pmatrix}\\ &\vdots& \end{eqnarray*} For each $n$, the answer to the problem is the product of all the entries in the corresponding matrix; denote each of these numbers by $P_{n}$. Now since each matrix contains the preceding matrix as a "submatrix", it is clear that we can find a recursive formula: in particular, some thought gives \begin{eqnarray*} P_{n} & = & P_{n-1}n^{2}\prod_{i=1}^{n-1}(in)^{2}\\ & = & P_{n-1}n^{2n}[(n-1)!]^{2}, \end{eqnarray*} with the initial condition $P_{1}=1$.

Now for each $n\in\mathbb{N}$ let $f(n) = (n!)^{2n}$. Clearly $P_{1}=f(1)$. Further, suppose that, for some $n\in\mathbb{N}$, we know that $P_{n-1} = f(n-1)$; then we have \begin{eqnarray*} P_{n} & = & P_{n-1}n^{2n}[(n-1)!]^{2}\\ & = & [(n-1)!]^{2(n-1)}n^{2n}[(n-1)!]^{2}\\ & = & (n!)^{2n}\\ & = & f(n). \end{eqnarray*}

By induction, $P_{n} = (n!)^{2n}$ for all $n\in\mathbb{N}$.

I believe I've come upon a solution. Just as @WillR suggested, who showed me the right approach to it, I'm posting this as an answer. Please feel free to notify me about flaws of logic if there are any. So, here it goes:

Let's start by choosing a cell from the top-left subgrid. As we have to select cells from each subgrids, I don't think this approach would affect the final outcome. We have $n^2$ choices in choosing the first cell then. Now, we move towards the right subgrid. This time, we'll have to keep in mind that one of the rows is used. So, we have $n(n-1)$ choices left. If we continue this way, the total number of ways in which we can select $n$ cells from the topmost row is $$n^2 \cdot n(n-1) \cdot \cdot \cdot n=n^n \cdot n!$$ Now, we move to the second row from the top. Now, we don't have to worry about the used rows anymore, only the used columns. So, when choosing the first one from here, we have $n(n-1)$ choices. When we move to the second subgrid, we'll have to avoid a row, but that reduces the number of choices by $(n-1)$, not $n$. Because, the row and column we have to avoid has a common cell. Continuing this way, in case of the second row, we have a total of $(n-1)^n \cdot n!$ choices.

Continuing this way, number of choices for the $r$'th row would be $(n-r+1)^n \cdot n!$. As the choices are independent, we can multiply them to get the total number of choices. That'd be: $$\prod_{r=1}^n{n!^n \cdot (n-r+1)^n} = n!^n \cdot \prod_{r=1}^nr^n=n!^n \cdot n!^n ={n!}^{2n}$$