CODEWITHSUNDEEP
phpalgorithmmathformulasudoku
john
john

Reputation: 57

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

Upvotes: 2

Views: 684

Answers (1)

Cimbali
Cimbali

Reputation: 11395

This comes from the way the cells are counted, which we could call row-major.

You can see block and cell numbers with their respective row and column numbers on this image :

illustrated

rows and columns

The first row (0) contains cells 0 to 8, the second row cells 9 to 17, and so on until row 8, which contains cells 72 to 80.

If you number rows 0 to 8 and columns 0 to 8 as well, we can see that the formula for a cell that corresponds to this numbering is then cell = 9 * row + col, which should explain the formulas for get_row and get_col.

When moving right from any cell by one column, you add 1 to the cell count, which means the formula for the cell number looks like something + col.

When moving down one row, you add to the cell number the amount of cells per row, which here is 9, so the formula also looks like 9 * row + something.

Putting those together, you get a formula that is 9 * row + col + offset : the "+ something"s dependencies is row and col are determined, but maybe they still contain a constant value. In our case, the formula gives the numbering we want with offset=0, but if you started numbering from 1 you formula would be 9 * row + col + 1.

However you do not have to do this reasoning every time. Just now that when you have a rectangle where you count items row by row, the formula for an item's number is always row * row_size + col + number at (0,0). This is also how contiguous memory is allocated for double arrays in C, for example, a very common pattern. If you count column by column, then you have col * col_size + row + number at (0,0)

Blocks

Now blocks are numbered the same way, but there are only 3 rows and columns. You can replace one by one the elements in the get_block formula to understand it : floor(row / 3) * 3 + floor(col / 3)

Since there are 3 rows of blocks but 9 of cells, the (cell-)rows 0, 1 and 2 correspond to the first row of blocks, 3 to 5 to the second row of blocks and 6 to 8 to the final and third row of blocks. What we get out of this is that a row of blocks rb contains the rows of cells 3 * rb, 3 * rb +1 and 3 * rb + 2. The opposite operation is dividing by 3 and flooring, which gets you rb for any of the expressions above.

This works exactly the same for the columns.

Thus when replacing in the expression, we now have : block_row * 3 + block_col. This I'd exactly the same formula (with 3 instead of 9) than we had for the numbering of cells, and thus gets you the number of the block from its row and column.

Upvotes: 4

Related Questions