SudokuW/SudokuWX (Windoku)

For fans of Killer Sudoku, Samurai Sudoku and other variants

SudokuW/SudokuWX (Windoku)

Postby Mathimagics » Tue Aug 21, 2018 3:59 pm

I have done some preliminary work on the Windoku variant, which I will refer to as SudokuW, and the diagonal extension as SudokuWX, in keeping with the other variant names we have used (SudokuP, SudokuPX, SudokuX etc).

SudokuW is a bit like SudokuP, but we add only 4 constraints to the standard 27, not 9. One constraint ("house") for each of the 4 "Window Boxes".

The number of different SudokuW grids is, as far as I can tell, 17,463,553,760 x 9! (relabelling factor). This was done by brute-force, I identified 544 templates for placing the "1"'s (with r1,c1 = 1 fixed), and counted all the solutions for each. This could have been made more efficient by using equivalence classes, but it only took a few hours in any case.

There are 128 SudokuW-preserving transformations (WPT) among the standard Sudoku transformations. For example, swapping R2/R3 and/or C2/C3, ditto for R7/R8, C7/C8. There are 16 ways to do these corner-fiddles, times 8 for rotation/reflection.

To count EDW = number of ED grids, my guess is under 200 million. The exact figure can be arrived at in two ways. Most efficient is the Burnside's Lemma calculation, and I am hoping that perhaps blue will do this, as he did for SudokuPX. I will arrive at (hopefully) the same number by the slow method, ie generating all solutions & reducing them via canonicalisation (a suitable impetus for optimising my canonicaliser function!).

As far as MNC (min number of clues), well it's early days, but we do have several 12-clue cases identified already, one is shown below. No 11-clue puzzles so far ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuW/SudokuWX (Windoku)

Postby Mathimagics » Tue Aug 21, 2018 4:03 pm

.
A 12-clue SudokuW (Windoku):

SudokuW-12C.jpg
SudokuW-12C.jpg (20.75 KiB) Viewed 119 times


Some further examples (not canonicalised):
Hidden Text: Show
Code: Select all
.2.3..................9......4.................7............8..6..1.4.9..5.....3.: 826345179491867325375291648234619587518472963967583214742936851683154792159728436
.2.3..................9..5...4.................7............8..6....4.9..5.....3.: 128345679395167248476298351234859167561472983987613524742936815613584792859721436
.2.3................1.9......4.................7............8..6....4.9..5.....3.: 826341579495867321371295648234659187518472963967183254742936815683514792159728436
.2.3.........9......1........4.................7............8..6....4.9..5.....3.: 826345179375291648491867325234619587518472963967583214742936851683154792159728436
.2.3.........9............5..4.................7............8..6....4.9..5.....3.: 826345179375291648491867325234619587518472963967583214742936851683154792159728436
.2.3.......1.9...............4.................7............8..6....4.9..5.....3.: 826341579371295648495867321234659187518472963967183254742936815683514792159728436
.2.3.......1.9...............4...3.............7...........28.......4.9..5.......: 429351768671298543835647921584926317316475289297183654943512876762834195158769432
.2.3.......1.9...............4.2.3.............7............8.......4.9..5.......: 429351768671298543835647921584926317316475289297183654943512876762834195158769432
.2.3......6..9..1..........8.4...3.............7............8.........9..5.......: 928371654463895217175264983894127365516439728237586149341952876782643591659718432
.2.3......1..9..6..........8.4...3.............7............8.........9..5.......: 928376154413895267675214983894627315561439728237581649346952871782143596159768432
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

SudokuWX (WindokuX)

Postby Mathimagics » Tue Aug 21, 2018 4:29 pm

.
For SudokuWX we have 144 valid templates, from which we determined that there are just 2,580,728 different grids (x 9! for relabelling).

We have just 16 SudokuWX-preserving transformations among the standard Sudoku set. The "corner-fiddling" options are reduced to just 1, ie swap R2,R3 and C2,C3 and R7,R8 and C7,C8, x 8 for reflection/rotation.

The number of EDWX grids is quickly (if unsubtly) arrived at, and it is just 161,991.

