- 3-Invalid-Jigsaw-Templates.gif (58.28 KiB) Viewed 1226 times
What they have in common is that they are all invalid - ie: there is no Latin Square which satisfies them.
Proving the validity of Jigsaw templates is a tricky problem. I have been using a DLX Solver (discussed here) with some success, but there remain examples such as these that take quite a long time to resolve.
For example, the template on the right takes 84s to prove invalid on my system using a DLX Solver, the one on the left takes 15 minutes (900s), and the one in the middle, which I have nicknamed "The Beast", takes over 4 hours.
Well, I have succeeded in taming the beast, so to speak, I have a methood that proves these templates invalid in less than 1/10 of a second (for the left and right templates), and 74 seconds for the beast.
The method in fact dates back to Euler, who in 1779 looked at the problem of finding pairs of orthogonal Latin Squares. He came up with a method using transversals.
We know (from this post) that solving any Sudoku (normal or Sudoku) is equivalent to finding a Latin Square that is orthogonal to a given Jigsaw template. DLX Sudoku Solvers use a now-standard formulation of the orthogonal LS problem as an exact cover problem.
This method is extremely efficient for standard Sudoku puzzle solving, but for the general case of Jigsaw template testing, it seems that Euler's method is superior.
This approach splits the problem in two - we first enumerate the transversals of the template, ie sets of 9 cells, one from each region, that cover all 9 rows and columns of the grid. We then search for a set of 9 transversals that cover the entire grid. If such a set exists then a Latin Square for this template can be formed by assigning the value 1 to the cells of the first traversal, 2 to the 2nd traversal, etc. Failure to find a covering set indicates that the template is invalid.
Enumerating transversals and finding a covering set are both straight-forward exact cover problems, so we still use the DLX algorithm, but in a different way.
