FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    How many possible unique rectangels?          Sudoku Programmers Forum Index -> The mathematics of sudoku 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*(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 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 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 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron