Equation for number placement in Sudoku-like grid

  • Thread starter zeb
  • Start date

zeb

33
0
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:

Code:
/--------------------------------------------\
|   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). Lets 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

Science Advisor
Homework Helper
9,394
3
yes, any number n is uniquely expressible as 9p+q where q is between 0 and 8.
 

zeb

33
0
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?
 
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!
 
Last edited:

zeb

33
0
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

Science Advisor
Homework Helper
9,394
3
zeb said:
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.
 
138
23
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

33
0
matt grime said:
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 ...
matt grime said:
...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):

Code:
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.
 
Last edited:

0rthodontist

Science Advisor
1,230
0
3 * floor((n -1)/27) + floor(((n - 1) mod 9) / 3) + 1
 

zeb

33
0
0rthodontist said:
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

Science Advisor
Homework Helper
9,394
3
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.
 
Last edited:

Related Threads for: Equation for number placement in Sudoku-like grid

  • Posted
Replies
1
Views
393
Replies
13
Views
6K
Replies
1
Views
1K
Replies
2
Views
2K
  • Poll
  • Posted
Replies
14
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top