The New Sudoku Players' Forum

[kjellfp]

When I think about it: The 4xC formula maybe isn't O(C^5), but a polynomial order of a more higher degree. That is because binomials are involved, and their calculation is linear on their parameters when the numbers start to grow.

[PatmaxDaddy]

When I think about it: The 4xC formula maybe isn't O(C^5), but a polynomial order of a more higher degree. That is because binomials are involved, and their calculation is linear on their parameters when the numbers start to grow.

But all of the binomials (n, k), 0<=k<=n<=2C, can be precomputed in O(C^2), and then just looked up in the inner loop, so I think it's still O(C^5).

[kjellfp]

But all of the binomials (n, k), 0<=k<=n<=2C, can be precomputed in O(C^2), and then just looked up in the inner loop, so I think it's still O(C^5).

You're right, I surrender. O(C^5).

[PatmaxDaddy]

Kjell: Amazing work on the RxC method. It's going to take me (and I assume everyone else) a while to digest everything you've posted, and explore the new opportunities that this opens. I'm definitely going to implement a general RxC band 1 counter based on your method, but that will be quite a while. I imagine that you are working on it too, and are way ahead.

I now completely understand the 4xC formula, and I believe that it is correct for all C. I think I'd like to write a proof and post it on the new RxC topic that you've created. I think a proof would serve to explain how the formula works, and would be a good stepping stone to understanding the general method. I certainly wouldn't even try getting my tiny mind around the general method until I had mastered 4xC. If you are planning to do something similar, I'll galdly defer to you.

I'm beginning to wonder if your method really is exponential in R, or is instead much faster. You seem to be using a method that repeatedly divides the band in half, and these methods usually lead to some sort of N*log(N) behavior (sorting and FFT are examples). Right now I have no idea how it will turn out, but it will be interesting to see.

[kjellfp]

Unforunately, I still think the process is exponential in R. The problem is the number of ways to break up a band. This comes from a mapping a:E->N where N are the natural numbers, and E is the set of all size L subsets of {1...R} (L is the number of boxes in the subband before breaking).

The size of E is (R ch L), and despite the different constraints on the choice for a, I still think the number of choices is exponential in R. I don't know if low values for C might slow this down so much that it's still possible to do Rx1-band counting, though RxC quickly becomes out of reach as C grows.

And if we could do Rx1-counting for several values of R, don't forget that this is just giving the number of Latin squares of size RxR, which is an unsolved problem for R>=12...

I'm trying to write a 5xC-program now. Maybe an RxC-code generator is something to look at later, but I also think that modifying the RxC-code to produce the (R+1)xC-code is relatively simple, and there aren't that many values for R that are doable anyway...

[PatmaxDaddy]

I took the liberty of changing it to "No" on Wikipedia. After all, the fact that the values concide with those done by others for C<=7 is more a confirmation of these explicit examples than a mathematical proof for the formula itself. There is a difference between confirming a formula and confirming a number. The first is logic, the second a calculation.

I changed it back to "Yes", with a link to the proof I posted. Of course someone should probably read the proof and confirm that it is correct.

[SianKJones31]

I'm having a little trouble confirming 3X2 can anyone confirm these results and explain where 8+64+8 = 80 ways?

http://benambra.org/benambra/?q=node/313#comment-387

Also does anyone have a copy of the calculations for 3XN in word format so that I can distinguish powers from multiples? I can't seem to get the numbers to work as I think they are now.

Thanks

Sian
SianKJones@hotmail.com

[kjellfp]

I agree on the 8+64+8=80 argument, but the final number of 3x2-grids given is wrong.

If box A1 is 123/456, there are 80 choices for A2. If we first assume that the elements in each column in A2 are sorted, what do we have? There is one way to put both 1 and 2 on the second column. There are 4 ways to put 1 on the second and 2 on the third, and another 4 ways to do the opposite. And finally 1 way to put 1 and 2 both in the third column. That gives 1+8+1. Then there are 2^3=8 ways to choose the order of elements in each column, and so we have 8+64+8=80 choices for A2.

It's correct also that B2 can always be chosen in 4 ways when A1, B1 and A2 is chosen. It's also correct that B2 as the last box can be chosen in either 0 or 4 ways. But the two cases do not contribute equally, and that's where the final clame about 33.177.600 solutions fails. The correct answer is 28.200.960.

I don't think I understand your question about 3xN. If you mean the complete grid count, the answers for N=1, 2 and 3 is 12, 28200960 and 6670903752021072936960. For N>=4 it's unknown.

