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 relabel 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 topleft  bottomright 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 


