Jigsaws and Low ED Counts

For fans of Killer Sudoku, Samurai Sudoku and other variants

Jigsaws and Low ED Counts

Postby Mathimagics » Sat Mar 23, 2019 6:20 am

Definition: I will use NED as a generic term for the ED count, ie. the number of ED solution grids, for a given Sudoku variant. So NED for standard Sudoku is 5,472,730,538. NSG will denote the total number of solution grids.

Jigsaw Layouts (JL's) can be powerful constraints, reducing the solution space considerably compared to standard Sudoku with its 3x3 boxes. There is a distinct "catalog" of solutions for each different JL. Some Jigsaw layouts have no solutions at all, so for these NED = NSG = 0. One pet project of mine is to find some method of predicting which JL's have solutions, and which JL's are more constrained, etc. (By means other than solving them!)

Non-consecutive (NC) is another powerful constraint. For standard Sudoku, adding the NC constraint reduces the NED count by a factor of roughly 16,500, to just 330,845. Variant NC+ ("cyclic NC") adds the extra forbidden pair {1, 9}, and here NED is reduced to just 12,263.

The NC/NC+ variants also have the interesting property that the minimum number of clues required for a valid puzzle is greatly reduced, well below the 8-clue theoretical limit that applies to "normal" variants (ie SudokuP, SudokuX, SudokuJ etc without cell value restrictions). For standard Sudoku + NC, tarek and I have recently found 2 and 3 clue puzzles.

The recently discovered 1-clue puzzle is a "SudokuJ-NC" (a standard Jigsaw + NC constraints).

The Jigsaw layout for the 1-clue puzzle is actually not particularly constrained - solving it as a standard Sudoku Jigsaw, with one row, col, or region fixed, still gives over 1 billion solutions. But it is just enough for NC to give the 1-clue puzzle.

I have since learned that this puzzle, with no clues at all, has NSG = 4. The complete catalog is:

Code: Select all
135724968681379524246853179792418635357962481819537246463185792928641357574296813
318692475753146829297581364642735918184269753536814297971358642425973186869427531
792418635357964281813529746468375192926841357574296813139752468685137924241683579
975386142429731586864257931318692475753148629291573864647925318182469753536814297


The symmetry of the Jigsaw layout means that solutions #1 and #2 are essentially the same, just mirror images. The same goes for #3 and #4.

The only relabelling allowed under NC rules is a reversal of the cell values, ie {123456789} is replaced by {987654321}, so solution #1 and solution #4 are essentially the same, and so are #2 and #3.

So in fact there is only one "essentially different" solution: NED = 1. 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1272
Joined: 27 May 2015
Location: Canberra

Re: Jigsaws and Low ED Counts

Postby Hajime » Sat Mar 23, 2019 12:42 pm

Congratulations. So 0 clues and 1 real solution. What is the JS layout?
User avatar
Hajime
 
Posts: 75
Joined: 20 April 2018
Location: Netherlands

Re: Jigsaws and Low ED Counts

Postby Mathimagics » Sat Mar 23, 2019 2:47 pm

Hi Hajime,

The JL is given below ...

There is nothing special about it, and I would expect to find many others with the same property …

Cheers
MM

Code: Select all
BBBBBBBCCBBDAEECCCDDDAEECCCDDFAEEECGDDFAAAEGGDHFFFAEGGHHHFFAGGGHHHFFAGIIHHIIIIIII
User avatar
Mathimagics
2017 Supporter
 
Posts: 1272
Joined: 27 May 2015
Location: Canberra

Re: Jigsaws and Low ED Counts

Postby Mathimagics » Sat Mar 23, 2019 7:36 pm

Here is a case that is perhaps even more remarkable, as it has NSG = 2. (The smallest non-trivial "catalog" possible?)

The operations "rotate 180" and "relabel" (replace each digit D with 10 - D) produce identical results.

Code: Select all
BDDDDDDCCBBDDDCCCCBBBBEEECCBAAEEEEECBFAAAAAEIHFFFFFAAIHHFFFIIIIHHHHGGGIIHHGGGGGGI

158469372682714935425937168793582641316258497964825713249371586571693824837146259
952641738428396175685173942317528469794852613146285397861739524539417286273964851
User avatar
Mathimagics
2017 Supporter
 
Posts: 1272
Joined: 27 May 2015
Location: Canberra

Re: Jigsaws and Low ED Counts

Postby tarek » Sun Mar 24, 2019 5:41 pm

Excellent work. Certainly the FPs were the way to reach single clue puzzles. There has been some Jigsaw configurations that have managed to force many hidden constraints like the "Hands" variant which when combined with FP may give something similar.

I can sense now that quest for that 0 clue puzzle which obviously can't be achieved with symmetrical regions as you've demonstrated. :idea:

tarek
User avatar
tarek
 
Posts: 2971
Joined: 05 January 2006

Re: Jigsaws and Low ED Counts

Postby Mathimagics » Mon Mar 25, 2019 4:20 am

Hi tarek,

Yes, for clueless we will need to find the right combination of:
  • non-symmetric JL
  • FP settings that don't allow relabelling
  • a bit of luck

That luck is needed is demonstrated by this example:
Code: Select all
JL: GGGGGFFFFGAABGGGHFAABBCCCHFABBCCEEHFABCCDEHHFABCDDEHIFABCDEEHIIABDDEIHHIDDDEEIIII
FP: 14 15 16 27 35 37 69


This has just 2 solutions, with a simple UA4 spoiling the party:
Code: Select all
183946752791852643579421368267598431436785219318679524624317895852134976945263187
183946752791852643579421368267598431634785219318679524426317895852134976945263187
                                                      * *
User avatar
Mathimagics
2017 Supporter
 
Posts: 1272
Joined: 27 May 2015
Location: Canberra

Clueless (NSG = 1)

Postby Mathimagics » Mon Mar 25, 2019 5:07 am

Bingo! 8-)

