The New Sudoku Players' Forum

[LarryLACa]

The kjell b(n,m) estimate and the related patmax b(k) estimates apply to rectangular nxm (row x cols) or square kxk blocks. Application to a 1x1 block is only valid for a 1x1 grid (latin or sudoku), which, as recently stated, is 'as accurate as it is useless' (nice words )

A latin square is a 'degenerate' form of sudoku with 1xc or rx1 block dimensions and blocks coincident with the rows or columns. Applying the b(n,m) estimates yields

For nxn latin squares, the estimate is

N(n,1) = b(n,1)^1 * b(1,n)^n / n!^n.

Now, b(1,n) is n! and b(n,1) is the number of nxn latin squares.

{--Ignore: wrong usage.. edit 12/13/05
I don't follow the 'b(n,1) = number of latin squares logic'. From the original b(n,m) description{--

This is how: Let X be the space of (nm)x(nm)-grids built by legal sudoku bands, but with no attention put on wether the columns follow the rules of Sudoku. The size of X is b(n,m)^m. Let also Y be the set of grids built by legal stacks with no attention put on the rows, #Y is then b(m,n)^n.

so the first b(n,m) argument (n) is the row size, and the second (m) is the column size, which are associated with the number of (^n) stacks and (^m) bands respectively.

AFAI can see, applying these description to a latin square gives:
b(n,1) is the number of permutations for a stack or column
b(1,n) the number for a band or row
b(1,n) = b(n,1) = n!, yielding an estimate
N (latin nxn) = n!^1 * n!^n / n!^n = n!
which is obviously bad.

I believe the error % is related to the deviation from the symmetry of a square block which has r=c = N(bands) = N(stacks). As the shape of the block diverges from square, N(bands) diverges from N(stacks) which degrades the cross product of the band and stack estimates. The failure for latin squares is the extreme example for the divergence of the exponential (^n, ^m) factors. An increase in grid size (nxm) probably magnifies the error.
end ignore --}
Using:

Let b(r,c) be the number of ways to create the bands of rxc boxes (that is r rows, c columns in each box, r boxes in a band of size rx(c*r).

Yields for a latin square
b(1,n) the number of permutations for a band = row = n!
b(n,1) has 'band' size = nx1*n = nxn, to be filled with boxes=cols, consistent with the latin square constraints, i.e. b(n,1)= N-latin-square :: NLS(n)
Giving
N (latin nxn) = NLS(n)^1 * n!^n / n!^n = NLS(n)
(as kjell stated..)

[kjellfp]

b(n,1) is the number of permutations for a stack or column
b(1,n) the number for a band or row

You're right about b(1,n), but not on b(n,1) which is the number of ways to place nx1-blocks on a band such that the elements on each column (=block) and each row are different. In other words, the number of nxn latin squares.

[LarryLACa]

OK, finally got it. I (wrongly) thought for rx1 and cx1 boxes, the band (or chute or stack) degenerates to the box. Wrong! Let me paraphase the original Kjell definition (substituting r,c for n,m and citing the band size) to confirm the usage:

Let b(r,c) be the number of ways to create the bands of rxc boxes (that is r rows, c columns in each box, r boxes in a band of size rx(c*r).

From which follows for latin squares

b(r,1) be the number of ways to create the bands of rx1 boxes (that is n rows, 1 columns in each box, r boxes in a band of size rxr).
i.e. = N(latin square) restated

I don't think this is the usage applied by tinfoil (Kevin) originally for estimating the total N from the stack estimates, but this definitely works better. Progress!

I think my equivalence transform for mapping PatMax b(k) to KJell b(n,m) still holds. I'll edit my last two posts accordingly.

[Red Ed]

Btw. you should be credited for the number of legal bands in 4x4-sudoku in the Wikipedia M.o.S-page, though you didn't spell it out. It's just 16!*b(4) = 973038982740573238251518542982676480000

I've confirmed this number.

Further calculation easily (but pointlessly, lacking analogues for stacks) gives:

• 4x5 bands: 20! * 5!^12 * 879491145024
• 4x6 bands: 24! * 6!^12 * 677542845061056
• 4x7 bands: 28! * 7!^12 * 563690747238465024

I've added these to Wikipedia's M.o.S. page, along with kjellfp's generic 3xC formula.

[PatmaxDaddy]

In thinking about the 4x3 counting problem I realized that I was doing some unnecessary work in my 3x3 program, so I fixed it and the new times are

Code: Select all

Band Counter   2.9
Permutations   5.3
Band 1         0.5
Gangsters      4.0
Gang lists     0.4
Gang counts   10.2
Band counts    2.2
Grid count    24.6
Overhead       0.1
Total         50.2

I apologize if everyone is now bored with all these timing results.

[kjellfp]

I think my equivalence transform for mapping PatMax b(k) to KJell b(n,m) still holds.

Indeed. My formula was meant to be a generalization of PatmaxDaddy's.

[LarryLACa]

Indeed. My formula was meant to be a generalization of PatmaxDaddy's.

Of course. You said as much in you're original post, and the conection was 'intuitively obvious' (for some). Just my penchant for overstating the obvious, and an attempt to preserve for posterity how we got from A to B when we look back at these posts 6 months from now.

[LarryLACa]

Observations to drawn from the b(n,m) and b(k) based estimates

1) It is ‘simpler’ to estimate square sudoku than rectangular sudoku, since you only need a single band enumeration. (for rectangular b(n,m) estimates we need both band and stack enumerations)

2) the estimate %error is (probably, still unconfirmed) better for square sudoku than rectangular sudoku.

