Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org [SOLVED] Sudoku - How to calculate the correct Box for a given Square?
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 04-08-2011, 10:49 AM #1 Jorek Member   Registered: Sep 2005 Distribution: Slackware 13.1 Posts: 65 Rep: Sudoku - How to calculate the correct Box for a given Square? Hi! Im doing a sudoku-solver as a school assigment in Java. It is supposed to solve both 6x6, 9x9 and 12x12 boards. Im pretty much done with my algorithm(brute force), but I'm having a hard time figuring out how to calculate the right Box for a Square. I found this snippet: Code: ```// calculate BoardPos for index, where index is 0..80 void loadBoardPosFromIndex(BoardPos &pos, int index) { pos.index = index; pos.row = index / 9; pos.col = index - (pos.row * 9); int boxRow = pos.row / 3; int boxCol = pos.col / 3; pos.box = (boxRow*3) + boxCol; }``` This works on 9x9 boards, but I really dont get the math behind this, and how I can create a generic rule for both 6x6, 9x9 and 12x12 boards. Any advice?
 04-08-2011, 11:32 AM #2 corp769 Guru   Registered: Apr 2005 Posts: 5,814 Rep: By the looks of the math, pos.row = index / 9 is calculating the row based off of the index being sent to the function; Divided by 9 gives you the row. Pos.col figures out the column. I'm pretty horrible at explaining, but if you break the math down, it is all common sense when you look at it from a general perspective. Take boxRow for example - row location divided by three will give you the result because in a 9x9 board, you have groups of 3 sections per part of the sudoku board. Hope that helps man, Josh 1 members found this post helpful.
 04-08-2011, 12:34 PM #3 Nominal Animal Senior Member   Registered: Dec 2010 Location: Finland Distribution: Xubuntu, CentOS, LFS Posts: 1,723 Blog Entries: 3 Rep: Corp769 said the important thing in his first sentence: Given an index to a zero-based row-major array, you find the row by dividing by the width, the column is then the remainder. If you consider how you calculate the index in the first place, Code: `index = x + y * width` elementary algebra tells you how to solve the inverse: Code: ```x = index / width y = index % width``` where / is integer division, and % gives you the remainder. (% is called the modulus operator, MOD in math and some programming languages.) For a 9x9 sudoku, the indices to a (zero-based row-major) array are Code: ``` 0 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``` In order to support other configurations, let's use constants Code: ``` boxwidth = 3 /* Width of a small box */ boxheight = 3 /* Height of a small box */ hboxes = 3 /* Boxes horizontally */ vboxes = 3 /* Boxes vertically */ width = boxwidth * hboxes height = boxheight * vboxes``` Given an index i into the array, finding the overall row and column should be obvious now: Code: ``` y = i / width x = i % width``` To find which column and row of boxes that is in, just do the same again for each of the coordinates. Code: ``` boxy = y / boxheight /* Box row */ innery = y % boxheight /* Row within the box */ boxx = x / boxwidth /* Box column */ innerx = x % boxwidth /* Column within the box */``` If you want to calculate the index of the box (here, 0 to 8), you do the inverse operation, multiply row by width and add the column: Code: ` box = boxx + hboxes * boxy` If you are interested why I qualified my post with "zero-based row-major array", not all programming languages arrange arrays like this. According to Wikipedia, Fortran, R, MATLAB and Octave use column-major order for arrays -- i.e. transposed compared to above, swapping width and height, and row and column. In Fortran for example, array indices also start at 1 by default -- making arrays in Fortran "one-based column-major arrays": Code: ```fortran_column = 1 + (fortran_index - 1) / height fortran_row = 1 + MOD(fortran_index - 1, height) fortran_index = fortran_row + (fortran_column - 1) * height``` Hope this helps. 2 members found this post helpful.
 04-08-2011, 02:21 PM #4 Jorek Member   Registered: Sep 2005 Distribution: Slackware 13.1 Posts: 65 Original Poster Rep: Thanks a lot guys! I think I get it now! =) I'll do some more work over the weekend, and apply the theory, then I'll mark this as solved. Again, thank you very much. Cheers, Jorek.
 04-08-2011, 04:02 PM #5 corp769 Guru   Registered: Apr 2005 Posts: 5,814 Rep: Not a problem! I wish I could just explain things like Nominal Animal -Josh Edit: To Nominal - I gave you rep because you did a better job at explaining that, LOL

 Tags java