How many different Shidoku Boards are there?

Question

A Shidoku board is a 4 x 4 grid of numbers where each of the numbers 1-4   
appears exactly once in each row, column, and in each of the four 2 x 2 sub-
grids. How many different shidoku boards are there?"

For the first row there are $4!$ different possibilities. Second row there are $4$ different possibilities. Now for the third row... the bottom-right sub-board row depends on the bottom-left sub-board top row.

Ex:

1 2 3 4

3 4 2 1

4 1 x x

The first $x$ couldn't be 3 or 2 since that would mess up the column and it can't be 4 or 1 since those numbers are already used.

This is the point where I am hitting my mental wall and am not progressing in the problem.

Answer 1

Besides factoring out a factor of $4!$, we can also factor out an additional factor of 4.

First, label the upper-right-hand box as $a,b,c,d$.

a b * *
c d ? ?
& ? ? ?
& ? ? ?

There are of course $4!$ ways to choose the values of a,b,c,d. Now the * signs must be c and d, and we can assume by switching the last two columns that they are in this order. Similarly, the & signs are b and d, and we can switch the last two rows to get them in this order. We've extracted a factor of $4$ by switching the rows and columns in this way, and we're left with

a b c d
c d ? ?
b ? ? ?
d ? ? ?

One can now simply check that

a b c d
c d ? ?
b a ? ?
d c ? ?

has two solutions and

a b c d
c d ? ?
b c ? ?
d a ? ?

has one, thus there are in total

$$ 4! \cdot 4 \cdot (2 + 1) = 288 $$

solutions.

$$ * \quad * \quad * $$

Note 1. This problem is closely related to the the problem of counting Latin squares. The reason this is relevant is that counting the number of Latin Squares of order $n$ is a very difficult in general, having only been calculated up to $n = 11$. Intuitively, one expects the number of Sudoku boards (of any size) to be similarly hard to compute, and sure enough, the problem is quite difficult: see here, here, here, and here for some references.

Note 2. Interestingly, the number of $4 \times 4$ Latin squares is 576, which is exactly twice our above calculation of $288$. In other words, if you try to generate a random "Shidoku" board by just ignoring the boxes and dealing only with rows and columns, there's a $50 \%$ chance you'll end up with a valid board anyway.

Answer 2

Remove a factor of $4!$ by assuming that the first row is 1234.

If we then denote forced values with a dot, we get

1234
a.b.
cde.
....

where the top $2\times 2$ blocks each force one value of the block and the right column and bottom row are forced by the row and column contraints respectively.

Assigning these variables in order, $a \in \{3,4\}, b \in \{1,2\}$ are independent. $c \in \{2,3,4\}\setminus \{a\}$ and $d \in \{1, a\}$ are independent. So we have 16 cases to analyse for legal values of $e$.

Finally there's a consistency check: will the constraints on the bottom-right corner give the same value? (Answer: yes. It's the value which isn't in the first three rows of the right column, which means that it's in each row of the top-left $3 \times 3$ block, which means that it's in each column of that block by consistency, which means that it isn't in the first three columns of the bottom row).

Answer 3

This is just a slight variant of 6005's (old) answer. The number of Shidoku boards is $4!\times2\times2$ times the number of boards of the form

 a b c d
 c d ? ?
 b ? d ?
 d ? ? ?

(That is, the numbers $\{1,2,3,4\}$ can be assigned to the letters {a,b,c,d} in any of $4!$ ways, after which the third and fourth columns can be swapped or not, as can the third and fourth rows.) The main new feature here is the presence of a "d" in the lower right hand quadrant, whose position is forced. Now the "a" in the lower right hand quadrant has $3$ positions it can go in. And for each of these, it's easy to see that the positions of the "b" and "c" are forced, at which point the rest of the unspecified entries (in the upper right and lower left quadrants) are also forced. So the total number of Shidoku boards is $4!\times2\times2\times3=288$.