Rael - you could be right [- as we have just seen posted] so please explain the well known other problem !

Guenter and Ed - it is reasurring to have you both on the project !

I await your next moves

truffaldino wrote:Sorry, just a quick question... am I going mad or is

2^15 * 3^8 * 5 * 7

not equal to

9! * 72^2 * 2^7

...?

Yes, they are equal.. and this is exactly what was claimed - that the result of the computation is equal to a big prime number, 27704267971 multiplied by some other factors which can either be expressed as the prime decomposition (2^15 etc) or in the other form (9! etc) which is more related to the structure of the problem.

- gfroyle
**Posts:**214**Joined:**21 June 2005

truffaldino wrote:No, I mean aren't they unequal....

Whoops.. sorry about that - you are right. I just checked that the last expression was a correct factorization of the big number, not realizing that you were concerned about the prime decomposition. Indeed, the correct factorization has 2^20 in there..... well spotted.

Gordon

- gfroyle
**Posts:**214**Joined:**21 June 2005

Congratulations to Ed for the completion of the calculation of essentially different grids! The web page has been updated suitably. (Incidentally, it should now be easy to work out the number if you take a different definition of "essentially different", perhaps just including rotations and reflections -- you just get a smaller symmetry group, but the invariants for each element are already calculated.) I'm rather in awe of Bertram, Ed and Guenter for their programming abilities. I'm going to have to improve my own... And I'm glad that Guenter's figure agrees with that already found by Bertram and Ed!

datprogrammer's computation shouldn't really be a surprise; straight away, we are dividing by 9!=362880 to account for relabelling, and it probably isn't too surprising that relections, rotations, and various permutations make any grid equivalent to tens of thousands of others.

Well done to truffaldino for spotting that missing factor of 32.

Frazer

datprogrammer's computation shouldn't really be a surprise; straight away, we are dividing by 9!=362880 to account for relabelling, and it probably isn't too surprising that relections, rotations, and various permutations make any grid equivalent to tens of thousands of others.

Well done to truffaldino for spotting that missing factor of 32.

Frazer

- frazer
**Posts:**46**Joined:**06 June 2005

Thanks for that Frazer.

I reasoned that the total has 9! * 6^2 as a factor because:

a) Any one "root" puzzle can have 9! variations simply by swapping numbers in a one-for-one mapping. You can swap anything from two to nine numbers in this way. For example; a substitution code (three number swap) could be let 1=5; let 5=9 and let 9=1. You could call this the "enigma variation" rule.

b) Secondly, you can also shift both rows and columns (of the "root" puzzle) in blocks of three so that sub-squares remain intact. If the nine subsquares are represented as

ABC

DEF

GHI

You could shift row blocks to give

DEF

GHI

ABC

and then shift column blocks to get

EFD

HIG

BCA

giving 6 * 6 variations on the root puzzle.

I think that the other factor may be n!/(n-1) as a general rule for all grids; in our case n=9.

So my gut feeling is that there should be

9! * 3!^2 * 9!/(n-1) = 9!^2 * 36 / 8 = 5.93 E 11 possible variations.

- Pete B

I reasoned that the total has 9! * 6^2 as a factor because:

a) Any one "root" puzzle can have 9! variations simply by swapping numbers in a one-for-one mapping. You can swap anything from two to nine numbers in this way. For example; a substitution code (three number swap) could be let 1=5; let 5=9 and let 9=1. You could call this the "enigma variation" rule.

b) Secondly, you can also shift both rows and columns (of the "root" puzzle) in blocks of three so that sub-squares remain intact. If the nine subsquares are represented as

ABC

DEF

GHI

You could shift row blocks to give

DEF

GHI

ABC

and then shift column blocks to get

EFD

HIG

BCA

giving 6 * 6 variations on the root puzzle.

I think that the other factor may be n!/(n-1) as a general rule for all grids; in our case n=9.

So my gut feeling is that there should be

9! * 3!^2 * 9!/(n-1) = 9!^2 * 36 / 8 = 5.93 E 11 possible variations.

- Pete B

- Pete-B
**Posts:**1**Joined:**15 July 2005

In a bid to find out a bit more about specific grids - I have an idea about

................doubling up the gang of 44.

This is using boxes

B1 B2 B3

B4

B7

Each horizontal element of the gang can be "crossed" with another of the vertical gang. Each of these classes will have a number of valid grids.

Each of these classes would have a variable number of completions from the representation of the 5 boxes.

Small numbers perhaps represents a tight grid.

There would be 44^2 classes = 1936 [Not too much for a computor ]

What do you think ?

................doubling up the gang of 44.

This is using boxes

B1 B2 B3

B4

B7

Each horizontal element of the gang can be "crossed" with another of the vertical gang. Each of these classes will have a number of valid grids.

