3
$\begingroup$

I'm programming a game with C# to solve Sudokus.

I have the following Sudoku:

enter image description here

It is a 4x4 squared divided into 2x2 squares.

If a cell is in row 2, column 2, that cell is in the first inner square, so the top left corner for the first inner square is row 1, column 1.

Do you if there is a formula to calculate the top left corner (row and column) of its inner square for any cell in the Sudoku grid?

$\endgroup$
0
+50
$\begingroup$

I'll generalize this a bit so it will work for larger squares as well. Let the Sudoku consist of an $M\times M$ array of squares in which each square contains $M\times M$ cells. The complete Sudoku grid therefore has $N=M^2$ rows and $N=M^2$ columns. For the puzzle in the question, $M=2$ and $N=4.$

Let's start with way of describing the location of a cell in terms of the answer we want. Numbering the squares in the array of squares from $(1,1)$ in the upper left corner to $(M,M)$ in the lower right corner, and the cells within each square also from $(1,1)$ in the upper left to $(M,M)$ in the lower right, suppose we give each cell four coordinates $i_C,$ $ j_C,$ $i_S,$ and $j_S,$ meaning that the cell is in row $i_C$ and column $j_C$ within its square, and the square is in "row" $i_S$ and "column" $j_S$ within the array of squares. For example, if $N=9$ (the usual Sudoku size) and if $i_C=1,$ $j_C=3,$ $i_S=2,$ and $j_S=2,$ then $M=3$ and the cell is in the upper right corner (row $1,$ column $3$) of the square in the center of the puzzle (row $2,$ column $2$ within the $3\times 3$ array of squares).

Now let's translate those coordinates to the row number $i$ and column number $j$ of each cell within the full $N\times N$ grid of cells. The row and column numbers of the cells in the upper left square are simply $i = i_C$ and $j = j_C,$ but each time we add $1$ to $i_S$ (moving to the next "row" of squares) we add $M$ to $i$ but each time we add $1$ to $j_S$ (moving to the next "column" of squares) we add $M$ to $j.$ So in the end, we find that \begin{align} i &= i_C + M(i_S - 1), \\ j &= j_C + M(j_S - 1). \end{align}

Now we can work backward from these two equations to deduce what $i_C,$ $ j_C,$ $i_S,$ and $j_S$ must be for any $i$ and $j.$ Let's work on the $i$ coordinate first. First, subtract $1$ from both sides of the equation: $$ i - 1 = i_C - 1 + M(i_S - 1). $$ Next, divide the equation for $i$ by $M$ on both sides: $$ \frac{i - 1}M = \frac{i_C - 1}M + (i_S - 1). $$ By definition, $i_S$ is an integer, so whatever the fractional part of $\frac{i - 1}M$ is, that is also the fractional part of $\frac{i_C - 1}M.$ The "floor" function $\lfloor x\rfloor$ has the effect of subtracting the fractional part from whatever number you give it, that is, $\left\lfloor \frac{i - 1}M \right\rfloor = \frac{i - 1}M - f$ where $f$ is the fractional part of $\frac{i - 1}M.$ Subtracting this fractional part from both sides of the equation gives us $$ \left\lfloor \frac{i - 1}M \right\rfloor = \left\lfloor \frac{i_C - 1}M \right\rfloor + (i_S - 1). $$ Now here's why we subtracted $1$ earlier: since $1 \leq i_c\leq M,$ we know that $0 \leq i_c \leq M - 1$ and therefore $0 \leq \frac{i_C - 1}M < 1$; that is, $\frac{i_C - 1}M$ is its own fractional part, and $\left\lfloor \frac{i_C - 1}M\right\rfloor = 0.$ That gives us $$ \left\lfloor \frac{i - 1}M \right\rfloor = i_S - 1, $$ that is, $$ i_S = \left\lfloor \frac{i - 1}M \right\rfloor + 1. $$ But we want to know the coordinates of the upper left cell of that square; since that cell is on row $1$ within the $M\times M$ square, its row number $i_{UL}$ within the entire $N\times N$ puzzle is $$ i_{UL} = 1 + M(i_s - 1) = 1 + M \left\lfloor \frac{i - 1}M \right\rfloor. $$

For similar reasons, the column number $j_{UL}$ of that cell within the entire puzzle is $$ j_{UL} = 1 + M \left\lfloor \frac{j - 1}M \right\rfloor. $$