So these 4 "window" constraints seem to be far more effective at reducing solutions than the 9 x SudokuP constraints, and when combined with diagonal constraints, we might expect to find a MNC value less than that of SudokuPX.

10-clue SudokuWX puzzles are certainly common - I have been running a single random morph-walker for just 24 hours and it has already hit over 14% of the EDWX grids - 22,687 grids, 51,036 puzzles when last checked. So it looks to me as though we could well find that a majority of EDWX grids have 10-clue puzzles.

Sadly, though, every one of those 12-clue puzzles is minimal, so no sign yet of an 11-clue puzzle! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuW/SudokuWX (Windoku)

Postby blue » Tue Aug 21, 2018 11:56 pm

Hi Mathimagics,

I've confirmed your two "big" numbers: 17,463,553,760 x 9! grids, for Windoku, and 2,580,728 x 9! for X-Windoku.
I've done the "Burnside Lemma thing" too, but and my results are ~half of yours: 68,239,994 and 81,571 (for ED grid counts).
You're missing a not-too-obvious transformation (again), that causes the VPT group sizes to double, and ED counts to ~half.

See the opening post here, and follow the link.
It should make what comes next, easier to understand.

The missing transformation ... "W" call it, for lack of a better name ... swaps rows 1&4 and 6&9, and columns 1&4 and 6&9.
It maps rows to rows, columns to columns, diagonals to diagonals, and it swaps boxes for "windows" (including the 5 "ghost" windows).

Code: Select all
1 1 1 2 2 2 3 3 3          5 4 4 4 5 6 6 6 5
1 1 1 2 2 2 3 3 3          2 1 1 1 2 3 3 3 2
1 1 1 2 2 2 3 3 3          2 1 1 1 2 3 3 3 2
4 4 4 5 5 5 6 6 6          2 1 1 1 2 3 3 3 2
4 4 4 5 5 5 6 6 6   <-->   5 4 4 4 5 6 6 6 5
4 4 4 5 5 5 6 6 6          8 7 7 7 8 9 9 9 8
7 7 7 8 8 8 9 9 9          8 7 7 7 8 9 9 9 8
7 7 7 8 8 8 9 9 9          8 7 7 7 8 9 9 9 8
7 7 7 8 8 8 9 9 9          5 4 4 4 5 6 6 6 5
blue
 
Posts: 684
Joined: 11 March 2013

Re: SudokuW/SudokuWX (Windoku)

Postby Mathimagics » Wed Aug 22, 2018 3:49 am

.
Thanks, blue, well done!

I tried really hard to come up with a non-standard transformation that might apply, but failed. I really thought that the SudokuP transforms were a one-off ... I should have known better!

It shouldn't take me long to confirm your revised figures and reduce my catalog accordingly ... I was just about to report my count of 136,366,657 for the number of ED W-grids.

Cheers! 8-)
M
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuW/SudokuWX (Windoku)

Postby Mathimagics » Wed Aug 22, 2018 4:03 am

.
Ok, I see that the ghost windows are true 9-sets, and so SudokuW (Windoku) is really just a different partitioning of the grid to that used by SudokuP. These variants are thus much more closely related than I had realised.
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuW/SudokuWX (Windoku)

Postby blue » Wed Aug 22, 2018 4:21 am

I was surprised that SudokuWX had such a low ED grid count, compared with SudokuPX.
I wonder what that means, regarding the possiblity of 8-clue puzzles,

Mathimagics wrote: ... I was just about to report my count of 136,366,657 for the number of ED W-grids.

Did you copy the right number ?
I matched your 161,991 number for "WX", using the smaller VPT group, but for "W", I get 136,439,416.

Cheers.
blue
 
Posts: 684
Joined: 11 March 2013

Re: SudokuW/SudokuWX (Windoku)

Postby Mathimagics » Wed Aug 22, 2018 5:07 am

blue wrote:I was surprised that SudokuWX had such a low ED grid count, compared with SudokuPX.
I wonder what that means, regarding the possiblity of 8-clue puzzles

Random morph walker found SudokuP 11-clue puzzles and SudokuPX 9-clue puzzles quickly, as non-minimal 12-clue/10-clue cases.

