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 2x2 soduku's?
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
fractal

Joined: 24 Apr 2006
Posts: 2
:

Items
PostPosted: Mon Apr 24, 2006 6:09 pm    Post subject: How many possible 2x2 soduku's? Reply with quote

How many possible 2x2 soduku's (4x4 grid)?
Back to top
View user's profile Send private message
Hydro

Joined: 05 Feb 2006
Posts: 12
:

Items
PostPosted: Mon Apr 24, 2006 9:50 pm    Post subject: Reply with quote

I would probably say 2^(4!), or basically- 16,777,216 - I'm probably wrong, but this seems quite reasonable.
Back to top
View user's profile Send private message
nero

Joined: 22 Mar 2006
Posts: 9
:
Location: Silicon Valley, CA, USA

Items
PostPosted: Tue Apr 25, 2006 12:11 am    Post subject: Reply with quote

Hydro wrote:
I would probably say 2^(4!), or basically- 16,777,216 - I'm probably wrong, but this seems quite reasonable.

How did you arrive at this answer? I don't think it's even close. One row has 4! ways to arrange it. Four rows would have (4!)^4 ways to arrange, them, or 331,776. And that yields far more invalid than valid grids; it doesn't even consider columns or boxes.
Back to top
View user's profile Send private message
Hydro

Joined: 05 Feb 2006
Posts: 12
:

Items
PostPosted: Tue Apr 25, 2006 4:23 am    Post subject: Reply with quote

nero wrote:
Hydro wrote:
I would probably say 2^(4!), or basically- 16,777,216 - I'm probably wrong, but this seems quite reasonable.

How did you arrive at this answer? I don't think it's even close. One row has 4! ways to arrange it. Four rows would have (4!)^4 ways to arrange, them, or 331,776. And that yields far more invalid than valid grids; it doesn't even consider columns or boxes.


Meh, I was close enough - I'm happy. Razz
Back to top
View user's profile Send private message
frazer

Joined: 06 May 2005
Posts: 8
:

Items
PostPosted: Tue Apr 25, 2006 7:33 am    Post subject: Reply with quote

Actually, the answer was worked out elsewhere on this forum - there are 288 2x2 sudokus.
Back to top
View user's profile Send private message
fractal

Joined: 24 Apr 2006
Posts: 2
:

Items
PostPosted: Tue Apr 25, 2006 8:06 am    Post subject: Reply with quote

Let me try
Row1 : 4x3x2x1
Row2: 3x2x1x1
Row3: 2x1x1x1
Row4: 1x1x1x1
So 24x6x2 = 288. Correct?
Back to top
View user's profile Send private message
nero

Joined: 22 Mar 2006
Posts: 9
:
Location: Silicon Valley, CA, USA

Items
PostPosted: Tue Apr 25, 2006 9:57 pm    Post subject: Reply with quote

fractal wrote:
Let me try
Row1 : 4x3x2x1
Row2: 3x2x1x1
Row3: 2x1x1x1
Row4: 1x1x1x1
So 24x6x2 = 288. Correct?


I understand your reasoning, but it's not quite correct. First of all, you're enumerating Latin Squares, not Sudokus. We'll deal with that later, though.

If I follow your reasoning correctly, the first row can be arranged 4! different ways. This is correct. There are four places to put the 1, three to put the 2, two to put the 3, and one remaining for the 4. So far, so good.

Now consider the second row. Since you're restricted by where you placed the numbers in the first row, there are three places to put the 1, two to put the 2, and the 3 and 4 have only one place to go. This reasoning is not correct. Without losing generality, let's say the first row is 1-2-3-4. Then we can enumerate the possibillities for the second row:


    2-1-4-3
    4-1-2-3
    2-4-1-3
    3-4-1-2
    4-3-1-2
    2-3-4-1
    3-4-2-1
    4-3-2-1


This gives us eight possibilities for the second row, not six. Of these, two have four possible third rows and the other six have two possible third rows. The fourth row is fixed in all cases.

To clarify, here is a list of the 20 possible Latin Squares, given the first row being 1-2-3-4:

Code:

1234   1234   1234   1234
2143   2143   2143   2143
3412   4312   3421   4321
4321   3421   4312   3412

1234   1234
4123   4123
3412   2341
2341   3412

1234   1234
2413   2413
3142   4321
4321   3142

1234   1234
3412   3412
2143   4123
4321   2341

1234   1234
4312   4312
2143   3421
3421   2143

1234   1234
2341   2341
4123   3412
3412   4123

1234   1234
3421   3421
2143   4312
4312   2143

1234   1234   1234   1234
4321   4321   4321   4321
2143   3142   2413   3412
3412   2413   3142   2143


Thus, we have (4!) * 20 possible latin squares, or 24*20=480.

Now, only half of these appear to be valid sudokus, because a valid sudoku will be divided into 2x2 squares. Therefore, there are 24*10=240 possible 2x2 sudokus. Fewer, if you don't count rotations, reflections, and row/column swaps.

