View previous topic :: View next topic 
Author 
Message 
 havard
 Joined: 20 Oct 2005  Posts: 14  :   Items 

Posted: Tue Jan 31, 2006 2:10 am Post subject: How many possible unique rectangels? 


Hi.
I was wondering how many possible unique rectangels there are in a sudoku grid? My solver checks 486. Does anyone know if this is the correct amount?
thanks
Havard _________________ Sudoku Assistenten : www.sudoku.frihost.net 

Back to top 


 juggle5
 Joined: 20 Apr 2006  Posts: 3  :   Items 

Posted: Thu Apr 20, 2006 8:32 am Post subject: 


I'm not sure what you're counting; nothing I compute comes to 486. Here's what I get:
To form a rectangle in a grid, we must choose two horizontal lines for the top and bottom, and choose two vertical lines for the left and right sides. These are independent, so multiply them together to get the total number of possibilities. For example, for a 2x3 grid:
Code: 
++++
   
++++
   
++++

there are 3x4 rows and columns of lines. So there are (3 choose 2) rows * (4 choose 2) columns = 3 * 6 = 18 rectangles we can make (assuming the corners of the rectangles are on the +'s).
For a sudoku board, there would be (10 choose 2)*(10 choose 2) = 45*45 = 2025 rectangles.
(To calculate choosing numbers, also known as binomial coefficients, we can use the formula (n choose k) = n*(n1)*(n2)*...*(nk+1) / (k*(k1)*...*3*2*1), so in particular, (n choose 2) = n*(n1)/2.)
Since I'm getting lots more than you computed, perhaps we're counting different things..
The number of different SIZES of rectangles (regardless of positioning) would be (number of possible widths)*(number of possible heights); for a 9x9 grid = 10x10 gridlines as in sudoku, the widths could be 1,2,3,...10; and same with the heights, meaning there would be 10*10 = 100 sizes of rectangles.
If you counted a 2x3 rectangle the same as a 3x2 rectangle, then all the nonsquare rectangles would be counted twice, so there would only be... 10*9/2 (different dimensions) + 10 (squares) = 55 sizes of rectangles.
Hope this is useful.. 

Back to top 


 Myth Jellies
 Joined: 20 Sep 2005  Posts: 14  :   Items 

Posted: Tue Apr 25, 2006 2:50 am Post subject: 


For every cell, I get 6*2 (rows) + 2*6 (columns). Multiply by 81 cells & divide by four cells per rectangle....
(6 * 2 + 2 * 6) * 81 / 4 = 486 _________________ Myth Jellies 

Back to top 


 juggle5
 Joined: 20 Apr 2006  Posts: 3  :   Items 

Posted: Tue Apr 25, 2006 3:34 am Post subject: 


Quote:  For every cell, I get 6*2 (rows) + 2*6 (columns). Multiply by 81 cells & divide by four cells per rectangle....
(6 * 2 + 2 * 6) * 81 / 4 = 486 
I'm confused; obviously I'm missing something. Could you explain this one more time so I can see what you're doing? I'm pretty good at math, but I don't understand where the 6*2 comes in for the rows or columns. Since the grid is 9x9, I would expect the answer would be something with 9's (or 10's if you are dealing with gridlines rather than squares) in it..
Thanks! 

Back to top 


 rkral
 Joined: 21 Oct 2005  Posts: 233  :   Items 

Posted: Tue Apr 25, 2006 10:30 am Post subject: 


juggle5 wrote:  I don't understand where the 6*2 comes in for the rows or columns. 
A unique rectangle can only exist in exactly two 3x3 boxes in a stack (tower, chute) or exactly two boxes in a band (floor, chute). 

Back to top 


 juggle5
 Joined: 20 Apr 2006  Posts: 3  :   Items 

Posted: Sun Apr 30, 2006 5:23 am Post subject: 


Thanks a bunch for clarifying.
I didn't realize that a "unique rectangle" was a specific termI was interpreting "unique" just as "different," so I was counting rectangles in general.
I agree with you on 486. I count it this way:
For one particular band, there are (3 choose 2) squares in which to place the rectangle corners; within each square there are 3 columns in which to pick the left side of the rectangle, and 3 columns for the right side. There are (3 choose 2) ways to pick the top and bottom. This gives (3 choose 2)^2 * 3^2 = 81 unique rectangles for one band. There are 3 bands, and a similar argument holds for stacks. Thus there are 81*3*2 = 486 ways.
This generalizes to other sizes of sudoku as 2*n*n^2*(n choose 2)^2 = ( n^5 * (n1)^2 ) / 2. When n = 3, we get 486; for a giant 25x25 sudoku (n=5) there are 5^5*(4^2)/2 = 25000 unique rectangles. 

Back to top 


