FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    2x2 / 16 grids mathematics of - am i right ? Goto page 1, 2  Next          Sudoku Programmers Forum Index -> The mathematics of sudoku View previous topic :: View next topic   Author Message coloin Joined: 05 May 2005 Posts: 97 : Items Posted: Thu May 05, 2005 9:11 pm    Post subject: 2x2 / 16 grids mathematics of - am i right ? I have worked out there are 24x24x24x24 = 331776 combinations of 2x2 grids am i right ? maybe divide by 4 for rotational similarity = 82944 A working grid would be: 1234 3412 2341 4123 This is one of ? 192 working grids 48 if you sort out the rotation. I may well be wrong on this !!!! Back to top Tempbow Joined: 18 Apr 2005 Posts: 22 : Items Posted: Fri May 06, 2005 12:12 pm    Post subject: Re: 2x2 / 16 grids mathematics of - am i right ? coloin wrote: I have worked out there are 24x24x24x24 = 331776 combinations of 2x2 grids am i right ? I would call it a 4x4 grid, but yes, 24**4 represents the number of ways you can place the 4 digits in a 4x4 array such that each row contains one occurrence of 1,2,3,4. There would be no restriction on occurrences per column, though, so few of these would be valid Sudoku. Quote: maybe divide by 4 for rotational similarity = 82944 A working grid would be: 1234 3412 2341 4123 This is one of ? 192 working grids 48 if you sort out the rotation. I may well be wrong on this !!!! If the 4x4 grid complies with Sudoku rules, then you could fill row 1 in 4! ways (4x3x2x1). That's because there are 4 values that can go in cell 1,1 and for each of those there are 3 values left to go in cell 1,2 and for each of those 2 placements there are 2 values left that can go in cell 1,3. Looking at the second row, once you have laid out row 1, there are only 3 values that can go in 2,1 and 2 values in 2,2 and 2 values in 2,3 Looking at row 3 there are 2 values left for 3,1 and 2 values left for 3,2. After that you are left with one choice for the rest. (4x3x2)x(3x2x2)x(2x2) = 1152 valid sudokus How you reduce those for similar patterns is up to you, not only do you have rotations, and horizontal and vertical mirror images, but you could phase shift each number by 1, 2, or 3 such as 1>2 2>3 3>4 4>1 and 1>3 2>4 3>1 4>2 and 1>4 2>1 3>2 4>3 Food for thought? Terry NZ Back to top frazer Joined: 06 May 2005 Posts: 8 : Items Posted: Fri May 06, 2005 2:24 pm    Post subject: Suppose the first block is 12 34 (There are 4!=24 possibilities for this first box, so we'll re-label to suppose that it is exactly this one.) Then the grid must be completed 1 2 [34] 3 4 [12] [2][1] ** [4][3] ** where [12] means 1 and 2, in some order. There are 16 ways to choose the [34], [12], and the vertical [24] and [13]. However, when the columns of the top right block are the rows of the bottom left block, e.g, 12 34 34 21 23 ** 41 ** then there are no solutions (the 2 and 3 would both have to go in the same cell in the bottom right); otherwise, there is one solution. Of the 16, 4 then have no solution and 12 have one. So I get 24x12=288. Frazer Back to top Animator Joined: 26 Apr 2005 Posts: 18 : Items Posted: Fri May 06, 2005 5:11 pm    Post subject: Trying every combination, and applying the sudoku rules, show me that there are 480 possible grids... Can someone explain this number? Last edited by Animator on Fri May 06, 2005 6:15 pm; edited 1 time in total Back to top frazer Joined: 06 May 2005 Posts: 8 : Items Posted: Fri May 06, 2005 6:08 pm    Post subject: I can't see anything wrong with my earlier answer of 288. Even if I've made an error, doesn't my method show that the most you can possibly get is 24x16=384? Back to top Animator Joined: 26 Apr 2005 Posts: 18 : Items Posted: Fri May 06, 2005 6:23 pm    Post subject: I'm sorry, 288 is correct... I made a typo... Back to top Tempbow Joined: 18 Apr 2005 Posts: 22 : Items Posted: Fri May 06, 2005 9:25 pm    Post subject: frazer wrote: I can't see anything wrong with my earlier answer of 288. Even if I've made an error, doesn't my method show that the most you can possibly get is 24x16=384? ROW 1 In row 1, you can fill the first cell 4 ways, the second is then left with 3, the third is left with 2, and the last is left with 1. There are 24 ways of filling row 1. ROW 2 Given the constraint of the 2x2 box, you can fill the first cell of row 2 in only 2 ways, leaving 1 way to fill the second. The third cell can be filled 2 ways and the fourth only 1 way. ROW 3 In row 3, the first cell and second cell can be filled 2 ways each, leaving only 1 possibility for the remaining cells. Total combinations become (4x3x2) x (2x2) x (2x2) = 384 You could divide this number by 2 for each of the permutations like rotate 90, rotate 180, rotate 270, horizontal mirror image, verticle mirror image etc. But that's another subject . . . . Terry NZ Back to top frazer Joined: 06 May 2005 Posts: 8 : Items Posted: Fri May 06, 2005 10:09 pm    Post subject: I think Tempbow is optimistic in what he says about Row 3. What is true is that the first and second cell can be filled 2 ways each, leaving AT MOST 1 possibility for the remaining cells. In fact, quite often (a quarter of the time, in fact), there is NO way to complete the grid. (See my earlier posting for an example.) That's why 288 is correct, rather than 384. Back to top Tempbow Joined: 18 Apr 2005 Posts: 22 : Items Posted: Fri May 06, 2005 10:50 pm    Post subject: frazer wrote: I think Tempbow is optimistic in what he says about Row 3. What is true is that the first and second cell can be filled 2 ways each, leaving AT MOST 1 possibility for the remaining cells. In fact, quite often (a quarter of the time, in fact), there is NO way to complete the grid. (See my earlier posting for an example.) That's why 288 is correct, rather than 384. I feared that might be the case! So 384 - (1/4 of 384) = 288. Hmmm sounds familiar Terry NZ Back to top upsidedownface Joined: 27 May 2005 Posts: 5 : Location: Leeds Items Posted: Sat May 28, 2005 2:40 pm    Post subject: I think the number is 12. It depends on what you mean by "different". To me it is different if a simple transformation like rotating the numbers or swapping rows or columns common to a box can't make them the same. Due to my personal WebIncompetence I've posted a reply to this topic to the topic "how many false/true Sudoku grids" Back to top tannedblondbloke Joined: 18 Apr 2005 Posts: 2 : Items Posted: Sun Jun 05, 2005 8:40 am    Post subject: Isn't your 12 actually 8 Fraser? Fix the top left block. There are 4 choices for the top right block as you say, and these are essentially the same, so we can pick one arrangement. Then of the 4 arrangements of the bottom left, 2, rather than 1, lead to the columns of top right being the coulumns of the bottom left - in your example below, both 23/41 and 41/23 fail. So I reckon the answer is 24x4x2=192 frazer wrote: However, when the columns of the top right block are the rows of the bottom left block, e.g, 12 34 34 21 23 ** 41 ** then there are no solutions (the 2 and 3 would both have to go in the same cell in the bottom right); otherwise, there is one solution. Of the 16, 4 then have no solution and 12 have one. So I get 24x12=288. Frazer _________________ Tanned Blond Bloke London Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jun 08, 2005 11:50 am    Post subject: If you look only at the unique solutions, there are only two grids: 1234 1234 3412 3421 2143 2143 4321 4312 every other grid can be obtained from one of these two by permutating the digits, swapping rows or columns common to a box, rotating or flipping the whole grid. Back to top coloin Joined: 05 May 2005 Posts: 97 : Items Posted: Fri Jun 10, 2005 10:56 pm    Post subject: 192 - 2 I cant remember how I got the 192 !!!!! I think I "number crunched" it on a sheet of A4 and counted the solutions - I was sure it was right at the time - but I have been wrong ever since ! There must be more than 2 unique solutions though ! Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Sat Jun 11, 2005 12:05 pm    Post subject: Re: 192 - 2 coloin wrote: There must be more than 2 unique solutions though ! There are only 2 really unique solutions, meaning that you can't turn one into the other by simple operations that don't change the underlying structure of the grid. Let's summarize the rules that can be used to convert a grid into an equivalent one: [1] permutate the digits [2] swap two rows or two columns common to a box [3] swap two rows or two columns of boxes [4] rotate or flip the whole grid So let's try building all possible 2x2 grids. Because of [1], we can assume box 1 to be fixed this way: 12** 34** **** **** Row 1 of box 2 can be either 34 or 43. However because of [2] we can assume it to be 34. Column 1 of box 3 can be either 2 4 or 4 2 However because of [2] we can assume the 2 to be on top. This leaves us with 1234 34** 2*** 4*** we can immediately add the missing 4 1234 34** 2*4* 4*** Look at (4,4) now. It can be either 1,2 or 3. But if it is 3, we can apply [1] and swap 2 and 3, getting this grid: 1324 24** 3*4* 4**2 which because of [4] we can flip on the top-left - bottom-right axis, getting again 1234 34** 2*4* 4**2 so we can assume (4,4) to be 1 or 2. If it is 1, the grid can only be completed this way: 1234 3412 2143 4321 If it is 2, the grid can only be completed this way: 1234 3421 2143 4312 which are the only two unique solutions. Back to top bjm Joined: 22 Dec 2005 Posts: 1 : Items Posted: Thu Dec 22, 2005 11:44 pm    Post subject: Hi all, I am interested in devloping my own sudoko program with PHP. Can anyone give me any links to help me get started? Thanks bjm 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 Goto page 1, 2  Next Page 1 of 2   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