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 ...
SudokuW/SudokuWX (Windoku)
51 posts
• Page 1 of 4 • 1, 2, 3, 4
SudokuW/SudokuWX (Windoku)
by Mathimagics » Tue Aug 21, 2018 3:59 pm
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: SudokuW/SudokuWX (Windoku)
by Mathimagics » Tue Aug 21, 2018 4:03 pm
.
A 12-clue SudokuW (Windoku):
Some further examples (not canonicalised):
A 12-clue SudokuW (Windoku):
- SudokuW-12C.jpg (20.75 KiB) Viewed 1835 times
Some further examples (not canonicalised):
Hidden Text: Show
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
SudokuWX (WindokuX)
by 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!
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!
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: SudokuW/SudokuWX (Windoku)
by 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).
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: 1052
- Joined: 11 March 2013
Re: SudokuW/SudokuWX (Windoku)
by 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!
M
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!
M
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: SudokuW/SudokuWX (Windoku)
by 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.
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.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: SudokuW/SudokuWX (Windoku)
by 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,
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.
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: 1052
- Joined: 11 March 2013
Re: SudokuW/SudokuWX (Windoku)
by 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.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: SudokuW/SudokuWX (Windoku)
by 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
- blue
- Posts: 1052
- Joined: 11 March 2013
Re: SudokuW/SudokuWX (Windoku)
by 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!
Last edited by Mathimagics on Wed Aug 22, 2018 7:45 am, edited 1 time in total.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: SudokuW/SudokuWX (Windoku)
by 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!
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
- blue
- Posts: 1052
- Joined: 11 March 2013
Re: SudokuW/SudokuWX (Windoku)
by 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
Morph walker 10-clue search has now hit over 28% of the ED SudokuWX grids. 23078 grids, 95164 puzzles, all minimal
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: SudokuW/SudokuWX (Windoku)
by 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 ....
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
SudokuW/SudokuWX Solver Tables
by 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.
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.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: SudokuW/SudokuWX (Windoku)
by 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
This will be helpful also in designing puzzles that require (or don’t require) certain windows to solve with ease!!!
Tarek
-
tarek - Posts: 3762
- Joined: 05 January 2006
51 posts
• Page 1 of 4 • 1, 2, 3, 4
