Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equation for number placement in Sudoku-like grid

  1. Apr 17, 2006 #1

    zeb

    User Avatar

    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 (Text):

    /--------------------------------------------\
    |   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?
     
  2. jcsd
  3. Apr 17, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    yes, any number n is uniquely expressible as 9p+q where q is between 0 and 8.
     
  4. Apr 17, 2006 #3

    zeb

    User Avatar

    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?
     
  5. Apr 17, 2006 #4
    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: Apr 17, 2006
  6. Apr 17, 2006 #5

    zeb

    User Avatar

    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.
     
  7. Apr 17, 2006 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper


    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.
     
  8. Apr 17, 2006 #7
    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.
     
  9. Apr 17, 2006 #8

    zeb

    User Avatar

    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 ...
    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 (Text):
    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: Apr 17, 2006
  10. Apr 17, 2006 #9

    0rthodontist

    User Avatar
    Science Advisor

    3 * floor((n -1)/27) + floor(((n - 1) mod 9) / 3) + 1
     
  11. Apr 18, 2006 #10

    zeb

    User Avatar

    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!
     
  12. Apr 18, 2006 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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: Apr 18, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Equation for number placement in Sudoku-like grid
Loading...