But for SudokuWX, while it has already found 85,732 10-clue puzzles, on 30,828 (19% of ED grids based on my uncorrected CF function) they are all minimal. So the signs are not good, even for 9-clue puzzles.

blue wrote:Did you copy the right number ? I matched your 161,991 number for "WX", using the smaller VPT group, but for "W", I get 136,439,416.


Oh dear, it looks like I missed a class! :?

Can you provide your list of W-equivalence classes, ie the number of members and grid counts for each class? That would help me track down the missing items. I just matched them by same number of solutions for a template, and took one of each.
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuW/SudokuWX (Windoku)

Postby blue » Wed Aug 22, 2018 6:57 am

Can you provide your list of W-equivalence classes, ie the number of members and grid counts for each class? That would help me track down the missing items. I just matched them by same number of solutions for a template, and took one of each.

I hope this is what you were looking for.
There were 40 template classes, each with a different number of completions.

Hidden Text: Show
Code: Select all
t( 1):   32  33935000  .1............1...........1..1..........1..........1..1...........1............1.
t( 2):   64  18579487  .1..........1...........1..1............1............1..1...........1..........1.
t( 3):   64  19092051  .1..........1...........1..1............1...........1...1..............1.....1...
t( 4):  128  14012703  .1..........1...........1..1............1............1..1.............1......1...
t( 5):  128  20985405  .1..........1...........1..1.............1..........1...1..............1....1....
t( 6):  128  18135497  .1..........1...........1..1.............1...........1..1.............1.....1....
t( 7):  128  37865805  .1..........1...........1......1............1..1......1.............1..........1.
t( 8):  128  20779103  .1..........1...........1......1............11..........1...........1..........1.
t( 9):  256  31043228  1...........1...........1......1...........1..1............1...........1..1......
t(10):   64  46336450  1.............1...........1...1...........1...1...........1...........1...1......
t(11):  128  38620044  1............1..........1.....1............1..1............1...........1..1......
t(12):  256  24959548  .1..........1...........1......1............1..1......1...............1......1...
t(13):  256  15947238  .1..........1...........1......1............11..........1.............1......1...
t(14):  256  41862167  1...........1.............1......1...1...........1......1...........1..........1.
t(15):  256  23361647  1...........1...........1..........1.1...........1......1...........1..........1.
t(16):  128  55694155  1...........1.............1......1...1............1.....1..........1...........1.
t(17):  128  27979333  1...........1...........1..........1.1............1.....1..........1...........1.
t(18):  256  28253552  1...........1.............1......1...1...........1......1.............1......1...
t(19):  256  17255013  1...........1...........1..........1.1...........1......1.............1......1...
t(20):   32  59035773  .1..........1.............1......1......1......1......1.............1..........1.
t(21):  128  31858885  .1..........1...........1..........1....1......1......1.............1..........1.
t(22):   64  17510912  .1..........1...........1..........1....1....1..........1...........1..........1.
t(23):  256  36327606  1...........1.............1......1.......1....1...........1...........1...1......
t(24):  256  24815514  1...........1...........1..........1.....1....1...........1...........1...1......
t(25):  128  21036397  .1..........1...........1..........1....1......1......1...............1......1...
t(26):  128  13641069  .1..........1...........1..........1....1....1..........1.............1......1...
t(27):  128  18053266  .1..........1...........1..........1.....1...1..........1.............1.....1....
t(28):  128  20912145  .1..........1...........1..1................1....1......1...........1..........1.
t(29):  128  17924631  .1..........1...........1..1................1....1......1.............1......1...
t(30):  256  23987112  1...........1...........1......1.....1...............1..1...........1..........1.
t(31):  256  45923655  1...........1.............1.....1....1.............1....1..........1...........1.
t(32):  256  23774953  1...........1...........1......1.....1..............1...1..............1.....1...
t(33):  256  17111442  1...........1...........1......1.....1...............1..1.............1......1...
t(34):  128  30341725  1............1..........1.....1......1..............1...1..............1.....1...
t(35):   64  20586058  1............1..........1.....1......1...............1..1.............1......1...
t(36):  128  14600673  .1..........1...........1......1....1................1..1.............1......1...
t(37):   32  10041474  ...1......1.............1..1............1............1..1.............1......1...
t(38):  128  13711170  ...1......1.............1..1.............1...........1..1.............1.....1....
t(39):  128  13162554  ...1......1.............1......1............11..........1.............1......1...
t(40):   32  10162692  ...1......1.............1..........1....1....1..........1.............1......1...
blue
 
