The New Sudoku Players' Forum

[Mathimagics]

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 #  288
123869457456237891789451236542793618967148523831526749278915364314672985695384172 #  192
123869457456237891789451236542793618967148523831526749278914365315672984694385172 #  192
123869457456237891789451236845723619967148523231596748578912364312674985694385172 #  192
123869457456237891789451236245793618967148523831526749578912364312674985694385172 #  192
123698457456237891789451236264873915875149623931526784548712369312964578697385142 #  192
123698457456237891789451236962873514875149623341526789298714365514362978637985142 #  192
123698457456237891789451236964823715275149683831576924548712369312964578697385142 #  192


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

[blue]

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.

[Mathimagics]

.
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]

.
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: 123869457456237891789451236842793615567148923931526748278915364314672589695384172
X2: 346287915127659384598341672475132869263798451819465237651824793932576148784913526
X3: 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]

.
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 |
  +-------+-------+-------+


[champagne]

.
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

[Mathimagics]

.
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!

[champagne]

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)

[Mathimagics]

.
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]

.
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.

[Serg]

Hi, 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.

I am very impressed by your speed. To solve such rather complicated problem in several days !

"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.

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]

Hi, Mathimagics!

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: 123869457456237891789451236842793615567148923931526748278915364314672589695384172
X2: 346287915127659384598341672475132869263798451819465237651824793932576148784913526
X3: 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

[Mathimagics]

.
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.

[Mathimagics]

Helloo Serg!

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

[champagne]

.
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 |
  +-------+-------+-------+

your starting solution grid

In each box, the possible diagonal triplets

Code: Select all

box1 159 278 346      167 249 358
box2 248 167 359      479 125 368
box3 247 568 139      259 167 348
box4 257 169 348      479 135 268
box5 159 247 368      679 123 458
box6 467 138 259      248 356 179
box7 259 378 146      179 236 458
box8 258 147 369      249 567 138
box9 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 169
boxes 168   346 179 258      249 138 567
boxes 267   248 356 179       
boxes 249  empty
boxes 348  empty
boxes 357  empty

only possibilities to have a valid status in the central box

Code: Select all

boxes 159   358 247 169
boxes 168   346 179 258   

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

Code: Select all

boxes 168   249 138 567
boxes 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