The New Sudoku Players' Forum

[ab]

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

I think this is what you're looking for:
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_Sudoku_solutions
it was posted a couple of messages before yours in this very thread!

[kaspar]

Hey all,

we have created a sudoku-counter that enumerates using graph isomorphism. It prints out the same result for 5x2. Can we now toggle the "verified"-entry for that gridsize on the wikipedia-page? ;)

Cheers
Kaspar, Matthias & Lars

btw. it took 124000 seconds on a Pentium4 3ghz...

[dukuso]

have they been counted meanwhile ?

[Isuru]

If you turn a sudoku 90,180 and 270 degrees you get a sudoku with different numbers. But they are the same. So I think there are only a quarter (a bit more than a quarter) of the accepted number.

[Red Ed]

Hello, Isuru. You can do more than just rotate: you can relabel the digits (e.g. replace each D by 10 minus D), swap rows/columns (up to a point), rotate the grid etc. and what you're left with will still be a valid sudoku solution. Taking into account all of these validity-preserving transformations gives 5472730538 "essentially-different" grids.

[Addlan]

If one considers a 4*4 sudoku
|---------------------|
| * * | * * |
| * * | * * |
|----------|--------- |
| * * | * * |
| * * | * * |
|---------------------|

To remove any tranditional permutations, one got
|---------------------|
| 1 2 | 3 4 |
| 2 * | * * |
|----------|--------- |
| 3 * | * * |
| 4 * | * * |
|---------------------|

i.e. all 4*4 sudokus can be transformed into the above form.

There are 4 possible variations:

|--------No1---------|
| 1 2 | 3 4 |
| 2 1 | 4 3 |
|----------|--------- |
| 3 4 | 1 2 |
| 4 3 | 2 1 |
|---------------------|

|--------No2---------|
| 1 2 | 3 4 |
| 2 1 | 4 3 |
|----------|--------- |
| 3 4 | 2 1 |
| 4 3 | 1 2 |
|---------------------|

|--------No3---------|
| 1 2 | 3 4 |
| 2 3 | 4 1 |
|----------|--------- |
| 3 4 | 1 2 |
| 4 1 | 2 3 |
|---------------------|

|--------No4---------|
| 1 2 | 3 4 |
| 2 4 | 1 3 |
|----------|--------- |
| 3 1 | 4 2 |
| 4 3 | 2 1 |
|---------------------|

No2 can be transformed to No1 by a local permutation/chain, i.e. swapping numbers marked with *.

|------Permu1------|
| 1 2 | 3 4 |
| 2 1 | 4 3 |
|----------|--------- |
| 3 4 | * * |
| 4 3 | * * |
|---------------------|

No3 can be transformed to No1 by the following local permutation/chain,

|------Permu2------|
| 1 2 | 3 4 |
| 2 * | 4 * |
|----------|--------- |
| 3 4 | 1 2 |
| 4 * | 2 * |
|---------------------|

No4 can be transformed to No1 by the following local permutation/chain,

|------Permu2------|
| 1 2 | 3 4 |
| 2 * | * 3 |
|----------|--------- |
| 3 * | * 2 |
| 4 3 | 2 1 |
|---------------------|

In order to fix the local chains, at least another two numbers are needed to be shared by the three chains.

In order to fix the global permutation, one needs at least 5 numbers, e.g. as below
|---------------------|
| 1 2 | 3 * |
| 2 * | * * |
|----------|--------- |
| 3 * | * * |
| * * | * * |
|---------------------|

Therefore, at least 7 clues are needed to fix all the permutations. All 4*4 sudokus can be transformed into each other through global and local permutations as above.

The situation of 9*9 sudokus could be similar as the 4*4 sudokus.

[Red Ed]

No, four clues are sufficient.

[Addlan]

Right, I was wrong.

[dtal]

Josh - what did your probability grid look like? I followed the same idea, populating from left to right, line by line the number of possibilities for each cell - the first line looks like this (no disputing this):

9 8 7 6 5 4 3 2 1

But I think the next line though looks like this:

6 5 4 6 5 4 3 2 1

This is because the the 1st box all ready has three numbers on the first line. Following the same logic, line 3 looks like this:

3 2 1 3 2 1 3 2 1

This leads to a possibility grid looking like this:

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

Multiplying these out you get around 1.74 x 10 ^ 33

You have an error in your grid. The grid should be:

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

The final result of combinations is: 15,284,122,844,890,200,000,000,000,000,000
or
1.52841E+31
If you like to see the proof then write me to:
dtalpk@gmail.com

Have a nice day,
User dtal

[Ton Smeets]

More on estimating N(4x4):

Back on April 22 "tinfoil" gave a method for estimating N(3x3) that produced 6.6571e21, which, although it wasn't known at the time, is only about 0.2% off of the correct value. This method easily generalizes to any size Sudoku grid:

