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   

2x2 / 16 grids mathematics of - am i right ?
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Thu May 05, 2005 9:11 pm    Post subject: 2x2 / 16 grids mathematics of - am i right ? Reply with quote

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

Joined: 18 Apr 2005
Posts: 22
:

Items
PostPosted: Fri May 06, 2005 12:12 pm    Post subject: Re: 2x2 / 16 grids mathematics of - am i right ? Reply with quote

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

Joined: 06 May 2005
Posts: 8
:

Items
PostPosted: Fri May 06, 2005 2:24 pm    Post subject: Reply with quote

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

Joined: 26 Apr 2005
Posts: 18
:

Items
PostPosted: Fri May 06, 2005 5:11 pm    Post subject: Reply with quote

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

Joined: 06 May 2005
Posts: 8
:

Items
PostPosted: Fri May 06, 2005 6:08 pm    Post subject: Reply with quote

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

Joined: 26 Apr 2005
Posts: 18
:

Items
PostPosted: Fri May 06, 2005 6:23 pm    Post subject: Reply with quote

I'm sorry, 288 is correct... I made a typo...
Back to top
View user's profile Send private message
Tempbow

Joined: 18 Apr 2005
Posts: 22
:

Items
PostPosted: Fri May 06, 2005 9:25 pm    Post subject: Reply with quote

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

Joined: 06 May 2005
Posts: 8
:

Items
PostPosted: Fri May 06, 2005 10:09 pm    Post subject: Reply with quote

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

Joined: 18 Apr 2005
Posts: 22
:

Items
PostPosted: Fri May 06, 2005 10:50 pm    Post subject: Reply with quote

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! Rolling Eyes
So 384 - (1/4 of 384) = 288. Hmmm sounds familiar Wink

Terry NZ
Back to top
View user's profile Send private message
upsidedownface

Joined: 27 May 2005
Posts: 5
:
Location: Leeds

Items
PostPosted: Sat May 28, 2005 2:40 pm    Post subject: Reply with quote

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

Joined: 18 Apr 2005
Posts: 2
:

Items
PostPosted: Sun Jun 05, 2005 8:40 am    Post subject: Reply with quote

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

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Wed Jun 08, 2005 11:50 am    Post subject: Reply with quote

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

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Fri Jun 10, 2005 10:56 pm    Post subject: 192 - 2 Reply with quote

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

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Sat Jun 11, 2005 12:05 pm    Post subject: Re: 192 - 2 Reply with quote

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

Joined: 22 Dec 2005
Posts: 1
:

Items
PostPosted: Thu Dec 22, 2005 11:44 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
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