Jigsaw Layouts (Generate / Test)

For fans of Killer Sudoku, Samurai Sudoku and other variants

Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Wed Feb 06, 2019 12:42 am

.
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
SudokuJ-Invalid.png (3.89 KiB) Viewed 489 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! :roll:

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. 8-)
Last edited by Mathimagics on Wed Feb 06, 2019 5:32 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Symmetric Jigsaw Layouts

Postby Mathimagics » Wed Feb 06, 2019 1:38 am

.
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
SudokuJ-SJL.png (5.34 KiB) Viewed 487 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 .                     
   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                     
   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                     
   . . . . . . . . .    . . . . . . . . .    . . . . . . . . .                     
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Wed Feb 06, 2019 8:57 am

.
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! :o
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Thu Feb 07, 2019 7:44 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby tarek » Thu Feb 07, 2019 5:06 pm

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
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Thu Feb 07, 2019 9:32 pm

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!

Sadly I would have to take your money! :lol:

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Thu Feb 07, 2019 10:38 pm

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 =  738
JP02: njl = 184040, nv3 =  83446, ni3 =   12, nv2 = 100309, nvi =  273
JP03: njl = 206328, nv3 =  75276, ni3 =    0, nv2 = 130403, nvi =  649
JP04: njl = 174074, nv3 =  82847, ni3 =   14, nv2 =  90979, nvi =  234
JP05: njl = 412091, nv3 = 167454, ni3 =   31, nv2 = 243790, nvi =  816
JP06: njl = 214882, nv3 =  82021, ni3 =   44, nv2 = 132232, nvi =  585
JP07: njl = 181349, nv3 =  80888, ni3 =    7, nv2 = 100151, nvi =  303
JP08: njl = 220551, nv3 =  89899, ni3 =  470, nv2 = 129872, nvi =  310
JP10: njl = 213629, nv3 =  84660, ni3 =    5, nv2 = 128496, nvi =  468
JP11: njl = 411807, nv3 = 176990, ni3 =   41, nv2 = 233881, nvi =  895
JP13: njl = 209467, nv3 =  81120, ni3 =    0, nv2 = 127705, nvi =  642
JP14: njl = 174884, nv3 =  70149, ni3 =    1, nv2 = 104347, nvi =  387
JP15: njl = 174992, nv3 =  87485, ni3 =    0, nv2 =  87303, nvi =  204
JP16: njl = 174990, nv3 =  98546, ni3 =    0, nv2 =  76268, nvi =  176
JP17: njl = 235094, nv3 =  87217, ni3 =   61, nv2 = 147353, nvi =  463
JP18: njl = 407023, nv3 = 160635, ni3 =    1, nv2 = 245473, nvi =  914
JP20: njl = 210922, nv3 =  86976, ni3 =    6, nv2 = 123449, nvi =  491
JP22: njl = 173913, nv3 =  67723, ni3 =    0, nv2 = 105679, nvi =  511
JP23: njl = 176932, nv3 =  62140, ni3 =    0, nv2 = 114236, nvi =  556
JP24: njl = 206938, nv3 = 101542, ni3 =   56, nv2 = 104900, nvi =  440
JP25: njl = 216534, nv3 = 100390, ni3 =   46, nv2 = 115642, nvi =  456
JP26: njl = 226471, nv3 =  87868, ni3 =   55, nv2 = 138028, nvi =  520
JP27: 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Fri Feb 08, 2019 11:10 pm

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby tarek » Sun Dec 15, 2019 10:09 am

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
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Sun Dec 15, 2019 12:38 pm

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 ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby tarek » Sun Dec 15, 2019 4:51 pm

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.
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Random Contiguous Jigsaw Layout Generation

Postby Mathimagics » Mon Dec 16, 2019 6:01 am

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   AAAAAAABB
ACBBBBBBB   ACBBBBBBB   ACCBBBBBB   ACCBBBBBB
CCCBDDEEE   CCCBDDEEE   CCCBDDEEE   ACCBDDEEE
FCCCDDEEE   FCCCDDEEE   FCCCDDEEE   FCCCDDEEE
FCFCDGEGE   FCFCDGEGE   FCFCDGEGE   FCFCDGEGE
FFFDDGGGE   FFFDDGGGE   FFFDDGGGE   FFFDDGGGE
FFFDDHGGG   FFFDDHGGG   FFFDDHGGG   FFFDDHGGG
HHHHHHHGI   HHHHHHHGI   HHHHHHHGI   HHHHHHHGI
HIIIIIIII   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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1583
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby tarek » Mon Dec 16, 2019 4:52 pm

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
User avatar
tarek
 
Posts: 3745
Joined: 05 January 2006

Re: Jigsaw Layouts (Generate / Test)

Postby creint » Mon Dec 16, 2019 5:50 pm

DLX is still too slow in finding a solution.
While SAT is very fast < 100ms to check if there is one solution.
creint
 
Posts: 210
Joined: 20 January 2018

Re: Random Contiguous Jigsaw Layout Generation

Postby coloin » Mon Dec 16, 2019 7:57 pm

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: 1918
Joined: 05 May 2005

Next

Return to Sudoku variants