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)
Sorry to necro-bump this, but here's a solution someone may find interesting (provided you can read lisps; Clojure in this case). It returns the indices of each "sector" of a sudoku board, and is general enough to be used for many different board sizes. standard-9-sector-indices assumes the board is split into 9 sectors, so the board width/height should be a multiple of 3. get-sector-indices can be used for any board size however:
(defn get-sector-indices [board-width sector-top-left-pos sector-dimensions]
(let [[sw sh] sector-dimensions
[tx ty] sector-top-left-pos]
(for [y (range ty (+ ty sh))
x (range tx (+ tx sw))]
(+ x (* y board-width)))))
(defn standard-9-sector-indices [board-dimensions]
(let [[bw bh] board-dimensions
[sw sh :as sd] (map #(/ % 3) board-dimensions)]
(for [y (range 0 bh sh)
x (range 0 bw sw)]
(get-sector-indices bw [x y] sd))))
The dimension arguments should be a vector/list representing a [x y] pair.
(standard-9-sector-indices [9 9])
Returns:
((0 1 2 9 10 11 18 19 20)
(3 4 5 12 13 14 21 22 23)
(6 7 8 15 16 17 24 25 26)
(27 28 29 36 37 38 45 46 47)
(30 31 32 39 40 41 48 49 50)
(33 34 35 42 43 44 51 52 53)
(54 55 56 63 64 65 72 73 74)
(57 58 59 66 67 68 75 76 77)
(60 61 62 69 70 71 78 79 80))
which are the indices of each sector of a standard Sudoku board (tested).
