Su-Doku's maths

Everything about Sudoku that doesn't fit in one of the other sections

Postby coloin » Fri Jul 08, 2005 4:19 pm

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
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby Guest » Sat Jul 09, 2005 8:53 pm

Bertram wrote:
The result of the computation is

6,670,903,752,021,072,936,960 = 2^15 * 3^8 * 5*7 * 27,704,267,971 = 9! * 72^2 * 2^7 * 27,704,267,971


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

...?
Guest
 
Posts: 312
Joined: 25 November 2005

Postby gfroyle » Sat Jul 09, 2005 11:52 pm

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

Postby Guest » Sun Jul 10, 2005 1:35 am

No, I mean aren't they unequal.... Surely

9! * 72^2 * 2^7 =

9.8.7.6.5.4.3.2 * (3^2 * 2^3)^2 * 2^7 =

3^2 * 2^3 * 7 * 2 * 3 * 5 * 2^2 * 3 * 2 * 3^4 * 2^6 * 2^7 =

2^20 * 3^8 * 5 * 7.

...32 times more than 2^15*3^8*5*7?
Guest
 
Posts: 312
Joined: 25 November 2005

Postby gfroyle » Sun Jul 10, 2005 7:31 am

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

Postby frazer » Mon Jul 11, 2005 9:33 am

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
frazer
 
Posts: 46
Joined: 06 June 2005

maths - how many permutations

Postby Pete-B » Sat Jul 16, 2005 1:02 am

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
Pete-B
 
Posts: 1
Joined: 15 July 2005

Sudoku Unraveling- I think

Postby coloin » Sat Jul 16, 2005 9:02 pm

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 ?
coloin
 
Posts: 1632
Joined: 05 May 2005

New Classification

Postby coloin » Sat Jul 16, 2005 9:18 pm

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
Last edited by coloin on Sat Jul 23, 2005 8:10 am, edited 2 times in total.
coloin
 
Posts: 1632
Joined: 05 May 2005

?

Postby coloin » Sat Jul 16, 2005 9:35 pm

Deleted
Last edited by coloin on Tue Aug 02, 2005 2:00 pm, edited 8 times in total.
coloin
 
Posts: 1632
Joined: 05 May 2005

4d possibilities

Postby Guest » Sun Jul 17, 2005 8:07 am

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

Computed number of squares

Postby skeptic » Sun Jul 17, 2005 9:33 pm

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.
skeptic
 
Posts: 2
Joined: 17 July 2005

Re: Computed number of squares

Postby coloin » Mon Jul 18, 2005 8:39 am

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: 1632
Joined: 05 May 2005

Postby frazer » Mon Jul 18, 2005 9:43 am

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
frazer
 
Posts: 46
Joined: 06 June 2005

skepticism retracted

Postby skeptic » Mon Jul 18, 2005 11:53 am

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.
skeptic
 
Posts: 2
Joined: 17 July 2005

PreviousNext

Return to General