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 229 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: 1433
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 227 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: 1433
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: 1433
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: 1433
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: 3182
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: 1433
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: 1433
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: 1433
Joined: 27 May 2015
Location: Canberra


Return to Sudoku variants