Code: Select all

                  2k
              b(k)
N(k x k) = -----------
             2  k(k-2)
           (k )!


where b(k) is the total number of solutions for band 1 when box 1 contians one fixed permutation of symbols.

Nice generalization, this can be used on nxm-sudoku for every n and m, and becomes a generalization of my 3xn-estaimates inhttp://forum.enjoysudoku.com/viewtopic.php?t=44&start=412 andhttp://forum.enjoysudoku.com/viewtopic.php?t=44&start=416. (What a coincidence on the url: 44 and 416... )

In general: Let b(n,m) be the number of ways to create the bands of nxm boxes (that is n rows, m columns in each box, n boxes in a band). To make the formula clearer, I say any band, regardless of symbol permutation in the first box.

Then the estimate of numbers of nxm-sudoku is

Code: Select all

                 m         n
           b(n,m)  * b(m,n)
N(n x m) = -----------------
                    nm
               (nm)!


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.

The nxm-sudoku grids are then the intersection of X and Y. A random x in X and y in Y are identical in a given box with probability (nm)!, and under the assumption that these probabilities are independent for each box, we arrive at the estimate above.

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 [Edit: I have now put you on M.o.S]

The reduction factor (n*n!)^n*n suggest no independence. For including a certain dependence, I tried (n*n! - f(n))^n*n.
Now, for n=1 f(n)= 0.
For n=2 f(n)= 3/4 reduces the error from 11.1% to 0.925%
For n=3 f(n) = 3/4*128 = 96 reduces the error from 0.207% to 0.031%

I suggest f(n) = (3/4)*(n-1)^(n*n - 2)
but I am missing a good heuristic argument for it.

B.t.w. the correction will be slowing down very fast for larger n.
For n=5 the number of Sudoku solutions is
4.36478 90633 27 E308 for f(5) = 0 and
4.36478 9063699 E308 for(5) according to the above suggestion

At least, the suggestion for f(n) helps in knowing how many of the most significant digits are correct, iff we can give a heurictic argument for f(n).

[Ton Smeets]

The following order 4 Sudoku puzzle with 64 clues has a unique solution as checked by sudoku-solutions.com

The Sudoku puzzle was obtained using minimal Sudoku puzzle of order 2 with 4 clues, and the self orthogonallity of such its solution to cunstruct an order 4 puzzle:
10003000D00020000005000G00070001006000F000A0005002000B00040006009000B000C000A0000008000C000G000400C000G000F000D00G000F000B000700D000F000G000E0000007000B000F000300A000C000B0009004000G000C00080050007000800060000006000A000E0002002000400030001001000D0009000500

I do not know if any puzzle is known up to now with less clues. I predict that the minimum number of clues for such a puzzle is bounded between 48 and 64.

[Afmob]

The current known minimum is 56 as one can see here.

[Ton Smeets]

The following order 4 Sudoku puzzle with 64 clues has a unique solution as checked by sudoku-solutions.com
The Sudoku puzzle was obtained using minimal Sudoku puzzle of order 2 with 4 clues, and the self orthogonallity of such its solution to cunstruct an order 4 puzzle:
10003000D00020000005000G00070001006000F000A0005002000B00040006009000B000C000A0000008000C000G000400C000G000F000D00G000F000B000700D000F000G000E0000007000B000F000300A000C000B0009004000G000C00080050007000800060000006000A000E0002002000400030001001000D0009000500

I do not know if any puzzle is known up to now with less clues. I predict that the minimum number of clues for such a puzzle is bounded between 48 and 64.

The following is even a 45-clue minimal Sudoku puzzle op order 4. It was obtained from the previous contribution by reducing the clues from the top left block, the top row, the left column and the left upper cells from each block. The uniqueness is again checked with the same tool.
00000000000000000000000G00070001000000F000A0005000000B000400060000000000000000000008000C000G000400C000G000F000D00G000F000B00070000000000000000000007000B000F000300A000C000B0009004000G000C00080000000000000000000006000A000E0002002000400030001001000D0009000500

[Afmob]

I've just checked both of your puzzles with JSudoku and they both have multiple solutions.

[JasonLion]

The following is even a 45-clue minimal Sudoku puzzle op order 4. It was obtained from the previous contribution by reducing the clues from the top left block, the top row, the left column and the left upper cells from each block. The uniqueness is again checked with the same tool.
00000000000000000000000G00070001000000F000A0005000000B000400060000000000000000000008000C000G000400C000G000F000D00G000F000B00070000000000000000000007000B000F000300A000C000B0009004000G000C00080000000000000000000006000A000E0002002000400030001001000D0009000500

This puzzle appears to have a very large number of solutions. I stopped my program after 1,000,000 solutions.