Which brings us to a stickier question. I've seen claims of the number of possible 3x3 sudokus, though I don't remember the value. I imagine it would be impossible to enumerate them without a computer, and maybe even with one. Is there a better mathematical approach that yields the correct answer?
Back to top
View user's profile Send private message
frazer

Joined: 06 May 2005
Posts: 8
:

Items
PostPosted: Wed Apr 26, 2006 2:30 pm    Post subject: Reply with quote

nero's most recent answer misses 4 possibilities, making 24 Latin squares with top row 1234. There is a ninth possibility for the second row, namely, 3142, which then has two more completions to a full grid. Further, the second row 3412 should have four completions, not two. In total, we get an extra four Latin squares, giving 4!*24=576, and exactly half of these are 2x2 sudoku, giving 288.

The number of essentially different ones, where we treat as the same those coming from rotations, reflections, relabelling and row/column swaps is just 2.

As for 3x3 sudokus, these were indeed enumerated by computer. Indeed, sufficiently many people have done this independently (and agreed with the answer that we first got!) that this number seems certain. The approach is quite mathematical. We listed all possibilities for the top three rows (nearly 10^12), and split them into equivalence classes, two possibilities being equivalent if we could prove that they had the same number of ways to complete to a full grid. Computer work showed that there were just 44 equivalence classes (all of different size); for each, we counted (by computer) the possible ways to complete the grid. Multiplying everything together and adding gives the total. Subsequent methods improved our original calculation by counting the number of ways using further simplifications to count the number of ways to complete these to a full grid, along the lines of our method for the top three rows. These methods have been pushed much further, to count sudoku grids of size 2x3, 2x4, 2x5 and 3x4, although the latter two have not been independently counted. The number of essentially different grids in the 2x3 and 2x4 cases are also known.

I doubt that you could get the 3x3 number without a computer, but that's something you should try to convince yourself!

See http://en.wikipedia.org/wiki/Mathematics_of_Sudoku for more.
Back to top
View user's profile Send private message
nero

Joined: 22 Mar 2006
Posts: 9
:
Location: Silicon Valley, CA, USA

Items
PostPosted: Wed Apr 26, 2006 3:24 pm    Post subject: Reply with quote

frazer wrote:
nero's most recent answer misses 4 possibilities, making 24 Latin squares with top row 1234. There is a ninth possibility for the second row, namely, 3142, which then has two more completions to a full grid. Further, the second row 3412 should have four completions, not two. In total, we get an extra four Latin squares, giving 4!*24=576, and exactly half of these are 2x2 sudoku, giving 288.

That's what I get for trying to do it by hand Confused

Thanks for the detailed response. I see that the answer is 288, but it is only coincidence that it equals 4! * 3! * 2! * 1!. Clearly there appears to be no simple mathematical formula that would extend to the 3x3 case.

Time for me to stop thinking about it now.
Back to top
View user's profile Send private message
serge asselman

Joined: 14 Jul 2006
Posts: 1
:

Items
PostPosted: Fri Jul 14, 2006 9:06 am    Post subject: How many 2x2 sudoku's? Reply with quote

1234 2134 3124 4123
1243 2143 3142 4132

1324 2314 3234 4213
1342 2341 3243 4231

1423 2413 3423 4312
1432 2431 3432 4321

# = 4! = 24

I have made this more visually @ :

http://groups.msn.com/overallesenniks/sudoku.msnw?action=ShowPhoto&PhotoID=275

with these combinations i try to make some 2x2 sudoku's @ :

http://groups.msn.com/overallesenniks/sudoku.msnw?action=ShowPhoto&PhotoID=276

If anyone shares the same interest, you are very welcome to
post me some 2 x 2 solutions to my msn group.

Serge Asselman
student elektronica
Back to top
View user's profile Send private message
tpgames

Joined: 13 Feb 2007
Posts: 7
:

Items
PostPosted: Wed Mar 07, 2007 5:54 pm    Post subject: Reply with quote

I found 40 possible 2x2 sudoku solutions, but I can not come up with the other 248 possibilities. googling it did not come up with a list of all the possibilities either. Yes, I'm doing this by hand, as math at this level is a little beyond me. I flunked P^... in college.

