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
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.
to clarify !