Number of "magic sudokus" (and random generation)

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

Number of "magic sudokus" (and random generation)

Postby DrSudoku » Sun Oct 30, 2005 1:28 pm

Hi,

I am intereste in calculating how many "magic sudokus" it's possible to create. A "magic sudoku" is a normal sudoku with an extra constraint:
in each of the 9 3x3 squares the sum of each row and col must be the same (15).

I have read about the difficulty in calculating the number of regular sudokus but I reckon it's possible to calculate the numbers when it's a magic sudoku. The number of possible 3x3 squares where the sum of each row and col is 15 should be each to calculate.

I have written a simple program i c to generate random "magic sudokus" but I am interested in knowing how many it's possible to make. I have a hunch that it's not that many.

Here's some output examples from my program:

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


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


8 6 1 | 2 9 4 | 3 5 7
3 7 5 | 6 1 8 | 4 9 2
4 2 9 | 7 5 3 | 8 1 6
---------------------
5 3 7 | 8 6 1 | 2 4 9
9 4 2 | 3 7 5 | 6 8 1
1 8 6 | 4 2 9 | 7 3 5
---------------------
7 5 3 | 1 8 6 | 9 2 4
2 9 4 | 5 3 7 | 1 6 8
6 1 8 | 9 4 2 | 5 7 3
DrSudoku
 
Posts: 2
Joined: 30 October 2005

Postby Pi » Sun Oct 30, 2005 2:49 pm

as sudoku's numbers aren't really number, they are just symbols i suppose that is easy to calculate.

Thanks to the people who calculated the number of sudoku in existance to be 6670903752021072936960 the number of your sudoku's is a fraction of that, if you can work out the probabilty if the sum of any random three number being 15 and then multiply that number by 54 (3X9X2) you can divide 6670903752021072936960 by this number and get your answer.
I believe your answer is

oh blast it's lquite considerably less than 1

could a mathematician have a go please!
Pi
 
Posts: 389
Joined: 27 May 2005

Postby PaulIQ164 » Sun Oct 30, 2005 3:02 pm

The problem (or at least, one problem) with your method is that if two of the mini-rows or mini-cols in a box add up to 15, then the other will by definition. I think it's going to be a very complicated calculation to work it out exactly.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby Pi » Sun Oct 30, 2005 3:13 pm

good point i didn't think of that
Pi
 
Posts: 389
Joined: 27 May 2005

Postby gfroyle » Mon Oct 31, 2005 3:38 am

I get

5 971 968 = 2^4 x 3^2 x 11 x 13 x 29

This is just a direct computer search because the condition is so restrictive that it dramatically reduces the search space.

I am sure dukuso can give a theoretical explanation of this number, and as I have no time to spare, I will leave it to him..

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Condor » Mon Oct 31, 2005 3:46 am

gfroyle wrote:5 971 968 = 2^4 x 3^2 x 11 x 13 x 29

Can we assume that includes rotations and reflections. From the lack of a 9! factor I would assume it does not include relabeling.
Condor
 
Posts: 62
Joined: 19 June 2005

Postby gfroyle » Mon Oct 31, 2005 4:12 am

Condor wrote:Can we assume that includes rotations and reflections. From the lack of a 9! factor I would assume it does not include relabeling.


That number has NO reductions performed at all, so it is literally the number of different strings of 81 numbers that can be written down to form a valid "magic Sudoku".

Notice that relabelling is not possible in this game...if we change the numbers then the magic-ness probably disappears...
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby DanO » Mon Oct 31, 2005 4:33 am

There are 7 sets of 3 numbers from 1-9 that add to 15:
Code: Select all
A   1 5 9
B   1 6 8
C   2 4 9
D   2 5 8
E   2 6 7
F   3 4 8
G   3 5 7

There is only 1 canonical 15 puzzle that can be built from these sub-lines so we will make that block 1.

Code: Select all
   B G C

A   1 5 9
E   6 7 2   
F   8 3 4


Row 1 of block 2 can be sub-line E or F. But if either is chosen then line 1 of block 3 will be the other. So there is only 1 canonical choice to complete row 1

Row 2 of block 2 must now be sub-line F so there is still only 1 canonical way to complete the first band.

Column 1 of blocks 4 and 7 must be type C or G and there is again only 1 canonical order and this defines the rest of blocks 4 and 7.

The possibilities to fill R4C4 are 1, 3, 5 and 8 and each of these 4 numbers define all of block 5.

Block 6 only has 2 options defined by R4C7 = 4 or 8 in this canonical grid

Block 8 also has two options defined by R7C4 = 5 or 7.

With the other blocks defined, block 9 is also defined and the grid is complete.

Code: Select all
1 of 16 variations
+-------+-------+-------+
| 1 5 9 | 2 6 7 | 3 4 8 |
| 6 7 2 | 4 8 3 | 5 9 1 |
| 8 3 4 | 9 1 5 | 7 2 6 |
+-------+-------+-------+
| 2 6 7 | 1 5 9 | 4 8 3 |
| 4 8 3 | 6 7 2 | 9 1 5 |
| 9 1 5 | 8 3 4 | 2 6 7 |
+-------+-------+-------+
| 3 4 8 | 5 9 1 | 6 7 2 |
| 5 9 1 | 7 2 6 | 8 3 4 |
| 7 2 6 | 3 4 8 | 1 5 9 |
+-------+-------+-------+

