The New Sudoku Players' Forum

[Bertram]

9! * 72^2 * 2^7 = 2^20 * 3^8 * 5 * 7.

...32 times more than 2^15*3^8*5*7?

Whoops. I wonder how that happened. Thanks for spotting this.

The calculation of the number of essentially different Sudoku grids is very impressive, I'll have to look at it in more detail, now that I have some spare time again.

Bertram

[coloin]

There may well be a new way of working out the number of grids -

- It might just be the sum of each [double shute combination] individual no of [Box 5,6,8&9] solutions which fit in with Box 2 and box 4.

-Edit

It would be if it were possible to calculate it - which it is not - Sorry.

Colin

[coloin]

The number of ways to fill a shute is 9!* 56*216^2 and
Red Ed has published the frequency n of these as the gang of 44
9!* 56*216^2= the sum of all of [n1+n2+n3...........n43+n44]


From Red Ed we know that The Box 2 is one of 8 different combinations [frequencies of 25,8,4,4,1,1,1&1] and we know that Box 3 can have around 33 conbinations. That makes around 8^2 possible combinations of B4/B2 and 33^2 possible combinations of B7/B3.

[dukuso]

Hi Colin,

again I have problems to understand you.
Probably you are referring to earlier messages, but I don't want
to look them up now. (I didn't understand parts of them either...)



>There might even be two equivalent ways of expressing the solution !

what you mean ? Which solution ? How "express" ?

>From:
>The number of ways to fill a shute is 9!* 56*216^2 and

chute, not shute

>Red Ed has published the frequency n of these as the gang of 44
>9!* 56*216^2= the sum of k*[n1+n2+n3...........n43+n44]

sum over k ?

>1. N= the sum of [44^2] of the possible 44*k*n*each of the
> possible 44*k*n * B5*B9 solutions

what's N ?
sum of [44^2] over which summing-index ?


>or
>
>2. N= 9!*[56*216^2]^2 * the sum of each of the 44^2 - B5*B9 solutions.


N is the total number of sudoku-grids ~6.67e21 ?
9!*[56*216^2]^2 is the number of way to fill B1,B2,B3,B4,B7 ?
sum [i,j=1..44] X(i)*X(j) is the number of ways to B5,B9 ?
This depends on B2,B3,B4,B7 of course.
And, it's not an invariant of the 44gang-type.



>From Red Ed we know that The Box 2 is one of 8 different combinations
>[frequencies of 25,8,4,4,1,1,1&1] and we know that Box 3 can have
>around 33 conbinations.

..provided what ? combinations of what ?

>That makes around 8^2 possible combinations
>of B4/B2

..given B1 ?

> and 33^2 possible combinations of B7/B3

given B1,B2 resp. B1,B4 ?


>One would have to analyse each of the 56*216-B2s and the 216-B3s to
>determine their frequecys of the actual pairings.

...to achieve what ? You are looking for another way to compute
the total number of sudoku-grids ? (~6.67e21)

>[May be this is
>is the gang of 44 !]
>
>[I find the working out of the possible solutions of 6 clue
> completion of B5 given B2/B4 quite taxing - but it must be
>relativly easy to programmers]

when the numbers are not so big, you can just backtrack
through the whole sub-problem-space.

If you want to calculate the 6.67e21 by splitting into
B1+B2+B3+B4+B7 and B5+B6+B8+B9 , then yes, I think it
can be done. But we already have enough confirmation
of that number, so it's not so important


Guenter.

[frazer]

In response to coloin, I'm also slightly unsure what you are doing. There is a 44^2 appearing in your messages, which makes me think that you are calculating the total number of grids again. There are indeed 44 classes of B1+B2+B3, as Bertram predicted and Ed confirmed. Consequently, there are 44 classes of B1+B4+B7. I don't believe it follows (and I thought about this quite a bit when trying to simplify the earlier calculations) that there are therefore 44^2 classes of B1+B2+B3+B4+B7, owing to the nature of the reductions we used. (If it were true, it would indeed speed up enormously the calculation of the total number of grids!) I persuaded myself that once B1 was fixed (after fixing B1+B2+B3), we lost a lot of the freedom to make further changes to B1, so this reduced the number of possible operations one can do to B4+B7. Indeed, once B1+B2+B3 is fixed, you have to be very careful that any operations you do to B1+B4+B7 don't mess up what you've already got for B1+B2+B3, and since these overlap in B1, you can't be quite so free as you were. In fact, I was only absolutely sure that we could reduce to 22266 possibilities (rather more than 44!) for B4+B7 to go with the 44 for B1+B2+B3, although this doesn't include all the reductions we eventually found, so this number can be reduced (but will still be in the thousands).

Good luck with your calculation; although the number that Bertram got has since been confirmed by Ed, and then by Guenter, all programmed independently and using slightly different reduction methods, further confirmation with a different method again is always good, although I think now we can be pretty sure that this number is right.

Frazer

[dukuso]

very good Frazer, I understood immediately all what
you wrote :-) (and agree)

Although - I don't think Coloin made that silly error with 44*44 ...

I feel it could be correct and doable but must be properly
formulated first (and motivated)

[coloin]