Posts: 684
Joined: 11 March 2013

Re: SudokuW/SudokuWX (Windoku)

Postby Mathimagics » Wed Aug 22, 2018 7:30 am

blue wrote:I hope this is what you were looking for.
There were 40 template classes, each with a different number of completions.


Thank you, that was exactly what I was looking, for. I had simply counted completions for each template and then assumed the counts were different for each equiv class, which turned out to be the case. So I built the full set for one template from each class, then used CF function + Sort/Merge ops to build the catalog.

I thought maybe two different clases might have had the same completion counts (not impossible), and that would tell me where to look for the missing items.

But its all moot now, since after rebuilding with the new transformation list, I found I had 68,239,994 ED grids.

And for SudokuWX I now have 81,571
Concordance is bliss! 8-)
Last edited by Mathimagics on Wed Aug 22, 2018 7:45 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuW/SudokuWX (Windoku)

Postby blue » Wed Aug 22, 2018 7:45 am

Mathimagics wrote:But its all moot now, since after rebuilding with the new transformation list, I found I had 68,239,994 ED grids.

Concordance is bliss! 8-)

Sweet :!:

I thought maybe two different clases might have had the same completion counts (not impossible), and that would tell me where to look for the missing items.

I realized just before your last post, that the table above, was for the full VPT group.
With the smaller group, there were 53 classes, and yes, some duplicate completion counts.
For completeness, here's the table I should have posted.

Hidden Text: Show
Code: Select all
t( 1):   32  33935000  .1............1...........1..1..........1..........1..1...........1............1.
t( 2):   64  18579487  .1..........1...........1..1............1............1..1...........1..........1.
t( 3):   64  19092051  .1..........1...........1..1............1...........1...1..............1.....1...
t( 4):  128  14012703  .1..........1...........1..1............1............1..1.............1......1...
t( 5):  128  20985405  .1..........1...........1..1.............1..........1...1..............1....1....
t( 6):  128  18135497  .1..........1...........1..1.............1...........1..1.............1.....1....
t( 7):  128  37865805  .1..........1...........1......1............1..1......1.............1..........1.
t( 8):  128  20779103  .1..........1...........1......1............11..........1...........1..........1.
t( 9):  128  31043228  1...........1...........1......1...........1..1............1...........1..1......
t(10):   64  46336450  1.............1...........1...1...........1...1...........1...........1...1......
t(11):  128  45923655  1...........1.............1.....1.........1...1...........1...........1...1......
t(12):  128  38620044  1............1..........1.....1............1..1............1...........1..1......
t(13):  128  24959548  .1..........1...........1......1............1..1......1...............1......1...
t(14):  128  41862167  .1..........1.............1.....1.........1....1......1...............1.....1....
t(15):  128  15947238  .1..........1...........1......1............11..........1.............1......1...
t(16):  128  28253552  .1..........1.............1.....1.........1..1..........1.............1.....1....
t(17):  128  17255013  .1...........1..........1.....1.............11..........1.............1......1...
t(18):  128  41862167  1...........1.............1......1...1...........1......1...........1..........1.
t(19):  128  23361647  1...........1...........1..........1.1...........1......1...........1..........1.
t(20):  128  55694155  1...........1.............1......1...1............1.....1..........1...........1.
t(21):  128  27979333  1...........1...........1..........1.1............1.....1..........1...........1.
t(22):  128  23361647  .1..........1...........1..........11.............1.....1..........1...........1.
t(23):  128  28253552  1...........1.............1......1...1...........1......1.............1......1...
t(24):  128  17255013  1...........1...........1..........1.1...........1......1.............1......1...
t(25):  128  15947238  .1..........1...........1..........11............1......1.............1......1...
t(26):   32  59035773  .1..........1.............1......1......1......1......1.............1..........1.
t(27):  128  31858885  .1..........1...........1..........1....1......1......1.............1..........1.
t(28):   64  17510912  .1..........1...........1..........1....1....1..........1...........1..........1.
t(29):  128  36327606  1...........1.............1......1.......1....1...........1...........1...1......
t(30):  128  24815514  1...........1...........1..........1.....1....1...........1...........1...1......
t(31):  128  21036397  .1..........1...........1..........1....1......1......1...............1......1...
t(32):  128  24959548  .1..........1...........1..........1.....1.....1......1...............1.....1....
t(33):  128  13641069  .1..........1...........1..........1....1....1..........1.............1......1...
t(34):  128  18053266  .1..........1...........1..........1.....1...1..........1.............1.....1....
t(35):  128  31043228  .1...........1..........1....1..............1.....1...1...........1............1.
t(36):  128  20912145  .1..........1...........1..1................1....1......1...........1..........1.
t(37):  128  23987112  .1..........1...........1..1................1.....1.....1..........1...........1.
t(38):  128  24815514  .1...........1..........1....1..............1...1.....1...............1......1...
t(39):  128  17924631  .1..........1...........1..1................1....1......1.............1......1...
t(40):  128  23774953  .1..........1...........1..1...............1......1.....1..............1....1....
t(41):  128  23987112  1...........1...........1......1.....1...............1..1...........1..........1.
t(42):  128  45923655  1...........1.............1.....1....1.............1....1..........1...........1.
t(43):  128  36327606  .1..........1.............1.....1...1..............1....1..........1...........1.
t(44):  128  23774953  1...........1...........1......1.....1..............1...1..............1.....1...
t(45):  128  17111442  1...........1...........1......1.....1...............1..1.............1......1...
t(46):  128  30341725  1............1..........1.....1......1..............1...1..............1.....1...
t(47):   64  20586058  1............1..........1.....1......1...............1..1.............1......1...
t(48):  128  14600673  .1..........1...........1......1....1................1..1.............1......1...
t(49):  128  17111442  .1...........1..........1.....1.....1................1..1.............1......1...
t(50):   32  10041474  ...1......1.............1..1............1............1..1.............1......1...
t(51):  128  13711170  ...1......1.............1..1.............1...........1..1.............1.....1....
t(52):  128  13162554  ...1......1.............1......1............11..........1.............1......1...
t(53):   32  10162692  ...1......1.............1..........1....1....1..........1.............1......1...
blue
 
