The New Sudoku Players' Forum

[Red Ed]

What happens to the numbers when we consider Sudoku X - the version where the main diagonal and anti-diagonal must also contain the digits once each.

I claimed a while back that there are 55613393399531520 Sudoku X grids, but AFAIK this remains unconfirmed.

[PatmaxDaddy]

My program can be found at www.tidewater.net/~bsilver/sudoku/ In this directory is the C++ code and a file containing the output from the program. Questions/comments are welcome.

Bill

[gfroyle]

that's not really interesting for a mathematician ?!

Depends where you're coming from...

The question "how many Sudoku grids are there" is just the same as the question "how many 9-colourings does a certain 81-vertex graph have". Adding the X just changes the graph that we are asking about....

You may argue that the normal Sudoku graph is regular and vertex-transitive and therefore "more interesting" than the variants.. this is probably true, but it doesn't make the variants entirely non-interesting.

But in general, if a graph arises in a natural way from human activity, then it automatically becomes more interesting - for example, there is a vast amount of work that has been stimulated by the "web graph" which a priori is not at all mathematically interesting.

Cheers

Gordon

[dukuso]

however..

latin squares are interesting for mathematicians,
while latin squares with all symbols different in the two main diagonals
are not. You won't find many papers dealing with them.

Also, latin cubes are somehow interesting too, although to
a smaller degree. This small interest is already a bit astonishing,
considering that physics is 3-dimensional.

Now, sudokus could be considered as 4-dimensional
latin-similar-structures, see:
http://forum.enjoysudoku.com/viewtopic.php?t=2151

