
View previous topic :: View next topic 
Author 
Message 
 fractal
 Joined: 24 Apr 2006  Posts: 2  :   Items 

Posted: Mon Apr 24, 2006 6:09 pm Post subject: How many possible 2x2 soduku's? 


How many possible 2x2 soduku's (4x4 grid)? 

Back to top 


 Hydro
 Joined: 05 Feb 2006  Posts: 12  :   Items 

Posted: Mon Apr 24, 2006 9:50 pm Post subject: 


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

Back to top 


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

Posted: Tue Apr 25, 2006 12:11 am Post subject: 


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 


 Hydro
 Joined: 05 Feb 2006  Posts: 12  :   Items 

Posted: Tue Apr 25, 2006 4:23 am Post subject: 


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. 

Back to top 


 frazer
 Joined: 06 May 2005  Posts: 8  :   Items 

Posted: Tue Apr 25, 2006 7:33 am Post subject: 


Actually, the answer was worked out elsewhere on this forum  there are 288 2x2 sudokus. 

Back to top 


 fractal
 Joined: 24 Apr 2006  Posts: 2  :   Items 

Posted: Tue Apr 25, 2006 8:06 am Post subject: 


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

Back to top 


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

Posted: Tue Apr 25, 2006 9:57 pm Post subject: 


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 1234. Then we can enumerate the possibillities for the second row:
2143
4123
2413
3412
4312
2341
3421
4321
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 1234:
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 


 frazer
 Joined: 06 May 2005  Posts: 8  :   Items 

Posted: Wed Apr 26, 2006 2:30 pm Post subject: 


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 


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

Posted: Wed Apr 26, 2006 3:24 pm Post subject: 


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
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 


 serge asselman
 Joined: 14 Jul 2006  Posts: 1  :   Items 


Back to top 


 tpgames
 Joined: 13 Feb 2007  Posts: 7  :   Items 

Posted: Wed Mar 07, 2007 5:54 pm Post subject: 


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.)
Thanks! 

Back to top 


 Pat
 Joined: 06 Sep 2006  Posts: 128  :   Items 

Posted: Wed Mar 14, 2007 11:26 am Post subject: re: 2x2 (24x12=288) 


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 


 tpgames
 Joined: 13 Feb 2007  Posts: 7  :   Items 

Posted: Thu Mar 15, 2007 3:07 pm Post subject: 


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.
Thanks though! (I'll reread that entire thread too after April) 

Back to top 


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

Posted: Fri Mar 28, 2008 4:14 pm Post subject: How many possible minimal 2x2 sudoku puzzles 


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 onetime 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 


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

Posted: Sat Mar 29, 2008 1:19 pm Post subject: 


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 4clues 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 




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