Posts: 684
Joined: 11 March 2013

Re: SudokuW/SudokuWX (Windoku)

Postby Mathimagics » Wed Aug 22, 2018 8:39 am

.

Morph walker 10-clue search has now hit over 28% of the ED SudokuWX grids. 23078 grids, 95164 puzzles, all minimal
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuW/SudokuWX (Windoku)

Postby Mathimagics » Wed Aug 22, 2018 8:44 am

blue wrote:With the smaller group, there were 53 classes, and yes, some duplicate completion counts.
For completeness, here's the table I should have posted.


This made me pause a bit. How did I get the correct results?

Probably because I only used templates with 1 in R1,C1. These have distinct completion counts ....
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

SudokuW/SudokuWX Solver Tables

Postby Mathimagics » Wed Aug 22, 2018 11:30 am

.
http://www.sudokuwiki.org/Windoku_Strategy

It is worth noting that it is not just human solvers that benefit from the "ghost windows".

In SudokuWX mode, when configured for 33 constraints (9R + 9C + 9B + 4W + 2D), my fsss2 solver takes 190s to solve the 200,000 x 10-clue minimal puzzles found so far.

When configured for the full 38 constraints (9R + 9C + 9B + 9W + 2D), it takes only 44s.

In SudokuW mode, the difference is even more pronounced. For 200,000 x 12-clue minimal puzzles the solver takes 100s when only 31 constraints are used, but just 3s when all 36 are used.
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuW/SudokuWX (Windoku)

Postby tarek » Wed Aug 22, 2018 1:23 pm

If you have singles +/- locked sets assisted recursive solvers then any hidden constraints will be extremely helpful.

This will be helpful also in designing puzzles that require (or don’t require) certain windows to solve with ease!!!

Tarek
User avatar
tarek
 
Posts: 2698
Joined: 05 January 2006

Next

Return to Sudoku variants