so, I argue that they are somehow mathematically interesting.
Sudoku-problems are also similar to QCP-problems
for programming. (while presumably X-sudoku is
different due to fewer symmetries, I'm not sure)

[gfroyle]

latin squares are interesting for mathematicians,
while latin squares with all symbols different in the two main diagonals
are not. You won't find many papers dealing with them.

But I don't think of Sudokus as Latin squares.. I think of them as partially coloured graphs.

So if the variant Sudokus are not interesting Latin squares then that might discourage a latin-square-theorist, but they may still be of interest to a graph theorist...

I do agree with you that they are less natural, and hence potentially less interesting, or even less interesting to mathematicians on average, but I also reserve the right to be interested in any darn graph that I choose . Besides I'm not saying that YOU should be interested in Sudoku X (or the other variants), just that *I* might be interested in it.

Cheers

Gordon

[dukuso]

>dukuso wrote:
>
>> latin squares are interesting for mathematicians,
>> while latin squares with all symbols different in the two main diagonals
>> are not. You won't find many papers dealing with them.
>
>
>
>But I don't think of Sudokus as Latin squares.. I think of them
>as partially coloured graphs.

most mathematicians won't think of QWHs (quasigroup with hole)
or QCPs (quasigroup completion problem) as just
"partially coloured graphs".
Certainly some special colored graphs. And with applications
similar to scheduling problems etc.


>So if the variant Sudokus are not interesting Latin squares then
>that might discourage a latin-square-theorist, but they may still
>be of interest to a graph theorist...

yes, that may happen. (does it ?)

>I do agree with you that they are less natural, and hence
>potentially less interesting, or even less interesting to

hmm, seems that you are talking about the X-sudokus here
while I thought you meant sudokus vs. QWHs

>mathematicians on average, but I also reserve the right
>to be interested in any darn graph that I choose .

yes, you can examine whatever you want, of course.
BTW. what's a darn graph ? ;-)

>Besides I'm not saying that YOU should be interested
>in Sudoku X (or the other variants), just that *I* might
>be interested in it.

why do you think, you might be interested in them (as a graph) ?
It has fewer symmetries and properties hard to specify
just from a graphtheory POV.
I suggest you should be interested in 3dokus instead.

>Cheers
>Gordon


Cheers
Guenter

[LarryLACa]

Given the recent reparte, this post is a little dry. The saga ends in questions about numerical accuracy. Please bear with my rambling.

Suffering from my usual sophomoric enthusiasm (euphemism for naivity), I tried to write a routine to convert the number of Sudoku solutions expressed as 0x20a7b8c11b3000 * 9! * 2 to a decimal (string). I got close, but stumbled onto/over numerical accuracy issues. This bit of LongMult hackery (compatible with Ed’s T-class ct[] generator usage)

Code: Select all

#include <stdio.h>
#include <math.h>
#define FBASE 1000000000.0
char * longmult(unsigned int ilong[], unsigned int n) {
double fa, fb;
static char  prod[30] = "123456789";

printf("*subtot 0x : %07x%07x\n",ilong[1],ilong[0]);
fa = ilong[1];
fa = fa* (2<<27);
fa += ilong[0];
printf("*subtot dbl: %020.0f\n", fa );

fb=floor(fa/FBASE);      /* like >> base 10 */
fa=fmod(fa, FBASE);      /* like << base 10 */
printf("*subtot fab: %011.0f,%09.0f\n",  fb, fa);

fa = fa * n;
fb = fb * n + fa/FBASE;
fa = fmod(fa, FBASE);
printf("*total fab : %.0f,%09.0f, n=%d\n",  fb, fa, n);

sprintf(prod, "%.0f%09.0f", fb, fa );  /* format width must match FBASE */
printf("*longmult  : %s\n", prod);
return prod;
}

produces, when called as longmult(ct, (unsigned int)362880*2),
  with the final ct[] result:
*subtot 0x : 20a7b8c11b3000
*subtot dbl: 00009191611210346496
*subtot fab: 00009191611,210346496
*total fab : 6670903752021,072936960, n=725760
*longmult  : 6670903752021072936960


converts 0x20a7b8c11b3000 to 9191611210346496 accurately and for the 9!*2 factor produces the right answer: 6670903752021072936960. But I was just lucky (numerically). While testing/exploring the coding I ran into numerical limits for both
- the ct[] to double conversion (when adding ct[0] to ct[1}<<28) and
- the two segment double multiply

Double addition is (apparently) only accurate to ~15 decimal digits. The 16 digit value for 9191611210346496, just happened to be exact. (For 16 digits, err ~ +/- 1, with ~10%? accurate). The two segment multiply suffers similarly.

The algorithm used is (I believe) algebraically correct, but limited by the numerical accuracy of the platform and software. Looking at the code you can’t tell they will fail. Running the code doesn’t throw exceptions for inaccuracies. You have to find them by handcheck (using alternate tools) or ‘independent verification’. This leaves me with the following questions/requests:

What are the limits of float (double) accuracy? Obviously depends on platform/compiler. What’s the spec Pentium class machines? How does this depend on compiler (options)?

Can someone point me to some trusted BigNum algorithms or C/C++ code for the likes of my LongMult kludge above?

The PatMax/Guenter/Ed programs are coming up with consistent numbers. Since consistent and implemented independently, I trust they’re correct (both in results and implementation). How (numerically) sensitive is this (counting) code to extension to bigger problems? There is obviously years of experience hidden in the code design, not immediately obvious, that can break when extended inappropriately.

P.S. I haven't looked at the Patmax code yet.

[PatmaxDaddy]

If I remember correctly, a standard double (there is a standard, published by IEEE) is 64 bits with a sign bit, 11 bits of exponent, and 52 bits of mantissa, plus a so-called "hidden bit" that one gets because the numbers are normalized. This gives 53 effective bits of mantissa. This is exactly how many are needed by our favorite number, because it is 73 bits long but it's prime factorization has 2^20, so the least significant 20 bits aren't needed in a floating point representation, leaving 53 bits!

I have very comprehensive unlimited-precision integer and rational arithmetic classes written in C++. They are fairly efficient, but I imagine that professionally-written packages might be better. I've used them to calculate pi to 100,000 decimal places, for example, but nothing that could compete with people who really like to do that sort of thing.

The program I just made available uses my bignum class just at the very end, to print out a result, and is not needed other than that. I haven't made the bignum source publically available, but I'm considering doing so. Right now everything runs under Microsoft Visual C++, and some twealing might be necessary to make it run under other C++ systems. Is there any interest in this code? This community doesn't seem to be big on C++.

[dukuso]

I at least am not big on C++.
Also I can't compile your program with gcc3.2,
it's long and complicated so I postponed reading it...

[PatmaxDaddy]

Back on April 22 someone posted an estimate for the 3x3 problem: 6.6571e21, a very good estimate. I came up with the same method and same result independently a while back, but since it was already known I never posted anything about it. I just tried the same thing for 4x4, and got an estimate of 5.96e98. As far as I can tell, the last discussion of an estimate for 4x4 was back on Oct 11, and the value was 1e107. This is also what Wikipedia has for this estimate. I'll describe the method and result in more detail soon, but right now I'm tired and need to go to bed. But before I write more, I thought it wise to solicit comments. Perhaps this is already known, or known to be bogus.

[dukuso]

this 1e107 is unconfirmed AFAIK and I've become a bit unsure
after some other errors...

I might also reformulate the method
and the calculations in an extra post
so everyone can redo it.

But I have some other priorities and it's not all that easy
for me, it requires some time to rethink, search for the
old files etc.

you should have posted on Oct.11, then it had been
much easier to remember and check the calculations

[PatmaxDaddy]

...it's long and complicated so I postponed reading it...

A good way to read the program is: 1) Read the general comments at the beginning; 2) Skip the classes and read the main program, which is less than 100 lines of code (not counting the stuff at the end that prints out the results); 3) When you come to the use of a class object that you want to understand, just read the public interface. For example, the Gangster class is fairly complex, but its public interface has just two functions and a constructor (and two more functions that just print diagnostics). You don't need to undersatnd any of the private data or functions, or any of the implementation, to understand how the main program uses the class. This is the value of object-oriented encapsulation. 4) Finally, read the class implementation for those that you want to understand.

