# closed form equation to figure out sudoku square from given index

Let's say I have a 1D array of 81 elements, which could be thought of as representing a Sudoku board... a 9x9 matrix (every 9 elements create a new row). The question is, given an index into the 1D array, is there a closed form equation to return the square in which that element exists on the Sudoku board and can you prove the equation is correct?

For example, if you're given index 10, the result would be 0 since the 10th element is in the top left 3x3 square. If you're given index 75, the result would be 7 since the 76th element is in the bottom middle 3x3 square.

array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80]

Sudoku board:

[  0,  1,  2|,  3,  4,  5|,  6,  7,  8]
[  9, 10, 11|, 12, 13, 14|, 15, 16, 17]
[ 18, 19, 20|, 21, 22, 23|, 24, 25, 26]
-----0-----  -----1-----  -----2-----
[ 27, 28, 29|, 30, 31, 32|, 33, 34, 35]
[ 36, 37, 38|, 39, 40, 41|, 42, 43, 44]
[ 45, 46, 47|, 48, 49, 50|, 51, 52, 53]
-----3-----  -----4-----  -----5-----
[ 54, 55, 56|, 57, 58, 59|, 60, 61, 62]
[ 63, 64, 65|, 66, 67, 68|, 69, 70, 71]
[ 72, 73, 74|, 75, 76, 77|, 78, 79, 80]
-----6-----  -----7-----  -----8-----

-

The solution I came up with is floor((index % 9) / 3) + 3 * floor(index / (9 * 3)). My reasoning behind this solution is the following...

So a sudoku "board" is a grid, right? You can look at it as a 3 by 3 matrix of 3 by 3 matrices and a 9 by 9 matrix of squares, where you can number each element from left to right, top to bottom.

Given any index [0, 80] in the 1D array, if you mod it by 9 you will get which column it is in in the 9x9 matrix... divide that by 3 and you get which column it is in the 3x3 matrix (and take the floor of the whole thing to avoid nasty decimals).

So at this point you essentially have an x coordinate. Now you have to find the y.

Taking that index and dividing it by 9 will tell you which row it is in in the 9x9 matrix, since each row starts at every 9th element in the 1D array. If you divide that by 3 you get which row the index is in in the 3x3 matrix. You could I think of this as dividing by 27, since there are 27 elements in each row in the 3x3 matrix.

However, both calculations give you a value between 0 and 2 inclusive. But they are your x and y coordinates. Now to get the correct square, I just multiply the y coordinate by 3 and sum the values together. The result is between 0 and 8 inclusive, where I starting the squares from left to right, top to bottom.

I'm pretty sure this works... but I don't know how to prove it.

-

First, think about the relation between the index $i$ in your array and the row and column numbers, $r$ and $c$. It is $r=\lfloor \frac i9 \rfloor, c=i \pmod 9$. Then the row block, $rb$,(which horizontal block the index is in) and column block, $cb$ (which vertical block the index is in) ares $rb=\lfloor \frac i{27} \rfloor, cb=\lfloor \frac c3 \rfloor$ Finally the square $s=3\cdot rb + cb$

-