No of sudokus, A107739

[David Wilson]

In a sudoku, rows, columns, and boxes must be filled using the same set of 
numbers, which implies that rows, columns and boxes will all have the same 
number of cells.  An immediate consequence is that a sudoku is square.

If, in addition, we require that the box be square, then it will have a 
square number of cells, implying that the rows and columns will as well. 
This means that the sudoku will have side n = k^2 (k >= 1).  This gives a 
natural way to write sudoku sequences, with a(k) referring to sudokus of 
side k^2.

If we allow a box to be rectangular, there will d(n) sudoku formats of side 
n, where d(x) is the number of divisors of x.  For example, a 6 x 6 sudoku 
might have 1 x 6, 2 x 3, 3 x 2, or 6 x 1 boxes, giving d(6) = 4 sudoku 
formats.  If we consider an a x b box equivalent to a b x a box, there are 
ceil(d(n)/2) sudoku formats of side n.  If we further require the boxes to 
be distinct from rows or columns, we are left with ceil(d(n)/2)-1 distinct 
sudoku formats of side n.

These conditions imply that for primes p, q:

    - if n = 1 or n = p, there are no sudoku formats of side n.
    - if n = pq or n = p^3, there is a unique sudoku format of side n.
    - otherwise, there are more than one sudoku formats of side n.

For example, a sudoku of side 7 has no acceptable boxes.  The only 
possiblity, a 1 x 7 box, is equivalent to a row.  A sudoku of side 10 could 
have a 2 x 5 box, this is the only possibility.  A sudoku of side 12 could 
have a 2 x 6 or 3 x 4 box.

The upshot is, if we allow rectangular boxes, there can be any number of 
soduko formats of a given side.  This makes a sequence of statistics on such 
sudokus somewhat complicated.  What would a(12) count, the number of sudokus 
with boxes of size 2 x 6 or of 3 x 4, or both?


----- Original Message ----- 
From: "Shripad M. Garge" <shripad at math.tifr.res.in>
To: "N. J. A. Sloane" <njas at research.att.com>
Cc: <seqfan at ext.jussieu.fr>
Sent: Friday, August 12, 2005 12:39 AM
Subject: Re: No of sudokus, A107739


>
> Dear Sloane,
>
> We do not always have to consider the boxe in Sudoku to be a square. For
> instance, a 6 X 6 sudoku may be constructed with 3 X 2 boxes in it, 2 in
> each rwo and 3 in each column. I have drawn one below. The number of all
> such sudokus, with 3 X 2 boxes or 2 X 3 boxes will be a(6) and the number
> of standard 9 X 9 sudokus will be a(9). The term a(p) will be then 1, as
> there is no possibility for smaller boxes in it.
>
> I can not do the comutations here, but will someone compute this sequence
> and put on OEIS?
>
> Regards,
> Shripad.
>
>
> |---|---|---||---|---|---|
> | 1 | 2 | 3 || 4 | 5 | 6 |
> |---|---|---||---|---|---|
> | 4 | 5 | 6 || 1 | 2 | 3 |
> |---|---|---||---|---|---|
> |---|---|---||---|---|---|
> | 2 | 3 | 1 || 5 | 6 | 4 |
> |---|---|---||---|---|---|
> | 5 | 6 | 4 || 2 | 3 | 1 |
> |---|---|---||---|---|---|
> |---|---|---||---|---|---|
> | 3 | 1 | 2 || 6 | 4 | 5 |
> |---|---|---||---|---|---|
> | 6 | 4 | 5 || 3 | 1 | 2 |
> |---|---|---||---|---|---|
>
>
>
>
>
> On Thu, 11 Aug 2005, N. J. A. Sloane wrote:
>
> ::
> :: Sequence A107739, submitted by Richard McNair, has a long entry,
> :: beginning:
> ::
> :: %I A107739
> :: %S A107739 1,2,288,6670903752021072936960
> :: %N A107739 Number of valid sudokus of order 2n.
> :: %H A107739 Wikipedia, <a 
> href="http://en.wikipedia.org/wiki/Sudoku">Sudoku</a>
> :: ...
> ::
> :: The definition looks wrong to me, but I don't
> :: know anything about these puzzles.  I'm guessing that
> :: the description should really "the number of order n"
> :: and that 6670903752021072936960 is the number of order 3,
> :: which is the standard 9 X 9 puzzle seen in newspapers.
> ::
> :: Can someone who knows about these things confirm this?
> ::
> :: Neil
> ::
>