Thanks very much for bearing with me - Its not easy to explain or understand what some crazed non mathematition is on about !
I wasnt initially trying to calculate the number of grids but it worked out I was. Im not doubting the number at all.

Guenter - You need to look at the numbers Red Ed's list to see what I am talking about. Red Ed multiplyed his final number by 1881169920 [the k] to get the final answer. My use of this numer was incorrect - he used it in the final multiplication. All I was saying was if you had up all the equivilents of the 44 you get all the ways of populating B1B2B3.

[coloin]

Red Ed never said how he generated the 1881169920

Analysis of Red Ed's 44 shows that B3 was by far the more important. Indeed for B2, the first 2 numbers in 43 of the 44 are the same.

I got a low result for Gfroyles 17 grid on B9 [its rearranged] - maybe that figures in how low is the minimum number of clues.

[dukuso]

> Guenter - You need to look at the numbers Red Ed's list to see
> what I am talking about.

where is it ?

...
> xxx oxx ooo
> xxx xox ooo
> xxx xxo ooo
>
> ooo oxx oxx
> ooo xox xox
> ooo xxo xxo
>
> oxx ooo oxx
> xox ooo xox
> xxo ooo xxo
>
> If you complete a grid like this you get only one unique
> solution - every time. Please try and verify this for yourself
> ! If you can find one then my whole theory is bunkum !

here is a counterexample:
5 6 4 0 2 9 0 0 0
2 8 1 7 0 5 0 0 0
3 9 7 4 6 0 0 0 0

0 0 0 0 7 6 0 9 4
0 0 0 9 0 3 1 0 5
0 0 0 1 8 0 6 7 0

0 1 5 0 0 0 0 8 2
8 0 6 0 0 0 4 0 9
9 4 0 0 0 0 5 6 0

[coloin]

Well done. You are good.

We therefore need a little bit more than 6 in each grid ie 7. - But that still wouldnt have solved your grid - how did you work that one out !

If you increase the clues you reduce the number of solutions possible.

We need to include a rule which picks it up - but what ?

Maybe we need to use 4x8 for B1B3B7- and B5. For B6&B8 they need to stay at 6. Actually I did say the 216 in B3 is still 216 when you only use the 6 clues - every 216 box had a unique 6 pattern - the last number in each box/row is predetermined by the whole row. [eventualy - when B2 is "filled"]

It has to work one way or another.

Red Ed's 44 - http://www.shef.ac.uk/~pm1afj/sudoku/ed44.html and back links to Frazer's page.

Thanks for your support.

Colin

[dukuso]

the counterexample was easy to find, I just tried a couple
of grids, deleted your o-cells and the 5th example worked.

For a more detailed list of the 44 see here:
http://forum.enjoysudoku.com/viewtopic.php?t=44&start=255

I haven't checked, but I assume the values coincide with Ed's.

I found it best to split the board into the 3 bands, so I could reuse
the numbers from that list

[coloin]

Yes
Your 44 was quite a calculation - surprising everybody by its precision. However I doubt many understood how you did it - except Red Ed !

Unfortunatly I have to admit defeat on this thread. I have made an wrong internal assumption which holds no validity at all. I was initially looking at the "minimum number of clues" problem.

What I was doing was removing clues from valid sudokus in the first place and I had thought that you can remove clues to that pattern - and it still holds - [The ludicrous "inserting clues and you therefore end up with a valid grid" - you almost aways end up with conflicting numbers !]

Your grid has totally crashed my theory - on both counts - as amazingly Guenter picked a grid which failed to regenerate a unique sudoku - the double pairing in two unfilled boxes - where a diagonal on a partially filled box had these two numbers in it. Therefore two solutions. So that rules out my classification system as well !

Frazer was right - and I apologize for my completly wrong assumptions.

Trying to regenerate the prime in Bertrams number would be an achievement - but not if all we are doing is essentially repeating what we had done before - albeit indirectly.

If you dont mind I will delete my wrong assertions as they are going to help no one.

Thanks again for your help.

I still have thoughts on crossing the grids - to look for grids with a low number of solutions - but I will re-evaluate.

Colin

[coloin]

The number of possible ways to fill B1B2B3B4B7 is 9!*56^2*216^2. = 53094139822080.

Given N [Bertram], this woud mean that each of these ,on average, has 125642939 solutions

Some of B1B2B3B4B7 might have fewer solutions - but it would be difficult to imagine that it would be zero solutions.

Going on from this take any B1B2B3 combination. From our data - it has a minimum 95,000,000 solutions to a full grid .....but B4&B7 give you 56*216^2 = 2612736 possible add-ons. That works out on average 36 solutions for each add-on B4&B7.

There is an error here - but where ?

[dukuso]

The number of possible ways to fill B1B2B3B4B7 is 9!*56^2*216^2. = 53094139822080.

I think, it's 9!*56^2*216^4

[coloin]

The number of possible ways to fill B1B2B3B4B7 is 9!*56^2*216^2. = 53094139822080.

Thanks

This of course should be 9!*56^2*216^4. = 2477160187538964480

this would mean that each of these ,on average, has 2693 solutions - that makes much more sense.