Jigsaw Layouts with No Solution?

A regular Jigsaw layout is the one that puzzlers are all used to - every region has N cells. I have to use "regular" to distinguish them from those irregular layouts that I've now started to use.

Regular puzzlers like the good folk here at SudokuXtra see lots of regular Jigsaw layouts, but have you ever wondered whether all layouts are valid? In other words are there impossible layouts, in which no Latin Square at all can satisfy the region boundaries given?

The answer is yes, which surprised me (although perhaps it shouldn't have!). Another surprise was that they exist even on very small grid sizes.

The image attached has some examples on grid sizes N = 4, 5 and 6.

Yes, it can be quite time-consuming to generate large jigsaw puzzles with non-trivial (i.e. not mostly rectangular) jigsaw regions. Making very large samurai jigsaw puzzles in particular doesn't work very well if you do it with entirely random regions.

Have you found a quick way to detect this with any given layout, or have you recursively searched for all possible fits and found none? I have never really given this any thought because a modern computer is easily fast enough just to use brute force to find valid layouts, but it's an interesting topic as you say.



Edited 1 time(s). Last edit at 05/11/2011 05:55PM by gareth.

Unfortunately, all that is known is that the decision problem (is a layout solvable?) is difficult, and just as difficult as the search problem (finding a solution). In complexity theory terms, both problems are NP-hard (and the decision problem is also NP-complete).

And in practice, well, testing a layout is effectively the same problem as finding a solution. My GDL (GD layout) test function is simply a call to the generalised "Sudoku" solver function with one region filled in, and an option to indicate that it can stop if and when it finds any one solution.

So I know just what you mean about testing layouts - 8x8 invalid layouts can take up to a minute to detect, and 9x9's up to an hour! I think this can be improved, the Solver is only "semi-smart" wrt this problem. How smart it can get I'm not sure.

The more regular the shapes of the regions, the more likely they seem to be resolvable, as you said. We'd like to be able to avoid invalid layouts, but would also like to be able to use layouts which have very few solutions, since these require fewer clues - indeed there should be some layouts which have just one solution for a single cell "given". But these are likely to be the ones hardest to detect.

Two approaches that I'm pursuing are

• improving the existing solver/tester speed

• generating layouts from solutions

The latter seems to me to the more "elegant" approach. All of my SS variants are created by starting with a solution (some random LS) and then adding/removing clues until I have both uniqueness and an appropriate difficulty level.

So if I intend to use regions it makes more sense to introduce these at the beginning, when the LS is generated. Finding existing region options is much easier than testing hypothetical ones. The idea would be to simply step through some of the options until I find one that I like.

This approach would definitely make sense for Samurai layouts, since the generation of random solutions (intersecting Latin Squares) is quite simple. Does your puzzle generation methodology allow for that approach?



Edited 1 time(s). Last edit at 05/12/2011 10:04PM by Mathimagics.

I should add that the only available results concerning the complexity of the decision problem for grid layouts are related to the regular layout, in which all regions have N cells. That's the Gerechte Design decision problem.

Now that I have a generalised layout system in which regions can be of arbitrary size, I seem to have ventured into the unknown. Theoretically regions smaller or larger than N are both weaker constraints, so in some sense the decision problem for validity of a layout should become easier.

Perhaps knowing what, if anything, can prevent a "VSR" layout from being completed will provide some insight into the regular layout problem.



Edited 2 time(s). Last edit at 05/12/2011 10:01PM by Mathimagics.

Quote
Jim
8x8 invalid layouts can take up to a minute to detect, and 9x9's up to an hour!

This turns out to be wildly inaccurate. I now realise I haven't actually detected an invalid order-9 Jigsaw layout, because all the ones whose testing I had abandoned (in one case after 3 hours) have since turned out to be valid! And with oodles of solutions, too.

The reason is that the larger the grid, the more significant is one's choice of a starting point, You can safely fix one entire row or column, or region. There are even some layouts in which you can fix one region and also one row or column intersecting that region. I haven't yet devised a way for my program to identify these latter cases, however. So we start with a region (or a row, or a column) filled in.

When the layout is valid, which region (row, col) you choose can be either lucky or not - "lucky" means a waiting time of just milliseconds to identify one solution, but "unlucky" can take, well I don't know - it could be hours, perhaps even days! I have not let any such cases proceed long enough to find out.

It's a very curious phenomenom, and it gave me an idea for a method to reduce the pain of testing randomly generated layouts. I try every region, and if I can't find a solution within a very small number of iterations, I put that layout in the file of "suspects".

I've not yet got any bright ideas on how to process the set of suspects, but I imagine some sort of progressive extension of the time allowed until I reach a point where they can be moved to a "probably invalid" tray. I'll probably pick one and let it run the full course just to see how long it takes.to get a definite answer.

It's fascinating stuff!

I nearly forgot to mention how easy it is to construct an invalid Jigsaw layout. All you need is 3 regions like this.

A 
A
A
A      
A  A  C  B  B  B 
C  C  C  B  B  B

Assume the grid size is 6. So the A in column 2 has to match the C value in the corner. If that's 3, say, then you can't put a 3 in region B.

That pattern can be extended to any grid size. Note that region C can be any shape, as long as it includes that corner cell. Indeed the possibilities are endless for similar constructions.