The New Sudoku Players' Forum

[Guest]

While there are 9! possible permutations of "adgbehcfi", a simple program can show the number of "LEGAL" permuations to be only 8784

You've introduced an additional constraint, not normally found in sudoku, that no digit can appear at the same offset within two 3x3 boxes. In that case then yes, there are 8784 legal perms. In the standard case, though, we're not restricted to permutations of abcdefghi and so the number of valid arrangements jumps to 46656.

Whilst I don't think there's much interest left in making the standard sudoku calculation quicker, it might be interesting to tackle restricted sudoku. In restricted sudoku, there seem to be very few symmetries to exploit, so we would appear to be in the unfortunate situation of needing much more computing power to calculate a much smaller number ...

[su bloko]

I note that Red Ed has now confirmed the exact number derived by Bertram/AFJ. Great!

I wonder if Bertram/AFJ are ready to publish their methodology? It would be much appreciated.

I write in the knowledge that wikipedia have made the sudoku entry a "featured article". It is likely that the result of your calculation will soon be exposed to the main page of wikipedia! Before this happens I would very much like to fully credit the calculation (i.e. AFJ as well as BF). Frazer, you need to let us all know your name if you want an entry in the the best Encyclopedia on the net!

You can email me at zimazama1001 AT yahoo dot com

[Guest]

You've introduced an additional constraint, not normally found in sudoku, that no digit can appear at the same offset within two 3x3 boxes.

Oops... Didn't take long to construct a problem that breaks this new rule. Now I see why my #s were so much lower.

I like the "restricted" sudoku, though: this one extra rule allows to drop the number of clues one needs and might allow problems that your solver would not like (yet). I'll play with it a bit.

thanks for clearing up the confusion
amanzimdwini

[tannedblondbloke]

My congratulations to Bertram and AFJ on enumerating the number of possible grids, and to Bertram in particular for getting his name in Wikipedia!

I seemed to miss so much while on holiday, this thread quadrupled in size! I haven't had the time to digest the details yet, but clearly your methods have faced quite a bit of scrutiny. I look forward to seeing your paper, and looking at this thread properly.

16 clue sodoku anyone?

[frazer]

The document with the method of enumerating grids is more or less ready, but I was delayed for various reasons (which will probably delay it for another week, at least). Also, we'd like to update it to include Red Ed's verification methods, which seems to isolate the 44 equivalence classes that we'd found more effectively.

Best wishes, Frazer

[tinfoil]

16 clue sodoku anyone?

You are a sadist for even posing the question.

However, if someone feels like working out the number of valid answers for a 4x16 chute, I'll be more than happy to give you a good estimate of the overall 16x16 answer (plus or minus 1%) that I would be willing to bet money on. ;)

[su bloko]

I have updated the wikipedia entry.

http://en.wikipedia.org/wiki/Sudoku

It needs a link to the paper the smart people who derived the result are in the process of writing.

It mentions that the 16x16 result is not known!

[Red Ed]

In an earlier post, I foolishly ventured that

In restricted sudoku, there seem to be very few symmetries to exploit, so we would appear to be in the unfortunate situation of needing much more computing power to calculate a much smaller number ...

Well, not so The number of restricted sudokus, such that no digit appears at the same offset in any two 3x3 boxes, appears to be 201105135151764480. Here's how ...

1. without loss of generality, we can assume the top left box is 1...9 in order. We can also assume that the 1s in boxes 2,3 (top middle/right) are in rows 2,3 respectively and the 1s in boxes 4,7 are in columns 2,3. So we solve the problem with those constraints and multiply the answer by 9! x 4.

2. naively, we can just exhaust over the 244 subproblems corresponding to each of the possible arrangements of 1s. Someone said earlier that there are 8784 arrangements without the constraints above, so that's 8784/9 = 976 with 1 in the top left cell and 976/4 = 244 with the additional row/col constraints. But we can do better.

