0
$\begingroup$

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?

$\endgroup$

migrated from scicomp.stackexchange.com Dec 25 '14 at 15:46

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

  • $\begingroup$ 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. $\endgroup$ – Paul Dec 25 '14 at 8:21
  • $\begingroup$ @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. $\endgroup$ – john Dec 25 '14 at 8:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Federico Poloni Dec 25 '14 at 15:31
  • $\begingroup$ 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. $\endgroup$ – peterwhy Dec 25 '14 at 15:53
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – john Dec 26 '14 at 3:04
  • $\begingroup$ What are some examples of your table data and formula? $\endgroup$ – peterwhy Dec 26 '14 at 3:06
  • $\begingroup$ 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 $\endgroup$ – john Dec 26 '14 at 4:11
  • $\begingroup$ 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$. $\endgroup$ – peterwhy Dec 26 '14 at 4:12
  • $\begingroup$ 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. $\endgroup$ – john Dec 26 '14 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.