Share your knowledge at the LQ Wiki.
 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, 09: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, 10:32 AM #2 corp769 LQ Guru   Registered: Apr 2005 Posts: 5,817 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, 11:34 AM #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, 01: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, 03:02 PM #5 corp769 LQ Guru   Registered: Apr 2005 Posts: 5,817 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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post us_ed Linux - Hardware 27 10-05-2010 12:35 PM pramod123 Ubuntu 0 08-18-2009 05:32 AM ewt3y Programming 21 08-30-2005 12:09 PM chaitanyakorde Linux - Newbie 3 04-16-2004 12:09 AM

LinuxQuestions.org

All times are GMT -5. The time now is 01:24 AM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -