Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

How many possible unique rectangels?

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
havard

Joined: 20 Oct 2005
Posts: 14
:

Items
PostPosted: Tue Jan 31, 2006 2:10 am    Post subject: How many possible unique rectangels? Reply with quote

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? Smile

thanks

Havard
_________________
Sudoku Assistenten : www.sudoku.frihost.net
Back to top
View user's profile Send private message Send e-mail Visit poster's website
juggle5

Joined: 20 Apr 2006
Posts: 3
:

Items
PostPosted: Thu Apr 20, 2006 8:32 am    Post subject: Reply with quote

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*(n-1)*(n-2)*...*(n-k+1) / (k*(k-1)*...*3*2*1), so in particular, (n choose 2) = n*(n-1)/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 non-square 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
View user's profile Send private message
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Tue Apr 25, 2006 2:50 am    Post subject: Reply with 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
_________________
Myth Jellies
Back to top
View user's profile Send private message
juggle5

Joined: 20 Apr 2006
Posts: 3
:

Items
PostPosted: Tue Apr 25, 2006 3:34 am    Post subject: Reply with quote

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! Smile
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Tue Apr 25, 2006 10:30 am    Post subject: Reply with quote

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
View user's profile Send private message
juggle5

Joined: 20 Apr 2006
Posts: 3
:

Items
PostPosted: Sun Apr 30, 2006 5:23 am    Post subject: Reply with quote

Thanks a bunch for clarifying.

I didn't realize that a "unique rectangle" was a specific term--I 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 * (n-1)^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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron