## SudokuX (Diagonal Sudoku)

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: SudokuX (Diagonal Sudoku)

Serg wrote: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?

Ok, let us call the set of 96 X-preserving transformations {X}, so that if G is SudokuX, then X[k](G) is SudokuX, for all k = 1 ... 96. Let's call such a set of 96 grids an "X-set".

Now, let {S} denote the set of standard Sudoku transformations, and let G be some SudokuX grid. You want a transformation S[j] (not in {X}) which for some SudokuX grids produces another SudokuX grid, but not always.

If H = S[j](G), and H is SudokuX, and S[j] is not in {X}, then clearly the equivalence class defined by {S} contains more than one "X-set".

For each X-set, there are 96 transformations that will convert members of one X-set to another, but will not always do so for SudokuX grids which are not in this equivalence class (ie are ED wrt G).

So these "X-set linking" transformations have the desired property. Also, they are the only cases possible, since no transformation in {S} can turn a SudokuX grid G into another SudokuX which is not isomorphic to G.

Here are some grids with more than one X-set. The number of SudokuX isotopes is indicated for each:
Code: Select all
`123869457456237891789451236842793615567148923931526748278915364314672589695384172 #  288123869457456237891789451236542793618967148523831526749278915364314672985695384172 #  192123869457456237891789451236542793618967148523831526749278914365315672984694385172 #  192123869457456237891789451236845723619967148523231596748578912364312674985694385172 #  192123869457456237891789451236245793618967148523831526749578912364312674985694385172 #  192123698457456237891789451236264873915875149623931526784548712369312964578697385142 #  192123698457456237891789451236962873514875149623341526789298714365514362978637985142 #  192123698457456237891789451236964823715275149683831576924548712369312964578697385142 #  192`

I haven't yet looked at the transformations involved. Nor do I yet know the maximum number of X-sets.

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

Mathimagics wrote:
blue wrote: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.

Yes, I forgot about that "agreement". I said in that thread, that it was something I would never have agreed to.
I don't like the idea, any more than I would like the idea of saying that two vanilla Sudoku grids are "not ED", when one can be transformed into the other using a transformation that preserves the validity of Latin squares, but destroys it for one or more Sudoku grids.
No point in rehashing that, though, except to say that I'll probably almost always forget, and use "ED" in a context-dependent sense.

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

I used the same approach that Russell and Jarvis used, but applied to the case of X-Sudoku grids, with thier 96 "VPTs".
The VPTs, split into 30 conjugacy classes. Only 8 of the (29) "non-trivial" classes, had one or more grids that were left invariant, and the largest grid count among those, was 1,675,008.

I used "templates", and code similar to what Red Ed described here, to count the number of "X" grids that are left invariant by a given VPT. I added some "speedup" features:
• After the initial lists of "extended templates" were built, if any of them was empty, the VPT (its "class") was skipped.
• Before the outer loop was entered: for each d > 1, the list of extended templates for "row 1, column d", was filtered to remove any cases that included a cell in a column "< d".
• Before each "next inner" loop, the relevant lists were filtered again, to remove any cases that overlapped the union of the templates from the current and outer loops. A fresh set of lists was produced for each depth ... each a filtered version of the corresponding list for the current depth.
To get the "153,255,603,504" count, I did what you did, essentially, with two exceptions:
• I used what could be called a "template-based" solver ... based on the code described above, but with normal, rather than "extended templates".
• For "seed", rather than using the 1040 templates that contain r1c1, I used a list of 115 (X-) canonical templates, and multiplied the "solution counts" by the number of templates having the relevant canonical form, before adding the results.
• The seed templates were in maxlex canonical form. That complicated things slightly, since 95 of them included r1c1 (in row 1), and the remaining 20, included r1c2.
blue

Posts: 967
Joined: 11 March 2013

### Re: SudokuX (Diagonal Sudoku)

.
Ok, elegant work indeed, as usual!

You used a bespoke surgical instrument, while I just hit it with a sledgehammer (well, 4 sledgehammers, each used 260 times) ...

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

.
For Serg,

Here is the grid listed above as having 288 X-transformations, ie 3 x X-Sets, with a representative grid from each set:

Code: Select all
`X1: 123869457456237891789451236842793615567148923931526748278915364314672589695384172X2: 346287915127659384598341672475132869263798451819465237651824793932576148784913526X3: 276589143519364782483172956732891564968457231154236897397615428841923675625748319`

Display format:
Hidden Text: Show
Code: Select all
`             X1                            X2                            X3  +-------+-------+-------+     +-------+-------+-------+     +-------+-------+-------+  | 1 2 3 | 8 6 9 | 4 5 7 |     | 3 4 6 | 2 8 7 | 9 1 5 |     | 2 7 6 | 5 8 9 | 1 4 3 |  | 4 5 6 | 2 3 7 | 8 9 1 |     | 1 2 7 | 6 5 9 | 3 8 4 |     | 5 1 9 | 3 6 4 | 7 8 2 |  | 7 8 9 | 4 5 1 | 2 3 6 |     | 5 9 8 | 3 4 1 | 6 7 2 |     | 4 8 3 | 1 7 2 | 9 5 6 |  +-------+-------+-------+     +-------+-------+-------+     +-------+-------+-------+  | 8 4 2 | 7 9 3 | 6 1 5 |     | 4 7 5 | 1 3 2 | 8 6 9 |     | 7 3 2 | 8 9 1 | 5 6 4 |  | 5 6 7 | 1 4 8 | 9 2 3 |     | 2 6 3 | 7 9 8 | 4 5 1 |     | 9 6 8 | 4 5 7 | 2 3 1 |  | 9 3 1 | 5 2 6 | 7 4 8 |     | 8 1 9 | 4 6 5 | 2 3 7 |     | 1 5 4 | 2 3 6 | 8 9 7 |  +-------+-------+-------+     +-------+-------+-------+     +-------+-------+-------+  | 2 7 8 | 9 1 5 | 3 6 4 |     | 6 5 1 | 8 2 4 | 7 9 3 |     | 3 9 7 | 6 1 5 | 4 2 8 |  | 3 1 4 | 6 7 2 | 5 8 9 |     | 9 3 2 | 5 7 6 | 1 4 8 |     | 8 4 1 | 9 2 3 | 6 7 5 |  | 6 9 5 | 3 8 4 | 1 7 2 |     | 7 8 4 | 9 1 3 | 5 2 6 |     | 6 2 5 | 7 4 8 | 3 1 9 |  +-------+-------+-------+     +-------+-------+-------+     +-------+-------+-------+`

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

.
Hi champagne,

I am having trouble using your method to find a SudkuX morph for the following grid. But they do exist.

It seems that more complex operations are required, although I might well have made a mistake somewhere.

Could you take look at it?

[ EDIT ] It looks like I have made an elementary mistake, once again. I have found the mapping, and am looking at how I managed to miss it!

Hidden Text: Show
Code: Select all
`123456789457189326869372514214537698376298145985641237531864972698723451742915863  +-------+-------+-------+  | 1 2 3 | 4 5 6 | 7 8 9 |  | 4 5 7 | 1 8 9 | 3 2 6 |  | 8 6 9 | 3 7 2 | 5 1 4 |  +-------+-------+-------+  | 2 1 4 | 5 3 7 | 6 9 8 |  | 3 7 6 | 2 9 8 | 1 4 5 |  | 9 8 5 | 6 4 1 | 2 3 7 |  +-------+-------+-------+  | 5 3 1 | 8 6 4 | 9 7 2 |  | 6 9 8 | 7 2 3 | 4 5 1 |  | 7 4 2 | 9 1 5 | 8 6 3 |  +-------+-------+-------+`
Last edited by Mathimagics on Sun Aug 05, 2018 2:45 pm, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

Mathimagics wrote:.
Hi champagne,

I am having trouble using your method to find a SudkuX morph for the following grid. But they do exist.

It seems that more complex operations are required, although I might well have made a mistake somewhere.

Could you take look at it?

[code]
123456789457189326869372514214537698376298145985641237531864972698723451742915863

Yes but as I don't have code to do it, can you post one existing X sudoku. I'll have a look anyway
champagne
2017 Supporter

Posts: 7324
Joined: 02 August 2007
Location: France Brittany

### Re: SudokuX (Diagonal Sudoku)

.
Looks like we posted/edited simultaneously ...

I think I can resolve this one, if I get stuck again I'll let you know (and include the known X-grid).

Thanks!

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

after a preliminary step, I find (by hand) 2 cases to study

box 1 as central box digit "3" in r5c5
box 6 as central box digit "3" in r5c5 again

I'll continue, but a first crosscheck could help (example of one solution)
champagne
2017 Supporter

Posts: 7324
Joined: 02 August 2007
Location: France Brittany

### Re: SudokuX (Diagonal Sudoku)

.
Here is one solution (first SudokuX found with TransformableX function):

Code: Select all
`X = 683427195792315684541986273236574819879231546154698732327859461415763928968142357 6 8 3 | 4 2 7 | 1 9 5 7 9 2 | 3 1 5 | 6 8 4 5 4 1 | 9 8 6 | 2 7 3 ------+-------+------ 2 3 6 | 5 7 4 | 8 1 9 8 7 9 | 2 3 1 | 5 4 6 1 5 4 | 6 9 8 | 7 3 2 ------+-------+------ 3 2 7 | 8 5 9 | 4 6 1 4 1 5 | 7 6 3 | 9 2 8 9 6 8 | 1 4 2 | 3 5 7`

It's a standard corner pattern with box 1 moving to the center, but it seems to have different row/col permutations in bands ,3 and stacks 1,3

So it looks like we need to test all 36^2 = 1296 such permutations for the corner box diagonals it seems ...

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

.
In which case I"m probably going the wrong way about it by enumerating corners first, then testing central box for fit.

It would be better to enumerate the central box first, each possibility providing 3 forbidden-digits in each diagonal, which permits a more efficient test of the corner permutations.

[ EDIT ] Handling all permutations of bands 1/3 and stacks 1/3 fixed the immediate problem. I know have that grid correctly identified. Will move on to test a bigger set.
Last edited by Mathimagics on Sun Aug 05, 2018 4:23 pm, edited 2 times in total.

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

Hi, blue!
blue wrote:
Mathimagics wrote: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.

I am very impressed by your speed. To solve such rather complicated problem in several days !
blue wrote:"Orbit connection problem"?
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 agree with you. I think "Orbit connection problem" does exist, but applies to patterns enumeration, not to solution grids enumeration (I am planning to publish separate post concerning this theme). So, I think Burnside's Lemma can be used for ED X-sudoku solution grids enumeration.
blue wrote: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.

Awesome!

Serg
Serg
2018 Supporter

Posts: 858
Joined: 01 June 2010
Location: Russia

### Re: SudokuX (Diagonal Sudoku)

Hi, Mathimagics!
Mathimagics wrote:Here is the grid listed above as having 288 X-transformations, ie 3 x X-Sets, with a representative grid from each set:

Code: Select all
`X1: 123869457456237891789451236842793615567148923931526748278915364314672589695384172X2: 346287915127659384598341672475132869263798451819465237651824793932576148784913526X3: 276589143519364782483172956732891564968457231154236897397615428841923675625748319`

Thank you for examples! But I don't see the most interesting thing - what "in doubt" transformations are applicable to these grids and to what resulting grids they are transformed?

Serg
Serg
2018 Supporter

Posts: 858
Joined: 01 June 2010
Location: Russia

### Re: SudokuX (Diagonal Sudoku)

.
I hate to disturb this love-in ....

But ...

For the record, it was Serg, if I recall correctly, who explained to me in great detail why he thought he number of ED (aka S-different) SudokuP grids could not be established using Burnsides' Lemma counting method because there are S-transformations that produce SudokuP grids from non-SudokuP grids, and vice-versa.

Once I understood tha group theory behind this argument, it made perfect sense.

If my use of the term "Orbit connection Problem" is incorrect or inappropriate, I will cease using it, but what I was referring to was precisely this group theoretic argument, and you can't argue with the math!

Exactly the same argument applies to SudokuX. You can't use Burnside directly, we need an explicit enumeration (or reduction) method.

For SudokuP that was easy, and now that blue's excellent work has produced a result, 1.5 billion X-different (or ED in blue-speak) grids, I am hoping he will share either code or data (*) to let us generate and reduce this set to S-different, even though I know he hates this definition!

If I wasn't doing so many other things at the moment, I would be happy to simply reproduce his results from scratch, but I am fully booked through to Xmas ...

(*) Actually that may not be necessary, if our method champenoise comes to fruition ... if it's fast enough I might be able to extract this data from the Sudoku ED catalog.
Last edited by Mathimagics on Sun Aug 05, 2018 5:03 pm, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

Helloo Serg!

Serg wrote:Thank you for examples! But I don't see the most interesting thing - what "in doubt" transformations are applicable to these grids and to what resulting grids they are transformed?

The only consistent set of transformations is the 96 transformation , ie {X}. Since each X-set is in the same (Sudoku) equivalence class, there are millions of transformations that will make a SudokuX into a non-SudokuX. There are also 96 connection transforms that map one X-set to another (within the equivalence class). But these will vary from class to class, I would imagine.

I'm not sure exactly what you would like to see. In my discussion with champagne above, you will find an example of non-SudokuX to SudokuX transformation, and I can provide that specific transformation, if that's what you want?

Cheers

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuX (Diagonal Sudoku)

Mathimagics wrote:.
Here is one solution
Code: Select all
` 6 8 3 | 4 2 7 | 1 9 5 7 9 2 | 3 1 5 | 6 8 4 5 4 1 | 9 8 6 | 2 7 3 ------+-------+------ 2 3 6 | 5 7 4 | 8 1 9 8 7 9 | 2 3 1 | 5 4 6 1 5 4 | 6 9 8 | 7 3 2 ------+-------+------ 3 2 7 | 8 5 9 | 4 6 1 4 1 5 | 7 6 3 | 9 2 8 9 6 8 | 1 4 2 | 3 5 7`

It's a standard corner pattern with box 1 moving to the center, but it seems to have different row/col permutations in bands ,3 and stacks 1,3

So it looks like we need to test all 36^2 = 1296 such permutations for the corner box diagonals it seems ...

Hi Mathimagics,

Good news, it is one of my 2 possibilities.

Let me describe how very simply I came to this

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

In each box, the possible diagonal triplets

Code: Select all
`box1 159 278 346      167 249 358box2 248 167 359      479 125 368box3 247 568 139      259 167 348box4 257 169 348      479 135 268box5 159 247 368      679 123 458box6 467 138 259      248 356 179box7 259 378 146      179 236 458box8 258 147 369      249 567 138box9 359 246 178      258 347 169`

For the six possible diagonal (3 boxes not in the same band/stack), the valid 9 digits possibilities

Code: Select all
`boxes 159     358 247 169boxes 168   346 179 258      249 138 567boxes 267   248 356 179        boxes 249  empty boxes 348  emptyboxes 357  empty `

only possibilities to have a valid status in the central box

Code: Select all
`boxes 159   358 247 169boxes 168   346 179 258   `

central box is box 1 central digit is digit 3 (your solution)

Code: Select all
`boxes 168   249 138 567boxes 267   248 356 179      `

central box is box 6 central digit is "3"

From here, we know that band 1 stack 1 has to be morphed to the right diagonal pattern, then box1 moved to the central box, but this plays no role in the final check.

In fact, we have to check that we have a valid status in the four corners.

I did not check in details, but the process could be

Morph 1 of the four corners to have the right diagonal status
Check if it is still possible to morph the seen corners in the right way
and see if the fourth corner is ok

This is easy with the computer, but boring and subject to errors by hand
champagne
2017 Supporter

Posts: 7324
Joined: 02 August 2007
Location: France Brittany

PreviousNext