Equation for number placement in Sudoku-like grid

[zeb]

Here's a problem that I need help figuring out...

imagine a 9x9 grid filled with the numbers 1-81 starting in the upper left corner and progressing left to right, top to bottom; like so:

/--------------------------------------------\
|   1,  2,  3  |   4,  5,  6  |   7,  8,  9  |
|  10, 11, 12  |  13, 14, 15  |  16, 17, 18  |
|  19, 20, 21  |  22, 23, 24  |  25, 26, 27  |
|--------------------------------------------|
|  28, 29, 30  |  31, 32, 33  |  34, 35, 36  |
|  37, 38, 39  |  40, 41, 42  |  43, 44, 45  |
|  46, 47, 48  |  49, 50, 51  |  52, 53, 54  |
|--------------------------------------------|
|  55, 56, 57  |  58, 59, 60  |  61, 62, 63  |
|  64, 65, 66  |  67, 68, 69  |  70, 71, 72  |
|  73, 74, 75  |  76, 77, 78  |  79, 80, 81  |
\--------------------------------------------/

Also imagine that within this grid of numbers are nine subdivisions which contain nine of the above numbers in a 3x3 grid (like a sudoku puzzle). Let's call these subdivisions blocks.

So the first block contains the numbers 1,2,3,10,11,12,19,20,21. The blocks are numbered 1-9 in the same direction (left to right, top to bottom) that the smaller squares are. So block #9 contains the numbers 61,62,63,70,71,72,79,80,81.

I need to come up with a formula to determine which block any given number is in. For example, the number 28 appears in block #4, number 20 appears in block #1, number 68 appears in block #8.

Any ideas?

 

[matt grime]

yes, any number n is uniquely expressible as 9p+q where q is between 0 and 8.

 

[zeb]

Thanks for your reply... I'm trying to figure out how to use the expression you wrote... Let's say I have the number 44, how do I get to the number 6 using the expression you wrote?

 

[BSMSMSTMSPHD]

I don't have a lot of time today to work on this, but I found a formula that will describe which row and column each number is in:

row # = ((n - n mod 9)/9)+1

call this number R

column # = ((n - R) mod 8) +1

call this number C

The location of the number n in the grid is Rth row, Cth column.

Not sure if this helps - I'll keep working on it though!

 

[zeb]

Thanks for your input. Unfortunately, I don't really need the row and column. I'm writing a web script, and I'm looking for the most efficient way of determining the block number. Obviously this scenario is very small, so I could write up some arrays and logic tests to find out which block a number is in, but I'd like to find a solution without using any (or many) logic tests... If it's possible.

 

[matt grime]

How do I get to the number 6 using the expression you wrote?

By thinking a little about it and using a little common sense. You were using these kinds of grid in kindergarten quite possibly. (If it were a ten by ten grid you'd have no trouble doing this at all. Try thinking on that.) Sorry if you'd rather I gave you the answer, but won't take long to figure out and it's better for you.

 

[pi-r8]

Or you do what I did when I was trying to solve that problem and give up and simply have the user imput numbers by block, so you start off knowing the block number and go from there to the row and column number.

 

[zeb]

By thinking a little about it and using a little common sense. You were using these kinds of grid in kindergarten quite possibly. (If it were a ten by ten grid you'd have no trouble doing this at all. Try thinking on that.) Sorry if you'd rather I gave you the answer, but won't take long to figure out and...

While I appreciate your help, I do not need to be insulted in the process. Most people frequent forums for assistance, not to give others the opportunity to exercise their arrogance and ...

...it's better for you.

self-righteous condescension.

I happen to enjoy a good challenge (which is why I'm building a Sudoku solver in the first place), but the search for the most efficient path is eluding me. Here is what I have so far (and my apologies to BSMSMSTMSPHD for initially ignoring the need for the row and column; it wasn't until a little bit later that I realized that the row and column certainly do help pin-point the block):

3 * floor( floor( (n-1)/9 )/3 ) + ceil( ( n mod 9 ? n mod 9 : 9 )/3 )

(I'm using PHP which uses function like 'ceil' and 'floor' for rounding down and up to the nearest integer.)

matt grime, if you can come up with a better solution, please do, that's what I'm posting here for. Just keep your ego out of it.

Thank you.

 

[0rthodontist]

3 * floor((n -1)/27) + floor(((n - 1) mod 9) / 3) + 1

 

[zeb]

3 * floor((n -1)/27) + floor(((n - 1) mod 9) / 3) + 1

That's perfect! Thanks! I was afraid to simplify the first part down to floor((n-1)/27), because of the rounding, but now that I look at it, it makes sense to use 27 because that is the vertical difference between the large blocks. And shifting the column portion of the equation to result in 0,1,2 and then adding 1 helps avoid the logic test.

Thanks so much!

 

[matt grime]

This problem looks like homework; I know of several comp sci people asked to write a sudoku solver for homework. It is not the policy here to just give out answers to homework, but to point people in the right direction.

Weren't you made to draw a 'number grid' or something when at school? 10x10 grid with the numbers 1,.,100 on it that you were supposed to use to spot patterns and things (multiples of 9 on an off diagonal etc)? There you can read off the grid position of any number, the two digit number xy lies in row x column y (start counting from 0). This is the base 9 version of it which is exactly what I posted in the first reply. It gives you the exact row and column of any square, it is then straight forward to work out the block it lies in.

Sorry that you didn't like that I didn't write out the answer for you. At least someone else was kind enough to do it for you.