Counting 3x2 grids by hand

Everything about Sudoku that doesn't fit in one of the other sections

Counting 3x2 grids by hand

Postby kjellfp » Tue Apr 11, 2006 10:28 pm

Since most of the numbers calculated on this site have used computer aid, it's always nice to see if there are some that do not need more than pencil, paper and a head. The complete number of 3x2 Sudoku grids can be done that way, I thought it could be interresting for others to see at least how I did it.

Notice that for 2x2 Sudoku, there is a very nice method mentioned by some others here, which simply says that any Sudoku of the pattern
Code: Select all
XX ..
X. ..

.. X.
.. .X

has one unique solution. Multiplying the number of choices for each clue gives 4*3*2*4*3 = 288 solutions.

3x2 isn't that direct, the total number has a factor of 17 which is not so easy to express as a choice, but it's still doable without any PC.

We have 6 boxes
Code: Select all

There are 10 column configurations for each box, the ways to split up the symbols 1,2,3,4,5,6 into two columns with 1 always in the first column. Those are:
Code: Select all
    14       13       13       13       12
C1: 25   C2: 25   C3: 24   C4: 24   C5: 35
    36       46       56       65       46

    12       12       12       12       12
C6: 34   C7: 34   C8: 43   C9: 43  C10: 53
    56       65       56       65       64

There are 1000 choices for B1|B2|B3 when each is one of the ten configurations above. These bands are grouped into equivalence classes under the action of symbol relabeling, column permutations within each box, and box permutations. The counting is simplified if we can understand these classes, their sizes and band counts. For this, we can always assume B1 to be C1, so we only need to group 100 elements into equivalence classes.

Just to get the different equivalence classes, we can assume B2 to be either C1 or C2, while the choices for B3 is any of C1...C10.

One class is when all boxes are equal, they are all C1. We call this Class 1.

One class is when two (but not three) boxes are equal: (B1,B2,B3) = (C1,C1,C2). We call this Class 2.

The other classes contain the eight cases B1=C1, B2=C2 and B3 is one of C3,C4,C5,C6,C7,C8,C9,C10. We can now see how different operations connect the classes together. We use operations that leave C1 and C2 fixed.

Swapping the symbols 1 and 2 connects C5 with C10, C6 with C9 and C7 with C8. Swapping 5 and 6 connects C3 with C4, C6 with C7 and C8 with C9. The swappings 1-5, 2-6 and 3-4 connects C4 with C5. Altogether we have at most to classes: {C3,C4,C5,C10} and {C6,C7,C8,C9}. These are indeed two different classes, because for (C1,C2,C3) there are two symbols (1 and 2) which are always in the same columns, while for (C1,C2,C6) there is no such pair. We call these classes Class 3 (B3=C3) and Class 4 (B3=C6).

Let E(N) be the size of Class N for N=1,2,3,4.

Class 1 is B1=B2=B3=C1, so E(1)=1.
Class 2 is when two, but not three of B1,B2 and B3 are equal. There are 9 choices when B1=B2=C1, 9 when B1=B3=C1 and 9 when B2=B3=/=C1. So E(2)=27.
Class 3 and 4 are equal in size and contain the remaining 100-1-27 elements, hence E(3)=E(4)=36.

We also need to find the number of bands from each configuration. We can assume that the elements in the first column are sorted, and carry this out as a factor at the end. The number of bands only depends on the equivalence class, call it B(N) for N=1,2,3,4.

The number of bands are the same for (B1,B2,B3) as they are for (B4,B5,B6) - simply because B1 and B4 have the same configuration, etc. So the final number of 3x2 Sudoku grids is

10 * 2 * 2 * 2 * 6 * 6 * SUM { E(N)*B(N)^2 }

where N runs from 1 to 4. The factors are 10 for the choice of B1, 2^3 for the permutations of the columns in each stack, and 6^2 for the permutations of the rows in each band.

B(N) is found by brute force with pencil and paper. We should get B(1)=24, B(2)=8, B(3)=8, B(4)=12. And so the total number of 3x2 Sudoku grids is

10*8*36* (1*24*24 + 27*8*8 + 36*8*8 + 36*12*12) = 28,200,960
Posts: 140
Joined: 04 October 2005

Return to General