LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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

Reply
 
Search this Thread
Old 04-08-2011, 10:49 AM   #1
Jorek
Member
 
Registered: Sep 2005
Distribution: Slackware 13.1
Posts: 65

Rep: Reputation: 16
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?
 
Click here to see the post LQ members have rated as the most helpful post in this thread.
Old 04-08-2011, 11:32 AM   #2
corp769
Guru
 
Registered: Apr 2005
Posts: 5,814

Rep: Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001
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.
Old 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: Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942
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.
Old 04-08-2011, 02:21 PM   #4
Jorek
Member
 
Registered: Sep 2005
Distribution: Slackware 13.1
Posts: 65

Original Poster
Rep: Reputation: 16
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.
 
Old 04-08-2011, 04:02 PM   #5
corp769
Guru
 
Registered: Apr 2005
Posts: 5,814

Rep: Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001Reputation: 1001
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
 
  


Reply

Tags
java


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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


Similar Threads
Thread Thread Starter Forum Replies Last Post
in Fedora 11 square screen have not adjust square of monitor. us_ed Linux - Hardware 27 10-05-2010 01:35 PM
Ubantu LTS on Upgrade displays "Square box" for each character pramod123 Ubuntu 0 08-18-2009 06:32 AM
Let us develop a C program to resolve the Sudoku square ewt3y Programming 21 08-30-2005 01:09 PM
PS2 mouse pointer problem Looks like a square box chaitanyakorde Linux - Newbie 3 04-16-2004 01:09 AM


All times are GMT -5. The time now is 03:42 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration