I'm implementing a sudoku solver using backtracking. It reads a sudoku board in the form:
027800061000030008910005420500016030000970200070000096700000080006027000030480007
I know how I can figure the elements on a column by doing index % 9 (and then doing a simple arithmetic progression of ratio 9) as well the elements on a line by using index/9 (and then by adding one until I get every one of them), where index is a number in the range [0,80].
What I cannot figure out is how to get the starting index of a box if I have an element's index in that box.
So I googled and I got: http://jakevdp.github.io/blog/2013/04/15/code-golf-in-python-sudoku/
This guy is getting the starting index in a box like this:
start = 27 * int(i / 27) + 3 * int((i % 9) / 3)
Where i is the index in my list of elements.
I cannot understand how he figured out that formula and how can I deduce it myself, so please explain that to me.
I understand the list comprehension that comes after this formula, it all makes sense just not this formula.
PS: I write this to learn Haskell, but it really doesn't matter, since now I want to get the gist of that formula.
index means index into your list. blockRow, blockCol and blockIndex refer to row/column/index of the block start. All divisions are integer divisions (rounding down to next integer).
index = row*9 + col
row = index / 9
col = index % 9
blockRow = (row / 3) * 3
blockCol = (col / 3) * 3
blockRow = (index / 9 / 3) * 3 = (index / 27) * 3
blockCol = (index % 9 / 3) * 3
blockIndex = (blockRow*9) + blockCol = ((index / 27) * 3 * 9) + (index % 9 / 3) * 3 =
(index / 27) * 27 + 3 * (index % 9 / 3)