2
$\begingroup$
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.

$\endgroup$
  • 1
    $\begingroup$ You may need to split the problem into cases! (renaming numbers as needed may help keep track of all the different cases without them growing to an unmanageable number) $\endgroup$ – Hurkyl Jun 7 '13 at 8:53
  • $\begingroup$ It looks like $4!\cdot4\cdot2\cdot1$ $\endgroup$ – gukoff Jun 7 '13 at 8:54
  • $\begingroup$ @Harold I calculate $4! \cdot 4 \cdot 3$. How did you get your answer? $\endgroup$ – 6005 Jun 7 '13 at 9:46
  • $\begingroup$ Oh, $4!\cdot4\cdot3\cdot1$ of course :) And this is obvious, in fact. $\endgroup$ – gukoff Jun 7 '13 at 9:52
  • 1
    $\begingroup$ Obvious things are often wrong... I didn't check my answer, it just looks like it is right. $\endgroup$ – gukoff Jun 7 '13 at 10:02
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Goos I'm sorry for what seems like a basic observation, but I am not understanding why it is okay to factor a 4! and such. I guess my approach was wrong? $\endgroup$ – Ozera Jun 7 '13 at 12:42
  • $\begingroup$ @Ozera your approach isn't necessarily wrong. The reason I like my approach here is that we were able to factor out $4! \cdot 4$ and then assume that 8 values in the grid were fixed. This reduced the problem to counting just 3 layouts, which is pretty nice. In your approach, you factor out $4!$ at the start, which is nice, but then with the second row you actually have to deal with the $4$ cases you count separately. You ran into a wall because you didn't do cases on this second row. $\endgroup$ – 6005 Jun 7 '13 at 20:04
  • $\begingroup$ @Ozera It's not completely obvious why you can factor out $4!$ and $4$. Basically, we first named whatever symbols happened to be in the top left box as $a,b,c$, and $d$. This works because the four symbols in the top left box are most certainly distinct, and there are $4!$ ways of choosing what $a,b,c$, and $d$ are. Then, observe that (1) in any board, we can switch the last two rows and/or last two columns to get the desired form, (2) given that ** and && are in the order we chose, there are exactly $4$ boards which result in our board once switched. Hence the factor of 4. $\endgroup$ – 6005 Jun 7 '13 at 20:10
  • $\begingroup$ @MarcvanLeeuwen I actually think you're right but for the wrong reason -- I think the expected value of $n$, the number of solutions ignoring boxes, will be $\le 2$, but I'm wrong because it could be strictly less than $2$. $\endgroup$ – 6005 Jun 7 '13 at 20:14
  • $\begingroup$ @MarcvanLeeuwen I've edited. Anyways, if the board were created without regard to boxes, and solved without regard to boxes, there'd be a $50\%$ chance of it ending up correct. So if it is created with regard to boxes, but still solved without regard to boxes, this can only increase the chances of you ending up having the correct boxes. Hence, expected value of $n$ is most certainly $\le 2$. $\endgroup$ – 6005 Jun 7 '13 at 20:19
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I hope you mean that out of the needed answer of $4!\cdot 12=4\cdot 4\cdot 3\cdot 2$; $16=4\cdot 4$ is accounted by the possible values of $e$. But, the top row can have $4!$ values. But, this makes the total choices of filling sudoku as $16\cdot 4!$. Please guide. $\endgroup$ – jiten Oct 2 '18 at 11:59
  • 1
    $\begingroup$ @jiten, I don't entirely understand your comment, but I think you've missed the meaning of to analyse for legal values. $\endgroup$ – Peter Taylor Oct 2 '18 at 12:43
  • $\begingroup$ So you mean that the $4$ invalid values for bottom-left & top-right blocks for a given configuration of the top-left $2*2$ block are filtered out from the possible $16$ choices of $e$. These $4$ invalid configurations are also shown at : theory.tifr.res.in/~sgupta/sudoku/shidoku.html. $\endgroup$ – jiten Oct 2 '18 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.