you should have posted on Oct.11, then it had been
much easier to remember and check the calculations.

I only just got the 5.96e98 result last night.

[LarryLACa]

If I remember correctly, a standard double (there is a standard, published by IEEE) is 64 bits with a sign bit, 11 bits of exponent, and 52 bits of mantissa, plus a so-called "hidden bit" that one gets because the numbers are normalized. This gives 53 effective bits of mantissa. This is exactly how many are needed by our favorite number, because it is 73 bits long but it's prime factorization has 2^20, so the least significant 20 bits aren't needed in a floating point representation, leaving 53 bits!

I thought we might be close the the edge, but this is too close. Even if our favorite 6.67e21 number can be represented accurately, the operations during it's construction will pick up noise in the low digits. Also even when the operations involve 2^20 factors there are problems. This code for the final total (subtot * 9! * 2), which must also have an internal 2^20 factor, mangles the last 3 digits:

Code: Select all

doube d=9191611210346496.0
printf("total = %f.2\n", d*725760);
shows     > 6670903752021072937000.00
should be > 6670903752021072936960

which is the error which started me down this path.

The T-Class enumeration .cpp code has a little bigger margin of safety. All the summands are relative to a factor of
9! 6^4, somewhat bigger than the 9!*2 example above. The external
9! 6^4 factor = 2^11 * 229635 < 2^29
So relative to the final sum with 73 bits, that leaves (73-29) = 44 bits for the sum and summand accuracy, which is OK, but only by a factor of ~2^8 < 10^3, which around here isn't much.

I think we're going to need some BigNum boots for wading through deeper muck.

Thanks for the insight
Larry

[Red Ed]

This code for the final total (subtot * 9! * 2), which must also have an internal 2^20 factor, mangles the last 3 digits:
<...snip...>

But (in case anyone cares) this doesn't:

Code: Select all

#include <stdio.h>

#define ADDTERM(A) for(j=k=0;j<22;j++){k=(A[j]+=term[j]+k)/10;A[j]%=10;}
#define MULTCT(C)  k=(ct[C]=ct[C]*(i+(i==1))+k)>>28; ct[C]&=0xfffffff;

int main(void) {
  int ct[3] = { 0x11b3000/*lo*/, 0x20a7b8c/*mid*/, 0/*hi*/ };
  int sum[22] = {0}, term[22] = {1};
  int i, j, k;

  for (i=1,k=0; i<=9; i++) { MULTCT(0); MULTCT(1); MULTCT(2); }
  for (i=0; i<73; i++) {
    if (ct[i/28] & 1<<i%28) ADDTERM(sum);
    ADDTERM(term);
  }
  for (j=21; j>=0; j--) printf("%d",sum[j]); printf("\n");

  return 0;
}

[gfroyle]

Can someone point me to some trusted BigNum algorithms or C/C++ code for the likes of my LongMult kludge above?

GMP is what you should use for arbitrary precision arithmetic...

Here is your program using GMP

Code: Select all

#include <gmp.h>
#include <stdio.h>

int
main(int argc, char **argv) {

  char *str = "0x20a7b8c11b3000";
  mpz_t total;

  mpz_set_str(total,str,0);

  mpz_mul_ui(total,total,(unsigned long int)(362880*2));

  gmp_printf("The number of standard Sudokus is %Zd\n",total);

}


Brief explanation:

mpz_t is the type for an arbitrary precision integer (hence the Z)
mpz_set_str initializes it to the value contained in a string
mpz_mul_ui multiplies an mpz_t by an unsigned long integer
gmp_printf prints it all out

(Syntax is a bit funny, but in general the first argument is the destination of the result, and the others are the arguments of the function.)

www.swox.com is the place to get GMP, and it is free and open-source.

Linux and Mac OS X users can just compile GMP directly from source, but Windows users will need cygwin or something else that adds Unix tools to Windows.

Cheers

gordon