Each of these 16 grids can then be trivially transformed by transposing the rows and columns, reordering the rows and columns within each band and swapping the last two bands of rows or columns giving a total of 16*2*6^6*2^2 = 5,971,968 grids.
DanO
 
Posts: 40
Joined: 18 October 2005

Re: Number of "magic sudokus" (and random generati

Postby r.e.s. » Mon Oct 31, 2005 4:44 am

DrSudoku wrote:A "magic sudoku" is a normal sudoku with an extra constraint:
in each of the 9 3x3 squares the sum of each row and col must be the same (15).

What you've described are sudoku solutions that are "magic". A magic sudoku puzzle might be one with such a unique magic solution and be such that the clues in each row, column, and box add to 15. Do these exist? (Less restrictively on the clues, perhaps just have them add to 15 in each box.)
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby dukuso » Mon Oct 31, 2005 6:50 am

each of the 5971968 has all its bands and stacks isomorphic to
band#1, the alphabetically first band from the gang of the
416 equivalence-classes of 3*9-bands.
In fact only one block is possible :
159
672
834
or its transformations by permuting rows,columns,transposing.


These 5971968 are from 2 different G-classes,
from 3 different S-classes and from 4 different T-classes.
For the definitions see:
http://www.setbb.com/phpbb/viewtopic.php?t=194&mforum=sudoku

Define M-classes as allowing the known 6^8*2 transformations and
all permutations of digits in minirows or minicolumns of:
159
672
834
as well as transposing that 3*3.That gives 3!*3!*2=72 permutations.

The whole group has size (72)*(6^8*2) and acts on the magic sudokus.
Our 5971968 magic sudokus form 3 classes, the minimal member from each
class is listed below. The 3 already posted magic sudokus were
from 2 classes only.
The automorphismgroups have sizes 72,648,108 so the group
generates orbits of sizes 3359232,373248,2239488 which sums to 5971968.

Maybe I can create some magic-sudoku puzzles, but it was slow when
I tried it on killer sudokus earlier. A magic sudoku would be a killer
sudoku with 54 overlapping regions and some additional clues.

the 3 M-classes:

Code: Select all
159267348
672483591
834915726
267159483
483672915
915834267
348591672
591726834
726348159

159267348
672483591
834915726
267348159
483591672
915726834
348159267
591672483
726834915

159267348
672483591
834915726
267348159
483591672
915726834
348672915
591834267
726159483

dukuso
 
Posts: 479
Joined: 25 June 2005

Postby Moschopulus » Mon Oct 31, 2005 12:08 pm

By the way, these should not really be called "magic".
A magic square has all rows, columns *and* diagonals summing to the same number.
They were discussed before in this thread

http://forum.enjoysudoku.com/viewtopic.php?t=897&start=0

You can't have all 9 boxes being magic squares.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby udosuk » Mon Oct 31, 2005 4:16 pm

DanO wrote:There are 7 sets of 3 numbers from 1-9 that add to 15:
Code: Select all
A   1 5 9
B   1 6 8
C   2 4 9
D   2 5 8
E   2 6 7
F   3 4 8
G   3 5 7
Whatever happened to "4 5 6"? ^_^

Great analysis though!

BTW "magic" is quite acceptable here. The diagonal property is just so that the 3x3 grid will be unique. It's not called the "3x3 magic squares sudoku" anyway...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby BlueSpark » Thu Nov 03, 2005 10:42 pm

Udosuk,

4 + 5 + 6 does equal 15, but this combo is unusable in a "magic" sudoku as it would preclude those numbers from being used in the rest of the row/column/square (and every combo adding up to 15 has to contain at least one of those numbers). If you look at the above "magic" sudokus, every three-number row and column contains only one of those three numbers.

But you probably already knew that!:)
BlueSpark
 
Posts: 18
Joined: 04 October 2005

Postby r.e.s. » Fri Nov 04, 2005 1:06 am

dukuso wrote:Maybe I can create some magic-sudoku puzzles
I presume that no followup means that no magic sudoku puzzles have yet been found (as opposed to magic sudoku solutions)?
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby DrSudoku » Fri Nov 04, 2005 2:59 am

r.e.s. wrote:
dukuso wrote:Maybe I can create some magic-sudoku puzzles
I presume that no followup means that no magic sudoku puzzles have yet been found (as opposed to magic sudoku solutions)?


How about this one:
2 9 4 | 8 6 1 | 3 7 5
7 5 3 | 4 2 9 | 8 6 1
6 1 8 | 3 7 5 | 4 2 9
----------------------
8 6 1 | 2 9 4 | 5 3 7
4 2 9 | 7 5 3 | 1 8 6
3 7 5 | 6 1 8 | 9 4 2
----------------------
1 8 6 | 5 3 7 | 2 9 4
9 4 2 | 1 8 6 | 7 5 3
5 3 7 | 9 4 2 | 6 1 8
DrSudoku
 
Posts: 2
Joined: 30 October 2005

Next

Return to General