Each of these classes would have a variable number of completions from the representation of the 5 boxes.

Small numbers perhaps represents a tight grid.

There would be 44^2 classes = 1936 [Not too much for a computor ]

What do you think ?

- coloin
**Posts:**1638**Joined:**05 May 2005

A method of classifying all valid grids.

Now you can represent a valid semicompleted grid like this

xxx xxx ooo

xxx xxx ooo

xxx xxx ooo

ooo xxx xxx

ooo xxx xxx

ooo xxx xxx

xxx ooo xxx

xxx ooo xxx

xxx ooo xxx

where x = a number and o = no number - 54 clues and it self fills

It can be reduced easily to 8 in each box - 48 clues the last number in each self completes .

It can also be expressed and reduced as 39 clues - pairs are prevented. I do hope everything else is as well. [it can lose an extra clue in box 1 but I like the option of the fixed box 1 [9!]

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

And it still always completes - 9! * [9!/3!]^5 = 293644550359018880630784000000 [way big]

Partially filling in a sudoku and swopping box/column 2 and 3 gives

[The reason for this is related to my previous posting]

123 ooo o47

456 ooo 1o8

789 ooo 32o

ooo o63 o59

ooo 9o1 4o3

ooo 42o 67o

o17 o92 ooo

2o4 8o6 ooo

36o 57o ooo

And every sudoku as boxes [[1]],[3,7], [5,6,8]

This grid woud be [[123456789]],[471832,172436,][639142,594367,928657]

Can anyone see a suduku that wont autocomplete with these - [does an x wing defeat it ?]

EDIT

THis defeats it unfortunately - "thanks" to Guenter

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

This means we need the first 8 numbers of each of the 6 boxes.

Colin

Now you can represent a valid semicompleted grid like this

xxx xxx ooo

xxx xxx ooo

xxx xxx ooo

ooo xxx xxx

ooo xxx xxx

ooo xxx xxx

xxx ooo xxx

xxx ooo xxx

xxx ooo xxx

where x = a number and o = no number - 54 clues and it self fills

It can be reduced easily to 8 in each box - 48 clues the last number in each self completes .

It can also be expressed and reduced as 39 clues - pairs are prevented. I do hope everything else is as well. [it can lose an extra clue in box 1 but I like the option of the fixed box 1 [9!]

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

And it still always completes - 9! * [9!/3!]^5 = 293644550359018880630784000000 [way big]

Partially filling in a sudoku and swopping box/column 2 and 3 gives

[The reason for this is related to my previous posting]

123 ooo o47

456 ooo 1o8

789 ooo 32o

ooo o63 o59

ooo 9o1 4o3

ooo 42o 67o

o17 o92 ooo

2o4 8o6 ooo

36o 57o ooo

And every sudoku as boxes [[1]],[3,7], [5,6,8]

This grid woud be [[123456789]],[471832,172436,][639142,594367,928657]

Can anyone see a suduku that wont autocomplete with these - [does an x wing defeat it ?]

EDIT

THis defeats it unfortunately - "thanks" to Guenter

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

This means we need the first 8 numbers of each of the 6 boxes.

Colin

Last edited by coloin on Sat Jul 23, 2005 8:10 am, edited 2 times in total.

- coloin
**Posts:**1638**Joined:**05 May 2005

I had an idea about a filled Sudoku grid acting as a 3x3x3x3 tesseract sliced up into 3x3 "sheets" and arranged according to other 2 dimensions.

- Guest
**Posts:**312**Joined:**25 November 2005

The number being promulgated seems to this observer to be fallacious. Symmetry seems to demand a perfect square. (x 9!, of course.)

The central sub-square (B5) can be filled in 9! ways. For each of them, sub-square B4 can be filled with triplets in each of its rows, without regard to permutations within each triplet. There are 56 possible sets of triplets, and therefore 56 x (3!)^3 = 12096 ways. This determines the row triplets for sub-square B6, but they can be permutated independently, for another factor of (3!)^3. Combined, B4 and B6 can be filled in 2612736 ways. They are complementary. For each configuration of B4, there is an identical configuration of B6. Put another way, B4 and B6 can be permutated or swapped. This applies equally for filling B2 and B8 above and below the central square. (So the total number of squares must be greater than 9! x (2612736)^2. (About 2.5E18, much less than the computed 6.7E21)

Calculation of the ways to fill B1 is complex. The number of possibilities for each of the 12096^2 combinations of B4 and B2 depends on the specific configurations of those two sub-squares. Symmetry makes me think the number should be a square, but perhaps not. On the other hand, the complete symmetry between the ways of filling B1 and B9 leads me to believe that they have to have identical possibilities. The possible triplet sets for B4 and B6 are identical. The same is true for B2 and B8.

When those 7 sub-squares are filled, the filling of B3 and B7 is deterministic, and unique. This implies that the total number of possible squares must be a perfect square, x9!. This is not true of the computed number.

The website states that filling B2 has constraints based on the configuration of B4. Is this true? Even if it is, the symmetry with regard to B1 ansd B9 applies.

The central sub-square (B5) can be filled in 9! ways. For each of them, sub-square B4 can be filled with triplets in each of its rows, without regard to permutations within each triplet. There are 56 possible sets of triplets, and therefore 56 x (3!)^3 = 12096 ways. This determines the row triplets for sub-square B6, but they can be permutated independently, for another factor of (3!)^3. Combined, B4 and B6 can be filled in 2612736 ways. They are complementary. For each configuration of B4, there is an identical configuration of B6. Put another way, B4 and B6 can be permutated or swapped. This applies equally for filling B2 and B8 above and below the central square. (So the total number of squares must be greater than 9! x (2612736)^2. (About 2.5E18, much less than the computed 6.7E21)

Calculation of the ways to fill B1 is complex. The number of possibilities for each of the 12096^2 combinations of B4 and B2 depends on the specific configurations of those two sub-squares. Symmetry makes me think the number should be a square, but perhaps not. On the other hand, the complete symmetry between the ways of filling B1 and B9 leads me to believe that they have to have identical possibilities. The possible triplet sets for B4 and B6 are identical. The same is true for B2 and B8.

When those 7 sub-squares are filled, the filling of B3 and B7 is deterministic, and unique. This implies that the total number of possible squares must be a perfect square, x9!. This is not true of the computed number.

The website states that filling B2 has constraints based on the configuration of B4. Is this true? Even if it is, the symmetry with regard to B1 ansd B9 applies.

- skeptic
**Posts:**2**Joined:**17 July 2005

skeptic wrote:This implies that the total number of possible squares must be a perfect square, x9!. This is not true of the computed number.

Nothing is sraightforward with this 9x9

skeptic wrote:The website states that filling B2 has constraints based on the configuration of B4. Is this true? Even if it is, the symmetry with regard to B1 ansd B9 applies.

The constraints apply but it depends what box order you use.

B1B2B3

B1B5B9 calculations have been identical

The B5 - B2B4B6B8 - B1B3B7B9 is symetrical I agree - one day soon we will have an explanation

Keep working on it !

- coloin
**Posts:**1638**Joined:**05 May 2005

In reply to skeptic, your argument looks good at first. There are indeed N=9!x(2612736)^2 ways to fill in B2, B4, B5, B6 and B8, for exactly the reasons you observe (B2 and B8 are independent of B4 and B6). However, different arrangements for B2, B4, B5, B6, and B8 have a different number of ways to complete to a full grid, which gets rid of the square factor. For example, if all but one of these N ways to fill in B2, B4, B5, B6 and B8 can be completed to a full grid in, say, 1000 ways, and the other one can be completed in 1001 ways, then the total number of full grids will be 1000*(N-1)+1001=1000N+1, no longer divisible by N.

As you observe, given B2 and B4, the number of ways of filling B1 is a complex calculation, and, indeed, it is here that the variation starts happening. There may be as few as 384 ways to complete B1, or as many as 448, if I remember correctly. Both B1 and B9 have this variation (and I see no reason why they should have the same number of possibilities, given B2, B4-B6, B8, although it's possible that it is true). You then point out, "the filling of B3 and B7 is deterministic and unique", but this is not quite right -- it is deterministic in that at most one solution exists, but it is actually much more likely that there are no solutions at this step. So again, you can have either 0 or 1 way to complete to a full grid given your first 7 blocks.

Frazer

As you observe, given B2 and B4, the number of ways of filling B1 is a complex calculation, and, indeed, it is here that the variation starts happening. There may be as few as 384 ways to complete B1, or as many as 448, if I remember correctly. Both B1 and B9 have this variation (and I see no reason why they should have the same number of possibilities, given B2, B4-B6, B8, although it's possible that it is true). You then point out, "the filling of B3 and B7 is deterministic and unique", but this is not quite right -- it is deterministic in that at most one solution exists, but it is actually much more likely that there are no solutions at this step. So again, you can have either 0 or 1 way to complete to a full grid given your first 7 blocks.

Frazer

- frazer
**Posts:**46**Joined:**06 June 2005

What seemed clear yesterday was clearly fallacious after sleeing on it. The symmetry I mention would result in a factor of 2, not a square. I'd hoped to retract the posting, in order to not waste reader's time.

My apologies to all, and my thanks to Frazer and Coloin for their incredibly prompt and tolerant replies.

My apologies to all, and my thanks to Frazer and Coloin for their incredibly prompt and tolerant replies.

- skeptic
**Posts:**2**Joined:**17 July 2005