# sudoku algorithm explanation formula

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?

## migrated from scicomp.stackexchange.comDec 25 '14 at 15:46

This question came from our site for scientists using computers to solve scientific problems.

• Hi zae and welcome to scicomp! I really don't think this is the best site for your question, since it deals with the algorithm to solve a game. It might do well in the game developers SE or the math SE site. – Paul Dec 25 '14 at 8:21
• @Paul oh, oakay I will ask there. I'm sorry, i'm so confused abaut this question. I already ask in stackoverflow but someone said this is math question. – john Dec 25 '14 at 8:23
• If the question is "how do I come up with these formulas", it's just logic/mathematization and I'd ask on math.se. That site is less research-oriented and more suited to explaining basic maths; one can get really insightful answers on these mental processes there. – Federico Poloni Dec 25 '14 at 15:31
• The author: It’s an array (line 193) with 81 values representing positions from 0 to 80. The value at n-th position is the one you will find on the table at row floor(n/9) and column n%9. – peterwhy Dec 25 '14 at 15:53

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. • I know how they work. But I don't know to make the formula. For example if I have another table data, for another case, I want to make formula, how can I determine the formula for that pattern. I tried with arhitmatic and geometry but it fails. Also I tried regression, but cam with non integer formula.. – john Dec 26 '14 at 3:04 • What are some examples of your table data and formula? – peterwhy Dec 26 '14 at 3:06 • This is for sudoku case : docs.google.com/spreadsheets/d/… . The number marked with red is the pattern. It's like f(x) function. x is the black number, and f(x) is the red one. I just confuse how to derive the formula like f(x) = x mod 9 or something else. Thanks – john Dec 26 '14 at 4:11 • Which is what I wrote in my answer, find the quotient and the remainder when the cell number is divided by$9$. Focus on the$9\times 9$grid in your spreadsheet and the cell$42$. The row number, or how many complete rows are before$42$, is$\lfloor 42/9\rfloor$. The remainder of the division,$42 \bmod 9$, gives how many complete columns are before$42$. – peterwhy Dec 26 '14 at 4:12 • I know how the function work, I just don't know how to explain that from the table, how can I get the function. I mean, how to get the formula if I dont have the answer (I don't know floor($cell/9) or $cell % 9). I just have the table. How can I explain that from the table I can conclude that the pattern was$cell%9, is that only by guessing or there is a math method ? It also to explain the block formula. – john Dec 26 '14 at 4:18