## Jigsaw Layouts (Generate / Test)

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Jigsaw Layouts (Generate / Test)

.
Every Jigsaw Sudoku puzzle involves a JL, ie a jigsaw layout (or pattern, if you prefer). A simple definition of a JL in puzzle-speak would be:

• fill in the grid with values 1 to 9, so that each value appears 9 time
• every cell must be adjacent to at least one other cell with the same value

So generating a JL is quite an easy task, probably much easier than generating a Sudoku from scratch.

But generating a useful JL, one that can be used in a puzzle, is not so simple. It has to be valid, for a start. By valid we mean that there is at least one Latin Square which matches the JL.

(I say "Latin Square", not "Sudoku", because a standard Jigsaw Sudoku puzzle replaces the "9 values in a box" rule with a "9 values in a region" rule. We can of course retain the box rule and have a 4D puzzle - I call this variant SudokuJS - that has rows + cols + boxes + jigsaw-regions.)

How can we know if an arbitrary JL is valid? That is, well, a genuine jigsaw puzzle, and is also the main topic of this thread.

Just to give a little example of the problem, here are two JL's, both of which are invalid:

Two invalid JLs: Show
SudokuJ-Invalid.png (3.89 KiB) Viewed 1061 times

The left-hand JL must be invalid because it requires the cells marked "A" to have the same value, and consequently the region below, which is entirely contained in cols 8 and 9, has nowhere that A can go.

But what about the other JL? Is there a simple logical argument one can make to demonstrate its invalidity? Can the "Law of Leftovers" tell us that this JL is invalid? I very much doubt that, but would be very happy to be proven wrong, so by all means have a go at it.

And also, is this JL really invalid? You only have my word to go on, after all!

You might like to think about ways to use software to confirm this. Is there any free solver that can do this? JSudoku as far as I can tell is the only one that has inboard general Jigsaw support. One should approach this with caution, however - I am currently testing this JL in JSudoku, by filling in the first region as givens, and then recursively solving. This has been running for over 32 hours (!) so far without any resolution!

I do have a method which is generic (requires no pattern analysis, "advanced solving techniques", etc), and in this case identifies the JL as invalid in less than 100ms. I will describe this method shortly, but I must point out here that some invalid-JL cases can take much longer, up to 5 minutes.

Anyway, if you have solvers that can be used to attack the problem by any other means, we would definitely like to hear about it.
Last edited by Mathimagics on Wed Feb 06, 2019 5:32 am, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Symmetric Jigsaw Layouts

.
For general use, such as with a puzzle generator, it is best to avoid the validity problem altogether and simply use a "stock" catalog of known valid JL's.

I generated such a catalog by restricting JL's to have these properties:

• symmetry: the JL should be the same when reflected both horizontally and vertically
• RCB-free: the JL should have no region that consists of a whole row, col, or a 3x3 box
• Non-partitioning: for any pair of adjacent rows/cols, at least one adjacent pair of cells must be in the same region. Another way of stating this is that every H/V grid line must pass through some region.
For example:
SJL example: Show
SudokuJ-SJL.png (5.34 KiB) Viewed 1059 times

These are attractive to me because they are aesthetically pleasing, easy to generate, and are countable. There are (I think) only 5,292,980 ED JL's that satisfy these parameters (confirmation invited!).

I won't bore you with the particulars, other than to note that there are just 23 ED patterns for the central region, to which cell(5,5) must belong, so I started with these, then created all possible regions for corner cells, so (1,1) + (9,9), then (1,9) + (9,1). That gives 5-regions completed, so with symmetry taken into account we need only enumerate one more level, since the last 2 regions will pick themselves. Solution tree trimming is done by rigorous contiguity checks at each level (do the free cells form contig regions in multiples of 9?).

We still have to "vet" them, ie test validity, but this set probably has a much higher percentage of valid JL's than a random set of JL's.

The 23 "seed patterns" are given below.