It just needed a tweak to the JL above, and a little searching for an FP set that worked:
Code: Select all
JL: AAAAABBBBAACCAADEBFFCCDDDEBFCCDDGGEBFCDDHGEEBFCDHHGEIBFCHHGGEIIFFHHGIEEIFHHGGIIII
FP: 15 18 23 39 49 57 59 68

NSG = 1 :!:
Code: Select all
635214879973648521891763452389176245548921763452897316726589134164352987217435698


There should be 9! = 362880 equivalent clueless puzzles, each obtained by relabelling the FP set.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1272
Joined: 27 May 2015
Location: Canberra

Re: Jigsaws and Low ED Counts

Postby tarek » Mon Mar 25, 2019 6:17 pm

Wow, well done again. I can’t believe that you are going to settle for few lines in a post. Show us the puzzle in all of its glory (an image of some sort :D ) This is something that many have been trying to do for ages!!!

A mini celebration probably. And you may even start a thread that has only these NSG=1 puzzles for players to solve!!!

This is not something that an average sudoku programmer is able to emulate. So my guess is that you can enjoy a clear field here :idea:

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

Re: Jigsaws and Low ED Counts

Postby Mathimagics » Mon Mar 25, 2019 7:24 pm

Ok, I will start a "Clueless Jigsaw" thread! 8-)

But I'm not sure any players will get very far solving it. Andrew over at SSF described the 1-clue Jigsaw-NC puzzle as "beyond diabolical"! :?

This is probably harder than that …

Sudoku Jigsaw with Forbidden Pairs {15 18 23 39 49 57 59 68}
Clueless-JFP.png
Clueless-JFP.png (2.01 KiB) Viewed 99 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 1272
Joined: 27 May 2015
Location: Canberra

Re: Jigsaws and Low ED Counts

Postby Mathimagics » Mon Mar 25, 2019 8:45 pm

Mathimagics wrote:This is probably harder than that …


Or is it? :?:

The clueless Jigsaw layout (JL) is in fact more constraining than the one used in the 1-clue puzzle. If we drop the forbidden pairs and solve them both as regular Jigsaw's, then the 1-clue JL has 1,055,193,713 x 9! solutions, but the asymmetric clueless JL has just 3,504,861 x 9! solutions.

This correlates with other measures, such as the number of "hidden houses": 2 for the 1-clue JL, but 5 for the clueless JL. (These are like the "hidden windows" of Windoku, they are complete houses implied by, but in addition to, the 9 jigsaw regions).
User avatar
Mathimagics
2017 Supporter
 
Posts: 1272
Joined: 27 May 2015
Location: Canberra


Return to Sudoku variants