[SianKJones31]

Thanks so much for you help, that really does help.

With the 3xN it can be seen on this page:
http://forum.enjoysudoku.com/viewtopic.php?t=44&start=412

I can't understand what the formular for R and for M actually are.

Thanks

Sian

[SianKJones31]

Given that the first cell is labelled canonically that is:

1 2 3
4 5 6





The number of RoDoku can be reduced by a factor of 6!.

The number of combinations that can be formed in the second half of the band are fixed by the three numbers in the first column.
{1,2,3} must be followed by {4,5,6} in some order (3! ways)
{4,5,6} must be followed by {1,2,3} in some order (3! ways)

That is 3!2 x 6! Combinations across the top row = 25920

The first stack is independent of the (1,2)mg in the ways mentioned above. As such the number of combinations down the first stack can be seen to have the following combinations.

If (1,1)mg is in canonical form, then there is one way to put both 1 and 2 on the second column. There are 4 ways to put 1 on the second and 2 on the third, and another 4 ways to do the opposite. And finally 1 way to put 1 and 2 both in the third column. That gives 1+8+1. Then there are 23=8 ways to choose the order of elements in each column, and so we have 8+64+8=80 choices for (1,2)mg.

It's correct also that (1,3)mg can always be chosen in 4 ways when (1,1)mg, (2,1)mg and (1,2)mg is chosen.

....

[SianKJones31]

My god this topic is getting jammed up, wouldn't it be a great idea to split topics up so that they can be more easily found?

Anyway my question is what is R? What is M? Is there anyone who can help? I'm so lost.

Thanks

Sian

[tinfoil]

WOW.
I was away from this forum for several months, once the math got way out of my league. You guys have been making some interesting progress.

I was fascinated by the 'Mathematics of Soduku' wiki article, and was VERY surprised to see my speculation last April, wrapped in some impressive math, still has some interest today (although you guys are giving me WAY too much credit for it). My name does not belong aside the others there.

I would concur with the previous poster that this thread is 'over the top' by now. It would be great if the divergent topics were summarized into their own threads, and an 'index' thread created to have a 'one-stop' set of links (perhaps in the wiki article?) for us mere mortals trying to follow along.


Kevin Kilfoil

[coloin]

Greetings PatmaxDaddy and kjellfp

As a "mere mortal" I have been trying to follow this thread and I can see the difficulty that many will have experienced with a thread of this length......and I have just looked at Wipekedia ! http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

Suffice to say

Code: Select all

The number of grids has been calculated for the following grids
 
2×2 288
2×3 28200960
2×4 29136487207403520 
2×5 1903816047972624930994913280000   
3×3 6670903752021072936960 = c. 6.7×1021


Code: Select all

We have reliable estimations for

3×4 unknown, estimated c. 8.1064×10^46 Pettersen n/a
3×5 unknown, estimated c. 3.5086×10^84 Silver n/a
4×4 unknown, estimated c. 5.9584×10^98 Silver n/a
4×5 unknown, estimated c. 3.1764×10^175 Silver n/a
5×5 unknown, estimated c. 4.3648×10^308 Silver/Pettersen n/a


You have now worked out a formula for the 3xC and 4xC and now the 5x5 and 5x6 bands. I presume this relates to the first row of boxes.

A long time ago.............before Bertram calculated 6.7×10^21, various others were attempting to work it out long hand ! Estimations at the time needed were in years.

But there was a Monte Carlo estimation [unreferenced] which actually gave a very accurate result. Interestingly it is on page 2 of this thread [!]

I have heard of someone using a Monte Carlo algorithm on a supercomputer for 20 days and coming up with an answer in the region of 6x10^21

As I understood someone worked out the average number of grid solutions from 25 different B1B5B9 grid fillings from

Code: Select all

xxx......
xxx......
xxx......
...xxx...
...xxx...
...xxx...
......xxx
......xxx
......xxx

and multiplied the result by [9!]^3

The thought of working out the 4x4 horrified many....and still does !

Im guessing that the large number of solutions precludes this approximation......so how near to an exact count for the 4x4 will we get. ?

Regards

[DrZ]

Sorry, folks, I'm new to this. I meant to enter the following post in this thread:

http://forum.enjoysudoku.com/viewtopic.php?t=2984&sid=a66541aa4746314d3a2cf60757147c30

It's a straightforward proof that the smallest possible number of
initial clues is 17.

Dr. Brandon Zeidler

[melodyaya]

i am doing a project on possibility of answers
and i want more information,can anyone give me more reference?
thank you