Any one got a link to a list of all 288 possibilites? Thanks!
(no one jumped or commented when I asked for someone to write a JavaScript 2x2 sudoku program using images for my 4 yr. old nephew, so I'm trying to have 288 pages, all with a different sudoku game on it - at least until I figure out Javascript.) Laughing


Thanks! Very Happy
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Wed Mar 14, 2007 11:26 am    Post subject: re: 2x2 (24x12=288) Reply with quote

tpgames wrote:
I found 40 possible 2x2 sudoku solutions, but I can not come up with the other 248 possibilities.

googling it did not come up with a list of all the possibilities either.

Yes, I'm doing this by hand, as math at this level is a little beyond me.

Any one got a link to a list of all 288 possibilites? Thanks!

not the list you've requested, but frazer (2005.May.6) explains the 24x12=288 --
Back to top
View user's profile Send private message Visit poster's website
tpgames

Joined: 13 Feb 2007
Posts: 7
:

Items
PostPosted: Thu Mar 15, 2007 3:07 pm    Post subject: Reply with quote

I read that post earlier, and tried to come up with all 288.

However, I came up with a problem with my idea of making 288 different pages...I don't understand JavaScript well enough to write the code to allow people to choose an image and put it in the box. No matter how, I thought it out, I'd still have that little issue. I'm using code from both a 3x3 and a 2x3 sudoku game to try and learn the code. So far, I've not been able to convert either into a 2x2 sudoku game. I'm going to look at this further after April. I've got too much stuff to do on my site before I can tackle this issue. Rolling Eyes
Thanks though! (I'll reread that entire thread too after April)
Back to top
View user's profile Send private message
mathrec

Joined: 15 Jul 2005
Posts: 10
:
Location: Carlsbad, CA

Items
PostPosted: Fri Mar 28, 2008 4:14 pm    Post subject: How many possible minimal 2x2 sudoku puzzles Reply with quote

The number of filled 2x2 solution grids is 288, and there are only two meaningfully distinct filled grids (distinct under operations of swapping rows or columns of boxes, swapping individual rows or columns, or permuting the number values).

But I'm trying to figure out the number of distinct 2x2 sudoku puzzles. For example, I found the following valid puzzles with the minimum four clues doing a search by hand (and no others that are meaningfully distinct, although this was only a one-time search by hand):

Code:

+--+--+ +--+--+ +--+--+ +--+--+ +--+--+
|1 |  | |1 |  | |1 |  | |12|  | |1 |  |
|  |1 | |  |1 | |2 |1 | |  |  | | 2|  |
+--+--+ +--+--+ +--+--+ +--+--+ +--+--+
|  | 2| |  |2 | |  |3 | |3 |4 | |  | 3|
| 3|  | |3 |  | |  |  | |  |  | |4 |  |
+--+--+ +--+--+ +--+--+ +--+--+ +--+--+
+--+--+ +--+--+ +--+--+ +--+--+
|1 |  | |1 |  | |1 |  | |1 |  |
|  |2 | |  |2 | |  |2 | |  |2 |
+--+--+ +--+--+ +--+--+ +--+--+
|3 |4 | |3 |  | |3 |  | | 3|  |
|  |  | |  |4 | |  | 4| |  | 4|
+--+--+ +--+--+ +--+--+ +--+--+

There are puzzles with up to 15 clues, but I'm only interested in minimal puzzles (where removing any of the clues makes the puzzle have multiple solutions). Does anyone know the answer to this one?
Back to top
View user's profile Send private message Visit poster's website
JPF

Joined: 05 Dec 2005
Posts: 29
:
Location: Paris

Items
PostPosted: Sat Mar 29, 2008 1:19 pm    Post subject: Reply with quote

Properties of 2x2 puzzles have probably already been posted in the players forum, but I can't remember where exactly.

Edit 1: see here
Edit 2 --------------
There are 288 grids ; only 2 are essentially different.

192 are isomorphic to :
Code:
1 2 | 3 4
3 4 | 1 2
----+----
2 3 | 4 1
4 1 | 2 3

96 are isomorphic to:
Code:
1 2 | 3 4
3 4 | 1 2
----+----
2 1 | 4 3
4 3 | 2 1
--------------
I got 13 minimal non isomorphic 4-clues puzzles :

Code:
. . | . .
. . | . 1
----+----
. 1 | . 2
3 . | . .

Code:
. . | . .
. . | . 1
----+----
. 1 | 2 .
. 3 | . .

Code:
. . | . .
. . | . 1
----+----
. 2 | . .
. 3 | . 4

Code:
. . | . .
. . | . 1
----+----
. 2 | . .
. 3 | 2 .

Code:
. . | . .
. . | . 1
----+----
. 2 | . .
3 . | 4 .

Code:
. . | . .
. . | 1 2
----+----
. . | . .
1 3 | . .

Code:
. . | . .
. 1 | . 2
----+----
. . | . .
. 3 | 4 .

Code:
. . | . .
. 1 | . 2
----+----
. . | . .
1 . | 3 .

Code:
. . | . .
. 1 | . 2
----+----
. . | . .
2 . | 3 .

Code:
. . | . .
. 1 | . 2
----+----
. . | . .
3 . | 4 .

Code:
. . | . .
. 1 | . 2
----+----
. . | 3 .
4 . | . .

Code:
. . | . 1
. 1 | . .
----+----
. . | 2 .
3 . | . .

Code:
. . | . 1
. 2 | . .
----+----
. . | 3 .
4 . | . .


The maximum number of clues for minimal puzzles is 6.

Here are minimal puzzles with 5 and 6 clues :
Code:
1 2 | 3 .
. . | . .
----+----
. . | . .
. 3 | 2 .

Code:
1 2 | . .
. . | . .
----+----
2 . | . 3
. 3 | . 1

JPF


Last edited by JPF on Thu Apr 10, 2008 9:55 pm; edited 2 times in total
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
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