SJL seed patterns (txt): Show
Code: Select all
`   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . X . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . X . . . . .    . . X X . . . . .    . . . X X . . . .    . . . X . . . . .   . . . X . . . . .    . . . X . . . . .    . . . X . . . . .    . . X X . . . . .   . . . X X X . . .    . . . X X X . . .    . . . X X X . . .    . . . X X X . . .   . . . . . X . . .    . . . . . X . . .    . . . . . X . . .    . . . . . X X . .   . . . . . X . . .    . . . . . X X . .    . . . . X X . . .    . . . . . X . . .   . . . . . X . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . X . . . . .    . . . X . . . . .    . . X . . . . . .    . . . . . . . . .   . . . X X . . . .    . . . X . X . . .    . . X X . . . . .    . X X X . . . . .   . . . X X X . . .    . . . X X X . . .    . . . X X X . . .    . . . X X X . . .   . . . . X X . . .    . . . X . X . . .    . . . . . X X . .    . . . . . X X X .   . . . . . X . . .    . . . . . X . . .    . . . . . . X . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . X . . . .    . . . X X . . . .    . . X . . . . . .   . . X X . X . . .    . . . X X . . . .    . . . . X . . . .    . . X . . . . . .   . . . X X X . . .    . . . X X X . . .    . . . X X X . . .    . . X X X X X . .   . . . X . X X . .    . . . . X X . . .    . . . . X . . . .    . . . . . . X . .   . . . . . . . . .    . . . . X . . . .    . . . . X X . . .    . . . . . . X . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . X . . . . .    . . . . X . . . .    . . . . . . . . .    . . . . . . . . .   . . . X . . . . .    . . . . X . . . .    . X X . . . . . .    . . X X . . . . .   . . X X X X X . .    . . X X X X X . .    . . X X X X X . .    . . X X X X X . .   . . . . . X . . .    . . . . X . . . .    . . . . . . X X .    . . . . . X X . .   . . . . . X . . .    . . . . X . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . X . X . . .    . . . X . . X . .    . . X . . . X . .    . . . . X . . . .   . . X X X X X . .    . . X X X X X . .    . . X X X X X . .    . X X X X X X X .   . . . X . X . . .    . . X . . X . . .    . . X . . . X . .    . . . . X . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .    . . . . . . . . .   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                        . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                        . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                        . . . X . . . . .    . . X . . . . . .    . X . . . . . . .                        . X X X X X X X .    . X X X X X X X .    . X X X X X X X .                        . . . . . X . . .    . . . . . . X . .    . . . . . . . X .                        . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                        . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                        . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                     `

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Jigsaw Layouts (Generate / Test)

.
Update: JSudoku has completed its deliberations and pronounced the JL in question to be invalid, thus confirming my result.

The verdict was arrived at in just 37 hours!

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaw Layouts (Generate / Test)

There are (I think) only 5,292,980 ED JL's that satisfy these parameters ..

I have now vetted all of these, and have identified 13,661 as invalid. That leaves us with 5,279,319 confirmed solvable symmetric JL's with the properties listed above.

The method adopted was fairly simple. Each JL was first tested with 9 givens (a complete row or col). By strictly limiting the number of guesses allowed by the solver, I can rapidly test all 18 rows and columns, looking for a magic one that produces a result (valid/invalid) within the allowed guess limit. This resulted in a rate of roughly 100,000 JL's per minute for those cases, and it turned out that 99.9% of the JL's were actually resolved in this manner.

