## Jigsaws and Low ED Counts

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Jigsaws and Low ED Counts

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
`135724968681379524246853179792418635357962481819537246463185792928641357574296813318692475753146829297581364642735918184269753536814297971358642425973186869427531792418635357964281813529746468375192926841357574296813139752468685137924241683579975386142429731586864257931318692475753148629291573864647925318182469753536814297`

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.

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaws and Low ED Counts

Congratulations. So 0 clues and 1 real solution. What is the JS layout?

Hajime

Posts: 205
Joined: 20 April 2018
Location: Netherlands

### Re: Jigsaws and Low ED Counts

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`

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaws and Low ED Counts

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
`BDDDDDDCCBBDDDCCCCBBBBEEECCBAAEEEEECBFAAAAAEIHFFFFFAAIHHFFFIIIIHHHHGGGIIHHGGGGGGI158469372682714935425937168793582641316258497964825713249371586571693824837146259952641738428396175685173942317528469794852613146285397861739524539417286273964851`

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaws and Low ED Counts

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.

tarek

tarek

Posts: 3745
Joined: 05 January 2006

### Re: Jigsaws and Low ED Counts

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: GGGGGFFFFGAABGGGHFAABBCCCHFABBCCEEHFABCCDEHHFABCDDEHIFABCDEEHIIABDDEIHHIDDDEEIIIIFP: 14 15 16 27 35 37 69`

This has just 2 solutions, with a simple UA4 spoiling the party:
Code: Select all
`183946752791852643579421368267598431436785219318679524624317895852134976945263187183946752791852643579421368267598431634785219318679524426317895852134976945263187                                                      * *`

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Clueless (NSG = 1)

Bingo!

It just needed a tweak to the JL above, and a little searching for an FP set that worked:
Code: Select all
`JL: AAAAABBBBAACCAADEBFFCCDDDEBFCCDDGGEBFCDDHGEEBFCDHHGEIBFCHHGGEIIFFHHGIEEIFHHGGIIIIFP: 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.

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaws and Low ED Counts

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

Tarek

tarek

Posts: 3745
Joined: 05 January 2006

### Re: Jigsaws and Low ED Counts

Ok, I will start a "Clueless Jigsaw" thread!

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 (2.01 KiB) Viewed 286 times

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaws and Low ED Counts

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

Mathimagics
2017 Supporter

Posts: 1583
Joined: 27 May 2015
Location: Canberra

Return to Sudoku variants