In terms of pushing the estimating envelope, it may be expedient to start thinking about the 5x5 and 6x6 cases.

3) The challenge in band estimating is in the non-terminal (aka middle) blocks. The first and last blocks are simple, the work is in the ‘middle’. Kjell's Nx3 form is an elegant expression of this principle. For the 3xC case, there is only 1 non-terminal block, whose N can be expressed using an M = n choose x derivation see M.o.S Band Enums

4) Guenter, Ed, Kjell, Bill: When you compute the permutations for the 4x middle boxes are you using an (optimized) recursive descent algorithm, T-Classes, or a partitioning expression (like Bell numbers)?. (Obviously I’m still struggling with my homework here ;-) ) Has anyone tried to develop a partitioning expression for sudoku bands?

[kjellfp]

Further calculation easily (but pointlessly, lacking analogues for stacks) gives:

• 4x5 bands: 20! * 5!^12 * 879491145024
• 4x6 bands: 24! * 6!^12 * 677542845061056
• 4x7 bands: 28! * 7!^12 * 563690747238465024

I can confirm all this, and several of the next numbers can be found from a general summation formula:

The number of 4xN bands is (4N)! * N!^12 * R(N) where

Code: Select all


               /
               |
               |   N!^2
R(N) =   Sum   | --------  *
       (a,b,c) | a!*b!*c!
               |
               \

                                                                         \  ^2
        /             ( a )   ( b )   ( c )   ( c )   ( b )   ( a ) \    |
        |     Sum     (   ) * (   ) * (   ) * (   ) * (   ) * (   ) |    |
        |  (k12,k13,  (k12)   (k13)   (k14)   (k23)   (k24)   (k34) |    |
        |   k14,k23,                                                |    |
        \   k24,k34)                                                /    |
                                                                         /

      (a)
where ( ) is the binomial expression, where the outer summand is taken over
      (b)

all a,b,c such that 0<=a,b,c and a+b+c=2N, and where the inner summand is taken
over all k12,k13,k14,k23,k24,k34>=0 such that

k12,k34 <= a  and
k13,k24 <= b  and
k14,k23 <= c  and
k12+k13+k14 = a-k12+k23+k24 = b-k13+c-k23+k34 = c-k14+b-k24+a-k34 = N




NB!! Notice that the entire outer sum is squared.

The expression within the outer summand is symmetric in a,b,c, so it's sufficient to do the counting for 0<=a<=b<=c and multiply with 6, 3 or 1 depending on whether a=b and b=c. It's not obvious from the expression (at least I can't see it) that R(N) becomes an integer, but nevertheless, this happens...

[Red Ed]

Nice. Go on then, let's have the 5xC case ...

[LarryLACa]

I couldn't decipher the last ascii art equation from the BB display: my browser (IE) wraps the display because of the width. I did a copy/paste unformatted into my editor and chose a fixed width to make it readable.

This is much less cryptic, though I'm still knawing on the partitioning constraints.
BTW: the inverse operation works for creating the same.

--edit--
A TeX version of the formula is now available at M.o.S - Bands
with the entire outer sum squared (as later updated!).

[PatmaxDaddy]

Kjellfp pointed out that my band solution counter was rather inefficient. I rewrote it to use his method and got these times for the 3x3 counting:

Code: Select all

Band Counter   0.4
Permutations   4.8
Band 1         0.3
Gangsters      3.6
Gang lists     0.4
Gang counts    0.2
Band counts    2.2
Grid count    24.2
Overhead       0.1
Total         36.1

Having the right method beats clever programming every time.

[kjellfp]

Nice. Go on then, let's have the 5xC case ...

I think I have the RxC case now. Must be proofread and tested. Will put it out later today.

[kjellfp]

Having the right method beats clever programming every time.

Having the right method and clever programming beats only having the right method.

[Pi]

I have created a new thread

http://forum.enjoysudoku.com/viewtopic.php?t=2532

Please can we try to condense this threa into a few pages of relevant information for people who don't want to read 37 pages of posts.

Ideally the results of the many enquiries that go on here.