[Math] sudoku algorithm explanation formula

algorithms

I'm implementing a sudoku solver using human way algorithm. Which have 3 constraint, different number ini row, cell and box.

I googled and I got http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/. But I cannot understand how this guy get floor($cell / 9) for return_row function or floor(return_row($cell) / 3) * 3 + floor(return_col($cell) / 3) for return_block.

I try to figure it out by write down the data in excel and I know there is some pattern like this :

[cell] [column]
0      0
1      1
2      2
3      3
4      4
5      5
6      6
7      7
8      8
9      0

But how did he figure it out that the formula was $cell % 9 ?

I want to know, if I don't know the answer for the formula, how can I calculate that ? How can I determine that formula ? What method should I use?

Thanks

— UPDATE —

Based on @peterwhy answer now I understand about the row, col and block.
I know about is_possible_col and is_possible_row , which show that index = 9*row + col so from here we get row = floor(index/9) and col = index % 9.

Now I confused about is_possible_block function. @peterwhy said :

floor($block/3)*27 + 9*floor($x/3) is 9 times the number of rows
before the cell, $x%3 + 3*($block%3) is the number of columns before
the cell.

Which make me think like this:

9row+col
9(floor($block/3)*3 + floor($x/3)) + ($x%3 + 3*($block%3))

row = 3row_block+row_x_block

9(3(floor($block/3) + floor($x/3))) + ($x%3 + 3*($block%3))
floor($block/3) = row_block
    floor($x/3) = row_x_block

col = 3col_block+col_x_block

How col = 3col_block+col_x_block , because what I know, the formula should be like this : col = 3row_block+col.

I know col_x_block mean column position on 0-8 block. And row_block mean row position on 0-2 block.

Please see this to see the detail calculation.

How do you explain this?

Best Answer

floor($cell/9) and $cell % 9 are just how (integer) quotient and remainder are calculated in programming language. The $cell indices are arranged row by row. The row number can be obtained as a quotient and the column number can be obtained as a remainder.

Take the cell numbered $42$ as an example. By division, $$42 = 9\cdot4 + 6$$ hence the cell is located on the 4th row (0-based) and the 6th column (also 0-based).

The block number is just sightly more complicated. The first part, floor(return_row($cell) / 3) * 3, first calculates the quotient of the row number divided by $3$. So rows $0$ to $2$ are in the first third, and $6$ to $8$ are in the last third. Then this "group of 3 rows" index is multiplied by $3$, because there are 3 blocks for each group of 3 rows.

The second part, floor(return_col($cell) / 3), again find the quotient of the column number divided by $3$.

Taking the same example of cell $42$, which is on row 4 and column 6. The row number $$4 = 3\cdot\color{red}1 + 1;\;\left\lfloor\frac43\right\rfloor = \color{red}1$$ the quotient $\color{red}1$ means the cell is on the 1st "group of 3 rows" (0-based). And the column number $$6 = 3\cdot\color{blue}2+0;\;\left\lfloor\frac63\right\rfloor = \color{blue}2$$ the quotient $\color{blue}2$ means the cell is on the 2nd "group of 3 columns" (also 0-based). Combining this two information, the block where cell $42$ is at is assigned a block index $$\color{red}1\cdot 3 + \color{blue}2 = 5$$

Again, take $42$ as an example:

$$\begin{array}{l|l|ccc|ccc|ccc|} \text{Row}&\text{Cells}&0&1&2&3&4&5&6&7&8\\ \hline 0&0-8&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc\\ 1&9-17&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc\\ 2&18-26&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc\\ \hline 3&27-35&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc\\ 4&36-44&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\color{red}\bigcirc&\cdots\\ \end{array}$$

Notice the red $\color{red}\bigcirc$ is the 43rd $\bigcirc$. Elementary division says $\lfloor42/9\rfloor=4$ gives how many complete groups of $9$ the $42$ black $\bigcirc$s can form:

$$\begin{array}{l|l|ccc|ccc|ccc|} \text{Row}&\text{Cells}&0&1&2&3&4&5&6&7&8\\ \hline \color{blue}0&0-8&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc\\ \color{green}1&9-17&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc\\ \color{blue}2&18-26&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc&\color{blue}\bigcirc\\ \hline \color{green}3&27-35&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc&\color{green}\bigcirc\\ 4&36-44&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\bigcirc&\color{red}\bigcirc&\cdots\\ \end{array}$$

And the remaining $42\bmod 9=6$ black $\bigcirc$s count how many columns are before the red $\color{red}\bigcirc$. Since the row number and column number are $0$-based, the quotient $4$ and the remainder $6$ also denote the row and column numbers respectively.

Related Question