How to mathematically determine row, column, and sub-square of cell in nxn array where n is a perfect square?

Question

Given an one dimensional array of size nxn, where n is a perfect square

How can one mathematically determine the row, column, and/or sub-square the cell resides in? Additionally, is there a mathematical way to traverse the subsquare?

Answer 1

Let the one-dimensional cells be $c_1, c_2, \cdots, c_{n^2}$.

Assume the top-left cell is at $(1,1)$, i.e., the first row and the first column. Assume the top right cell is at $(1,n)$, i.e., the first row and the $n$-th column. Then the $i$-th cell, $c_i$ is at $(i/n + 1, i \%n +1)$. Here $i/n$ is the integer division and $i\%n$ is the modulo operation in any popular programming language. For example, let $n=9$. Then the $42$-th cell, $c_{42}$ is at $(42/9+1, 42\%9+1)=(5, 7)$.

Suppose the subsquares are lined up in the same order as the cells, so that we have subsquares $S1, S2, \cdots, Sn$. Consider each subsquare as a kind of "large cell". So that we would have the following coordinates for subsquares.

Note that $c_i$ belongs to the $(i/n+1)$-th subsquare, i.e. subsquare $S(i/n+1)$. For example, $c_{37}$ belongs to the $5$-th subsquare, i.e, subsquare $S5$. We are in the same situation as before, but with the $(i/n+1)$-th "large cell" and a $\sqrt n\times\sqrt n$ of "large cells". So similarly we see that the $(i/n+1)$-th subsquare is at $((i/n+1)/\sqrt n + 1,(i/n+1)\%\sqrt n + 1)$, using the coordinates for subsquares.

Suppose we want to traverse the subsquare at $(j,k)$ (where $(j,k)$ is in the coordinates for subsquares).

• The first cell (the top-left cell) of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n +1}$
• The first cell of the second row of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n +1 + n}$
• $\cdots$
• The first cell of the last row of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n + 1 + (\sqrt n -1 )n}$

So we can traverse all cells in that subsquare by the following pseudocode.

$\quad$ for $row$ in $1, 2, \cdots, \sqrt n$
$\quad\quad$ for $column$ in $1, 2, \cdots, \sqrt n$
$\quad\quad\quad$ visit the cell at $row$-th row and $column$-th column of the subsquare at $(j,k)$, which is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n + (row -1 )n + column}$

Note "$row$-th row and $column$-th column" are referring to cells in that subsquare.

For example, we will traverse the cells at subsquare (2,3) in the following order.

• cells in its first row, $c_{34}$, $c_{35}$, $c_{36}$,
• cells in its second row, $c_{43}$, $c_{44}$, $c_{45}$,
• cells in its third row, $c_{52}$, $c_{53}$, $c_{54}$.