With this job running in 3 parallel streams, the great bulk of the 5 million JL's took about 20 minutes to check. The few JL's that fell through this filtering process (around 3000 JL's) were then resolved via "Plan B", a more rigorous process that basically uses 2 adjacent rows/cols to form an 18-clue puzzle. We fix one row/col and then ask the solver to count how many valid settings there are for the additional row/col (effectively a "solve for nominated house completions only" mode). By applying a limit on the number of solutions we can look for those pairs with the least number of settings in a relatively quick time.

Having chosen our notionally optimal row or column pair, we now revert to normal solver mode, and ask the solver to solve the list of 18-clue puzzles. If any one produces a solution, we can exit with the result "valid". Only if we get failures on every setting can we declare the JL to be invalid.

Once again most of the JL's that need this treatment turn out to have solutions, and so these generally take only a few seconds to find. It's the tiny number that resist this process, that have a large number of settings for all 16 adjacent row/col pairs, that are the fly in the ointment. Some will turn out to be valid, some not - in the latter case they can take anywhere from 1 minute to 3 minutes to finally get a result. Just a few hundred of these take as long to process as the rest of the catalog.

Most of the very hard cases turn out to be in the same batch, the central region is the first one in the 23 base patterns listed above, and that just happens to be the one that is closest to being a 3x3 box. Consequently this batch took 90 minutes to complete, while other batches (all of size approx. 200,000 JL's) took as little as 90 seconds.

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaw Layouts (Generate / Test)

Well done on making this exhaustive search. Although Jigsaw templates are not on my radar at the moment, I will still follow this thread with interest. I would have thought that a safe bet would be that the jigsaw region must intersects with at least 3 rows & 3 columns but you've done better by going through checking the templates exhaustively. Symmetry is a good way to do it as you wouldn't want generate a non symmetrical jigsaw pattern anyway

tarek

tarek

Posts: 3759
Joined: 05 January 2006

### Re: Jigsaw Layouts (Generate / Test)

tarek wrote:I would have thought that a safe bet would be that the jigsaw region must intersect with at least 3 rows & 3 columns

Hi tarek!

Regions that only span 2 rows or 2 columns, while these do seem to figure prominently in the list of invalid layouts, their presence alone does not necessarily actually mean that the layout is invalid. It's how it interacts with other regions that matters.

But the converse could well be true, and I will need to look into this - if no region spans only 2R/2C, does that mean the JL is always valid?

[EDIT] Converse conjecture doesn't hold, either. There are invalid JL's with no 2RC regions.

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaw Layouts (Generate / Test)

It may be of some interest to look at the stats for this "2RC" question.

Legend:
• JPnn: identifies the common central-region pattern
• njl: number of JL's
• nv3/ni3: valid/invalid counts for non-2RC cases
• nv2/ni2: valid/invalid counts for 2RC cases (some region has 2RC span)
Code: Select all
`JP01: njl = 207528, nv3 =  83176, ni3 = 1037, nv2 = 122577, nvi =  738JP02: njl = 184040, nv3 =  83446, ni3 =   12, nv2 = 100309, nvi =  273JP03: njl = 206328, nv3 =  75276, ni3 =    0, nv2 = 130403, nvi =  649JP04: njl = 174074, nv3 =  82847, ni3 =   14, nv2 =  90979, nvi =  234JP05: njl = 412091, nv3 = 167454, ni3 =   31, nv2 = 243790, nvi =  816JP06: njl = 214882, nv3 =  82021, ni3 =   44, nv2 = 132232, nvi =  585JP07: njl = 181349, nv3 =  80888, ni3 =    7, nv2 = 100151, nvi =  303JP08: njl = 220551, nv3 =  89899, ni3 =  470, nv2 = 129872, nvi =  310JP10: njl = 213629, nv3 =  84660, ni3 =    5, nv2 = 128496, nvi =  468JP11: njl = 411807, nv3 = 176990, ni3 =   41, nv2 = 233881, nvi =  895JP13: njl = 209467, nv3 =  81120, ni3 =    0, nv2 = 127705, nvi =  642JP14: njl = 174884, nv3 =  70149, ni3 =    1, nv2 = 104347, nvi =  387JP15: njl = 174992, nv3 =  87485, ni3 =    0, nv2 =  87303, nvi =  204JP16: njl = 174990, nv3 =  98546, ni3 =    0, nv2 =  76268, nvi =  176JP17: njl = 235094, nv3 =  87217, ni3 =   61, nv2 = 147353, nvi =  463JP18: njl = 407023, nv3 = 160635, ni3 =    1, nv2 = 245473, nvi =  914JP20: njl = 210922, nv3 =  86976, ni3 =    6, nv2 = 123449, nvi =  491JP22: njl = 173913, nv3 =  67723, ni3 =    0, nv2 = 105679, nvi =  511JP23: njl = 176932, nv3 =  62140, ni3 =    0, nv2 = 114236, nvi =  556JP24: njl = 206938, nv3 = 101542, ni3 =   56, nv2 = 104900, nvi =  440JP25: njl = 216534, nv3 = 100390, ni3 =   46, nv2 = 115642, nvi =  456JP26: njl = 226471, nv3 =  87868, ni3 =   55, nv2 = 138028, nvi =  520JP27: njl = 278541, nv3 = 108548, ni3 =   84, nv2 = 169250, nvi =  659`

You can see that the great majority of invalid JL's are in just 2 center-pattern classes.

Also the converse of tarek's conjecture is "almost true" for the other 21 classes. If all regions span at least 3 rows & 3 cols, then the JL is far more likely to be valid.

Two patterns have just 1 invalid case for non-2RC layouts. I will extract these and have a close look.

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaw Layouts (Generate / Test)

Mathimagics wrote: I have now vetted all of these, and have identified 13,661 as invalid. That leaves us with 5,279,319 confirmed solvable symmetric JL's with the properties listed above.
… most of the JL's that need this special treatment turn out to have solutions, and so these generally take only a few seconds to find. It's the tiny number that resist this process, that have a large number of settings for all 16 adjacent row/col pairs, that are the fly in the ointment. Some will turn out to be valid, some not - in the latter case they can take anywhere from 1 minute to 3 minutes to finally get a result. Just a few hundred of these take as long to process as the rest of the catalog.

Due to the usual finger trouble, a slight mistype in the implementation meant that some JL's were being mis-diagnosed. The effect was negligible on overall results (only 23 JL's were labelled invalid that shouldn't have been), but the effect on timings was more dramatic. Now the most time spent on the worst-case JL is only 5 seconds.

The entire catalog was re-processed. As a single process this took 165 minutes.

The adjusted counts are: invalid JL's = 13,638 + valid = 5,279,342

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaw Layouts (Generate / Test)

Mathimagics wrote:
Mathimagics wrote:The adjusted counts are: invalid JL's = 13,638 + valid = 5,279,342

Is this something you would like to share possibly to incorporate in the Sukaku explainer project? I'm currently thinking about a random layout generator. I haven't thought about symmetry, ... etc

Essentially a JAVA class or method that would spit out a valid 81 character Jigsaw layout nothing more at the moment!

Tarek

tarek

Posts: 3759
Joined: 05 January 2006

### Re: Jigsaw Layouts (Generate / Test)

tarek wrote:Essentially a JAVA class or method that would spit out a valid 81 character Jigsaw layout nothing more at the moment!

Happy to share what I have, but we are a long way off from that! What I have is all written in VB6 ...

Probably of more direct use is my catalog of symmetric Jigsaw layouts, which have the properties listed above, ie valid, no partitions etc.

I have 3.5 million of those, and have a subset of 25,000 that I actually use ...

I'm happy to describe the basic RCJL (random contig jigsaw layout) methodology, it's fairly simple, if you want to try your hand at generating ...

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaw Layouts (Generate / Test)

I would enjoy a challenge. It appears that my ( prioritizing-part of the brain ) is focused on sudoku until the new year. I've done with Sukaku explainer in the past few months what I haven't done with all of my work in sudoku for 15 years which is to share, and that feels more satisfying.

tarek

Posts: 3759
Joined: 05 January 2006

### Random Contiguous Jigsaw Layout Generation

Donor-Recipient Method

This is a perturbation method - given a valid JL (Jigsaw Layout) we tweak it to produce another JL.

• choose any region as the "initial donor region" (IDR), then choose a cell X in the IDR that has a neighbour Y in a different region, the "recipient region" (RR). Assign cell X to region RR. Region IDR now has 8 cells, region RR has 10 cells.
• repeat this process using the previous RR as the donor region, DR. Each iteration will "fix" the donor region, it will now have 9 cells. The new RR will have 10 cells, unless RR = IDR, in which case we have complated a cycle, IDR will now have 9 cells, and we can exit the loop.

Example:
Code: Select all
`AAAAAAAAB   AAAAAAABB   AAAAAAABB   AAAAAAABBACBBBBBBB   ACBBBBBBB   ACCBBBBBB   ACCBBBBBBCCCBDDEEE   CCCBDDEEE   CCCBDDEEE   ACCBDDEEEFCCCDDEEE   FCCCDDEEE   FCCCDDEEE   FCCCDDEEEFCFCDGEGE   FCFCDGEGE   FCFCDGEGE   FCFCDGEGEFFFDDGGGE   FFFDDGGGE   FFFDDGGGE   FFFDDGGGEFFFDDHGGG   FFFDDHGGG   FFFDDHGGG   FFFDDHGGGHHHHHHHGI   HHHHHHHGI   HHHHHHHGI   HHHHHHHGIHIIIIIIII   HIIIIIIII   HIIIIIIII   HIIIIIIII DR = A      DR = B      DR = C RR = B      RR = C      RR = A X  = 1,8    X  = 2,3    X  = 3,1`

Note that this example begins with a symmetric layout, and would produce a symmetric result if the same 3 donor-recipient operations were applied to the corresponding opposite cells: DR = I, RR = H, X = (9, 2) etc.

Contiguity Checking

In the example, with IDR = A, note that various choices of X, eg (1,1), (1,2), would disconnect region A, and this needs to be avoided. We need to perform a region contiguity check, and this can be applied at each step of the cycle, or we can simply perform a global check at the end of the cycle, starting over again if we produced a dud.

Jigsaw Validity Checking

Having produced a contiguous jigsaw layout, it's probably a good idea to check whether that layout actually supports Sudoku solutions! This is by no means 100% guaranteed.

Mathimagics
2017 Supporter

Posts: 1884
Joined: 27 May 2015
Location: Canberra

### Re: Jigsaw Layouts (Generate / Test)

Very nice …
This seed Layout could be any layout
For a certain constraint type (in this case Jigsaw). Explainer gives each region has an ordinal. Each cellRegion in the grid would have that ordinal. Each cell in a region also has an ordinal representing the position within it. With your technique I can see how all of these can be re-assigned.

BTW, you can have the impression of non-contiguous group cells if you allow C1 and C9 to be adjacent similar to R1 and R9, giving you the impression of a toroidal board. Which is then declared to the solver as a toroidal Jigsaw puzzle!

tarek

tarek

Posts: 3759
Joined: 05 January 2006

### Re: Jigsaw Layouts (Generate / Test)

DLX is still too slow in finding a solution.
While SAT is very fast < 100ms to check if there is one solution.
creint

Posts: 339
Joined: 20 January 2018

### Re: Random Contiguous Jigsaw Layout Generation

Mathimagics wrote:....
Having produced a contiguous jigsaw layout, it's probably a good idea to check whether that layout actually supports Sudoku solutions! This is by no means 100% guaranteed.

Well that does surprise me but i guess it figures.

So there are 5,279,342 valid ED continuous JLs
[ and 13,638 invalid] to clarify !
.... and each of these valid layouts may have 0,1 or more ED solutions

from a post way back bumblebeagle - it seems that the minimum clues is 8

I guess in the layouts these puzzles are in there would tend to be few ED grid solutions - and paradoxically these are hardish puzzles
coloin

Posts: 2194
Joined: 05 May 2005
Location: Tenerife

Next