3. following AFJ's and Bertram's lead, we can look for equivalence classes. The following operations leave the number of solutions intact: (a) rotate the whole grid; (b) transpose it; (c) switch the order of the row bands [by band, I mean rows 1,2,3 or 4,5,6 or 7,8,9]; (d) switch the order of the rows within each band according to the *same* permutation for each band. Applying these ops, we find that the 244 layouts of the 1s breaks down into 11 equivalence classes of sizes 1, 2, 4, 9, 12, 18, 18, 36, 36, 36, 72. The number of solutions for each of the 11 representative subproblems is different, suggesting this is the best we can do.

I could easily have messed up my sums here -- I've done it before. Anyone want to check it?

[Bertram]

I note that Red Ed has now confirmed the exact number derived by Bertram/AFJ. Great!

I wonder if Bertram/AFJ are ready to publish their methodology? It would be much appreciated.

I was extremely busy with something else for the last week, but I'll have time to look into this again in the next few days. Ed's computation methods and programs are also very impressive.

Bertram

[tinfoil]

16 clue sodoku anyone?

You are a sadist for even posing the question.

However, if someone feels like working out the number of valid answers for a 4x16 chute, I'll be more than happy to give you a good estimate of the overall 16x16 answer (plus or minus 1%) that I would be willing to bet money on. ;)

First pass to get folks started on solutions for a 16x16:

Step 1: Applying only the box rule, there are 16! ways to fill each box, for 16!^16 ways to fill all 16 boxes. This represents an intimidating 1.349 * 10^213 ways to fill the boxes, ignoring row and column rules.

Step 2A: Let's apply only the row rule to the above. Box (1,1) has 16! ways to arrange the digits. For each of these, there are K combinations of digits for the ROWS of boxes (1,2) and (1,3). The rows of box (1,4) are forced by the other boxes in the chute. There are 4! ways to arrange each row in these 3 boxes, for 4!^12 permutations. This creates a total of 16! * 4!^12 * K ways to fill the top chute, and this value raised to the fourth power to fill all four chutes. Determining the value of K is left as an exercise for the student ;)

Step 2B: The same logic can be applied to the columns to work out the number of valid solutions for each vertical chute.

Step 3: Either way, you will get a reduction ratio R equal to [16!^16] / [16! * 4!^12 * K]^4 by applying the row and column rules separately. This can be reduced a bit to R = [16!^12] / [4!^48 * K^4].

Step 4: I contend that combining both of these rules together would reduce the initial 16!^16 value for valid solutions by a factor of almost exactly R^2.


As an aside, I suspect the sheer size of the computational logistics makes the exact solution a very very difficult target.


P.S: 10^213 ? And to think that I thought I'd never see a 'practical' use for numbers bigger than a google. Now I'm using numbers on the order of 10 trillion (google)^2.

[Hobbess]

For some reason last night while trying to get to sleep my head started wanting to work out the number of possible solutions to a normal 9x9 sudoku puzzle. I jumped on the web in the morning to find the answer and have just read through a lot of this thread to see that I was way off, not being much of a mathematician. out of interest though I wanted to post my thoughts and see what people think!

Pretty sure my approach hasn't been used anywhere on this thread.

Using a grid of squares:
abc
def
ghi

I tried to figure out how many ways you could place 1 number uniquely in a sudoku grid. So starting in one square you have 9 options for the first number. From that you choose two more squares which are unrelated to each other but bound by the first one, i.e. where you place it in one wont effect where you place the number in another.

So if your first number is in e then you can choose b and d for both of these you have 6 options in each one for the number, as either one column or one row already has the original number in.

So options so far = 9*6*6 = 324

Next two boxes choose only those effected by only 2 previous filled boxes, so in the example h and f, these now have two rows or two columns filled so only 3 options each

So options so far = 324*3*3 = 2916

Next another two boxes again only effected by two previous boxes, g and c, this time they are now effected by one row and one column so there are 4 options each

so options so far = 46656

