The New Sudoku Players' Forum

[Mathimagics]

.
Following a suggestion from Leren , I have also been looking at standard SudokuX, ie Sudoku with distinct values along both diagonals. Mysteriously, while it is a popular variant, it seems, little is known about the numbers.

How many different SudokuX grids there? I think the answer is (up to relabelling) 153,255,603,504.

Given that number appears nowhere relevant on the Web, I am either wrong, or nobody has counted them before.

Ah, I hear you say, but how many essentially different SudokuX grids are there?

My guess is around a billion, but I do hope to come up with an accurate figure for the number of SX-different grids at some stage soon.

As we did for SudokuP, we define SX-equivalence in terms of the subset of Sudoku transformations that preserve the diagonal property.

There are, it seems, just 12 of these (x 8 for rotation/reflection, giving 96 in all). There are 6 ways to tweak a grid so that the diagonals in the corner boxes are permuted but not shifted.

We can also permute Band2/Stack 2 to give a 180-degree rotation of the center box.

It now becomes clear why nobody seems to know how many ED SudokuX grids there are. We can't use McGuire's method (Burnside's Lemma) because of the orbit connection problem. We can (and probably will) calculate the number of SX-different grids, but the exact number of ED grids will of course be less than that.

We were able to count ED SudokuP grids because the grids that needed checking are not too numerous. But we have here around 1,000 times the number of grids, so SudokuP methods that took just a few days would take years here (not to mention the 5TB of disk space we'd need to hold all the grids).

The only alternative appears to be checking the 5.47 billion ED Sudoku grids to deterimne which have SudokuX isotopes, but that's still a daunting task.

Minimum clue counts: it is known that 12-clue puzzles exist, so the first question here is, are there 11-clue SudokuX puzzles?

Finally, I determined the number of grids above by the '1's-template method (there are 1040 templates). Thanks largely to dobrichev's fabulous fsss2 solver, I counted them all in 4 threads x 6 hours.

[Leren]

It's not clear to me whether or not all 96 X preserving transformations preserve the ES property of the X grid (ES is shorthand for not ED). The reflections and rotations obviously do but what about the others ? Also, whatever the answer, what use can be made of this information ?

We also need some motivation for this project. Presumably we would want to:

1. Confirm the total number of X Grids

2. Determine the number of ED X Grids.

3. Find out if < 12 clue puzzles exist and, if so, how many there are.

4. If 12 is the minimum, determine them all, if they are not too numerous.

5. Anything else ?

Leren

[tarek]

This is Ruud's cannoncalization method here:

http://www.sudocue.net/minx.php

tarek

[Mathimagics]

.
Ok, definition time again. We agreed, I think, that ED (essentially different) grids will always refer to comparisons made using the standard set of 3,359,232 transformations that morph one Sudoku grid into another.

ES makes sense as an abbreviation for "not ED", thanks Leren.

Ok, how to answer Leren's question 2, ie how many ED SudokuX grids?

Method 1 (test all ED grids)

We can simply count the number of ED Sudoku grids that can be morphed into a SudokuX grid.

Each of the 5.47 billion ED S-grids needs to be morphed in all ways possible. We can reduce the number of morphs required by a factor of 8, I think, so we don't waste time checking transposes/rotations, but that is still 419,904 morphs per grid.

I tested band 240 (167,032 S-grids) using the full morph set, and it took 10 hours (about 22% were X-morphable).

Even if this can be reduced to 1.25 hours by reducing the morphs by factor 8, that extrapolates to about 40,000 hours of CPU time needed for the full set. Thats' about 3 CPU-years.

Method 2 (test all X-grids)

We can take the set of X-grids and reduce that set by removing ES duplicates. ES testing is easier than morphability checking (we just compare CF's). So we would take each template, generate the X-grids, append the CF, sort the grids by CF, remove duplicate entries. We can then merge the ttemplate files to produce the final reduces set.

This worked well for SudokuP, and looks like the best option here. It also gives us the ED X-grid set, which is estimated (based on the 11% figure obtained above) at 1.2 billion grids. I'm testing one template set to see how long this will take.

[Mathimagics]

This is Ruud's cannoncalization method here:
http://www.sudocue.net/minx.php

Hi tarek,

Thanks for that link.

Swapping rows 4 & 6 and/or columns 4 & 6 gives 4 permutations for each puzzle.

I think this is wrong, swapping R4,R6 and C4,C6 will preserve X-property, but you need both, so his count of 192 should be 96.

[champagne]

.

Ok, how to answer Leren's question 2, ie how many ED SudokuX grids?

Method 1 (test all ED grids)

We can simply count the number of ED Sudoku grids that can be morphed into a SudokuX grid.

Each of the 5.47 billion ED S-grids needs to be morphed in all ways possible. We can reduce the number of morphs required by a factor of 8, I think, so we don't waste time checking transposes/rotations, but that is still 419,904 morphs per grid.

I tested band 240 (167,032 S-grids) using the full morph set, and it took 10 hours (about 22% were X-morphable).

Even if this can be reduced to 1.25 hours by reducing the morphs by factor 8, that extrapolates to about 40,000 hours of CPU time needed for the full set. Thats' about 3 CPU-years.

This seems relatively easy using the frame in progress to search 17 clues puzzles.

No need in my opinion to morph the grid.

The way I understand it, the job is to combine valid diagonal patterns in boxes and valid boxes triplets.

If I am right
6 mini diagonal main and 6 anti per box
6 ways to combines boxes in band and 6 ways in stack

And combining 2 boxes fails i one mini row/ mini column has the same digits as the first mini diagonal.
Anyway, the average number of valid solutions for 2 boxes is far from 6 x 6

This would not be too hard

[tarek]

Swapping rows 4 & 6 and/or columns 4 & 6 gives 4 permutations for each puzzle.

I think this is wrong, swapping R4,R6 and C4,C6 will preserve X-property, but you need both, so his count of 192 should be 96.

I agree with you. As the corner cells in the centre box are different. Swapping only R4R6 or C4C6 would give us an invalid SudokoX. Only when you do both swaps R4R6 AND C4C6 that you avoid that invalidity. This means only 2 permutations not 4

Tarek

[Mathimagics]

No need in my opinion to morph the grid.

The way I understand it, the job is to combine valid diagonal patterns in boxes and valid boxes triplets.

I think that what you mean is that a direct approach is possible. If a grid has some SudokuX morph then it should be possible to find that morph using only a limited set of row/col swap operations.

Is that what you mean? It looks like a good idea ...

[champagne]

No need in my opinion to morph the grid.

The way I understand it, the job is to combine valid diagonal patterns in boxes and valid boxes triplets.

I think that what you mean is that a direct approach is possible. If a grid has some SudokuX morph then it should be possible to find that morph using only a limited set of row/col swap operations.

Is that what you mean? It looks like a good idea ...

What I have in mind seems even simpler

For a given ED solution grid



You have, if I am right 6x2 valid box triplets to build a diagonal (the box order is neutral)

In each triplet, you have to consider the valid diagonals that each box can produce (6 digit triplets if I am right)
and to see if then you can get a full diagonal

Extracting the 6 valid diagonal in a box does not require swaps of rows/ columns.

EDIT

slightly more in X mode

You have 9 ways to define the central box, and having the central box, 9 ways to define the central cell.
This done, you have 9x9 starts in the central box.

And for each of the 9 central boxes, the four "corner boxes" are locked.

Combined with the previous remarks, the process should be relatively fast

[Mathimagics]

You have, if I am right 6x2 valid box triplets to build a diagonal (the box order is neutral)

I can get only 9 distinct box-triplet pairs (diag + antidiag) from the 36 box permutations:

Code: Select all

159 357
168 267
249 348
168 348
159 249
267 357
249 267
348 357
159 168


[ EDIT ] Of course! That's 1 pair for each central box choice, which fixes 4 corners, just as you indicated

[champagne]

And if you first list all valid diags and all valid antidiag (3 boxes) , To have a "X" sudoku, the diag and antidiag of the central box share one digit and only one.

Another quick filter before the final validation, so IMO, the preliminary task is to find these potential diagonal patterns

[blue]

How many different SudokuX grids there? I think the answer is (up to relabelling) 153,255,603,554.

Assuming that was a typo, I can confirm that there are (9!) * 153,255,603,504 such grids.

It now becomes clear why nobody seems to know how many ED SudokuX grids there are. We can't use McGuire's method (Burnside's Lemma) because of the orbit connection problem.

"Orbit connection problem" ?
This is the Jarvis/Russell or "Russell & Jarvis" method, BTW.

There's nothing wrong with using Burnside's Lemma, other than that it doesn't help, when it comes to producing an actual list of ED grids.
I get a result of 1,596,582,158 ED grids ... in under a second, not counting the time to arrive at the "153,255,603,504" number.

Note: Here, grids A and B are "essentially distinct" (ED), if neither can be transformed to the other, using relabelling and one of the 96 "validity preserving transformations" for SudokuX (X-Sudoku).

Nice work with the counting !

Best Regards,
Blue.

[Serg]

Hi, Mathimagics!

Following a suggestion from Leren , I have also been looking at standard SudokuX, ie Sudoku with distinct values along both diagonals. Mysteriously, while it is a popular variant, it seems, little is known about the numbers.

I heard nothing about number of such Sudokus too. But, just because it's a popular variant of Sudoku (and some players continue to publish such puzzles at this site) we should use common name for such Sudokus - "X-sudoku".

How many different SudokuX grids there? I think the answer is (up to relabelling) 153,255,603,554.

Congratulations on this result! Should we multiply this number by 9! to get number of all different X-sudoku solution grids? It turns out that number of all different X-sudoku solution grids is 3.6 times less than all different SudokuP solution grids. It's curious for me, since SudokuP has more constraints. So, I'd expect that SudokuP solution grids would be more rare than X-sudoku solution grids.

Please, describe your method in details. Did you use Red Ed's approach ("Equivalence classes") in the same manner as for SudokuP enumeration?

There are, it seems, just 12 of these (x 8 for rotation/reflection, giving 96 in all). There are 6 ways to tweak a grid so that the diagonals in the corner boxes are permuted but not shifted.

We can also permute Band2/Stack 2 to give a 180-degree rotation of the center box.

It seems to be true. I see 96 isomorphic transformation, transforming any valid X-sudoku solution grid to another valid X-sudoku solution grid.

We can't use McGuire's method (Burnside's Lemma) because of the orbit connection problem.

First of all, McGuire has nothing to do with Burnside's Lemma usage in Sudoku mathematics. It was Red Ed (aka Edward Russell), who used Burnside's Lemma for ED Sudoku solution grids enumeration.

Do you know an example of isomorphic transformation which transforms some valid X-sudoku solution grids to other valid X-sudoku solution grids, but breaks X-property for the rest valid X-sudoku solution grids?

Serg

[Mathimagics]

Assuming that was a typo, I can confirm that there are (9!) * 153,255,603,504 such grids.

It was a typo, and I have duly corrected it above.

"Orbit connection problem" ?
This is the Jarvis/Russell or "Russell & Jarvis" method, BTW.

Apologies, of course that's right.

There's nothing wrong with using Burnside's Lemma, other than that it doesn't help, when it comes to producing an actual list of ED grids.
I get a result of 1,596,582,158 ED grids ... in under a second, not counting the time to arrive at the "153,255,603,504" number.

Note: Here, grids A and B are "essentially distinct" (ED), if neither can be transformed to the other, using relabelling and one of the 96 "validity preserving transformations" for SudokuX (X-Sudoku).

We agreed to call grids ED only when referring to the full set of Sudoku transformations, so you have obtained the XD (X-different) counts. That's why I said that Burnside's Lemma does not apply.

Anyway, I'm astonished (no, gob-smacked!) by how quickly you came up with the XD count! Tell us how you did it, please!

Cheers!

[Mathimagics]

Hi, Serg!

I heard nothing about number of such Sudokus too. But, just because it's a popular variant of Sudoku (and some players continue to publish such puzzles at this site) we should use common name for such Sudokus - "X-sudoku".

I respectfully disagree! We have Sudoku, SudokuP, SudokuPX, etc Any variant can have an "X" variety so I think that suffix is best. I note that the SudoCue website (link given by tarek above) agrees with us!

Should we multiply this number by 9! to get number of all different X-sudoku solution grids?

Indeed, yes! The total number is therefore 55,613,393,399,531,520

It turns out that number of all different X-sudoku solution grids is 3.6 times less than all different SudokuP solution grids. It's curious for me, since SudokuP has more constraints.

Yes, that is indeed a surprise, and needs some explaining. At this point I don't really know why. The P-set constraints are apparently weaker.

Please, describe your method in details. Did you use Red Ed's approach ("Equivalence classes") in the same manner as for SudokuP enumeration?

I was intending to do this, and so I started with generation of '1's templates, as I did for SudokuP. With box 1 fixed, there are 1040 ways to place the 8 x "1"'s. I then just fed each template as a puzzle into my SudokuX solver (adapted from Mladen's fsss2 solver) and asked it to count all solutions.

While I was still wrestling with GAP in order to obtain the equivalence classes that would reduce the number of templates that needed processing, I found that the counting job for all templates had already finished!

Do you know an example of isomorphic transformation which transforms some valid X-sudoku solution grids to other valid X-sudoku solution grids, but breaks X-property for the rest valid X-sudoku solution grids?

Yes, I believe that I did stumble across such cases. I will try and find some examples for you.

Cheers!