A variation on these formulas is to use the "ceiling" function $\lceil x\rceil$ instead of the "floor" function. In that case, we skip the "subtract one" step, and instead count on the fact that if $1\leq i_C\leq M,$ then $\left\lceil \frac{i_C}M \right\rceil = 1$ always, and we find that $$ i_S = \left\lceil \frac iM \right\rceil,$$ leading to the formulas \begin{align} i_{UL} &= M\left\lceil \frac iM \right\rceil - M + 1, \\ j_{UL} &= M\left\lceil \frac jM \right\rceil - M + 1. \end{align}

Another alternative (which I would prefer as a programmer) is to number the rows and columns within the entire puzzle from $0$ to $N-1$ instead of from $1$ to $N,$ and within the array of squares or an individual square to number the rows and columns from $0$ to $M-1$ instead of from $1$ to $M.$ That is, in this scheme we number the rows and columns the way the elements of a C# array are numbered. (If you want the user to see row and column numbers $1$ through $N$ you can always add $1$ to each row or column number when you show it to the user.)

Then the "floor" formulas come out to \begin{align} i_{UL} &= M\left\lfloor \frac iM \right\rfloor, \\ j_{UL} &= M\left\lfloor \frac jM \right\rfloor. \end{align}

$\endgroup$
  • $\begingroup$ Thanks for your answer but I'm not sure if I have understood it. If I have a $N\times N$ soduku it iwll have $N$ rows and $N$ columns. I don't understand why you said: The complete Sudoku grid therefore has $N^2$ rows and $N^2$ columns. $\endgroup$ – VansFannel Nov 30 '17 at 7:19
  • 1
    $\begingroup$ The number of rows in a complete Sudoku is always a square number. This number was $N^2$ in my initial version of this answer. But since you are more comfortable using just $N$ for the number of rows in the complete Sudoku, I changed the answer to use a different name, $M,$ for the number of rows in the inner square. Then $M=\sqrt N,$ which is an integer because $N$ is a square number, and $N=M^2.$ Alternatively I could have written $\sqrt N$ everywhere instead of $M,$ but I think that would make the answer harder to read. $\endgroup$ – David K Nov 30 '17 at 13:15
2
$\begingroup$

Yes, and these formulae are especially simple to be programmed. Coordinates $(x,y)$ of the top left corner of an inner square for any cell $(i,j)$ are given by formulae $x=1+((i-1) \operatorname{shr} k) \operatorname{shl} k$ and, similarly $y=1+((j-1)\operatorname{shr} k) \operatorname{shl} k$, where $\operatorname{shr} k$ (resp., $\operatorname{shl} k$) shifts the binary non-negative integer by $k$ bits to the right (resp., to the left). That is, $t \operatorname{shr} k=\left\lfloor t/2^k\right\rfloor$ and $t \operatorname{shl} k=2^k\cdot t$. This formula can be easily generalized to the case when the side of an inner square is $2^k$ to $x=1+(i-1 \operatorname{shr} k) \operatorname{shl} k$ and $y=1+(j-1 \operatorname{shr} k)\operatorname{shl} k$. In general case when the side of an inner square is $n$ we have $x=1+n\cdot ((i-1) \operatorname{div} n)$ and $y=1+n\cdot ((j-1) \operatorname{div} n)$, where $t \operatorname{div} n=\left\lfloor t/n\right\rfloor$ denotes the largest integer number $m$ such that $mn\le t$. At last, I remark that if we start the coordinates of the cells not from $1$ but from $0$ instead, the formulae for the corners will became even more simple, because we’ll do not need to substrat and to add $1$ anymore. For instance, when inner squares have side $2$, we have $x=i \operatorname{shr} k \operatorname{shl} k$ and $y=j \operatorname{shr} k \operatorname{shl} k$.

PS. The generalization of all above stuff to high-dimensional case is straightforward. :-)

$\endgroup$
  • $\begingroup$ It seems to me that you are considering the basic case $2^k=2$, i.e. $k=1$ in the first few sentences, but without explicitly stating that? May be clearer if we did ‘shl 1’ and ‘shr 1’ to start with, and then proceeded with generalisations? $\endgroup$ – user491874 Nov 27 '17 at 20:42
0
$\begingroup$

If I understand you correctly:

The top-left cell in the innermost 2x2 square containing the cell in row $m$, column $n$ is located in row $2 \lceil m/2 \rceil - 1$, column $2 \lceil n/2 \rceil - 1$.

$\lceil x \rceil$ is the ceiling function, which should be available through the C# Math.Ceiling() method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.