Final 2 boxes which are effected by 2 columns and 2 rows so they would each only have one option, no more multiplication needed.

so number of options one number can be placed 9 times in a sudoku square = 46656

the theory in my head is now not so sure about whether the next step is to put this to the power 9 for all 9 numbers or even to factorial this number? Anyway first thought was i put it to the power 9 and I get number of possible sudoku combinations as: 1.048 x 10^42

Make sense or am I miles off?

[geoff]

going accross the top row
B1 16! of course
B2 748521 * 24^4
symetry reduces this to 28 cases we need to look at for box 3
B3 1664 * 24^4 to 4900 * 24^4 average 1273431960 * 24^4 / 748521
B4 24^4

using the approximations I used for 9 by 9 and 4 by 4 I get
5.95838 * 10 ^ 98

= (1273431960 * 24^12 /16!)^8
I was 11.1% low for 4 by 4
0.2% low for 9 by 9
I would be very suprised if this was outside 1%

A note on the source of errors in the approximation

with 4 boxes
B1 B2
B3 B4

I get the average for B4 based on all possible B2 and B3 ignoring B1.
note that the nuber of posibilities for box 4 depends only on the contents of the columns of box 2 not on the order of the columns or the order within the columns, similarly for rows in box 3.
in the 4 by 4 case this means I average 9 instead of 4 cases. 44% of cases are possible.
in 9 by 9 I average 280 ^2 instead of 252^2. 81% of cases are possible
in 16 x 16 over 98% of case are possible but they are not equally likely as they were for the smaller cases.

similarly for boxes
123
456
789

I calculate the average number for box 9 using all possible boxes 3 6 7 and 8 ignoring 1 2 4 5.

and the same for box 16.

[geoff]

You got the first bit right. the 9 copies of your first number can go in in 46656 (6^6) ways. For the next number many of the 46656 ways are blocked. I first gess is each of the first 9 entries block 1/9 of possibilities. This would leave 16163.4774 ways of puting in a second set. The actual answer is slightly higher, if I remember correctly between 17 and 18 thousand. You could then estimate the possibilities fro the third set at 46656 * (7/9)^9 but the estimates get increasingly inaccurate. If you have 8 sets in the probability the ninth goes in is not 46656 /(9^9) = 1.2 * 10^ -4 but 1. Also after you have put in the 1's and 2's the number of ways of inserting the 3's depends on the method chosen for 1's and 2's making an accurate count this way difficult

Others have followed this line further than I have. I suspect that after putting in 1's and 2's the best thing is to reduce the number of cases by symetry and count each by computer. or count the solutions to the problem below and multipy by 46656 * 4032 (6^6 * 8!)

123 xxx xxx
456 1xx xxx
789 xxx 1xx

x1x xxx xxx
xxx x1x xxx
xxx xxx x1x

xx1 xxx xxx
xxx xx1 xxx
xxx xxx xx1

[rod]

Whilst I have no idea how to work out how many puzzles there can be I was looking at the "uniqueness" of each solution. Before I found out that the basic terms for each 3x3 box were numbered

123
456
789 I had named them

ABC
DEF
GHJ and the chute ABC has a relationship with the band ADG such that a puzzle could be presented with the chutes and bands shuffled yet still maintaining Sudokuness.

In other words

BAC
EDF
HGJ is a valid puzzle and likewise

CAB
FDE
JGH etc.

Similarly you can shuffle all the boxes but still maintain a Sudoku solution for essentially the same group of numbers and same total number of clues, just the symmetry of the clues would change.

This means there are 72 different "arrangements" of the same solution for a given set of clues. Of course each of my shuffled permutations are already included in all the myriad calculations of possible Sudoku puzzles.

..... I think......

[tinfoil]

The result of the computation is

6,670,903,752,021,072,936,960

Two interesting facts:
Number of valid Sokuku solutions 6.67 * 10^21
Mass of Oberon, a moon of Saturn, in pounds: 6.67 * 10^21.

A coincidence? I think not. ;)