Is there a mathematical way to check if a KenKen (Mathdoku / Calcdoku) puzzle has at most one solution

combinatoricspuzzle

Is there a mathematical way to check if a KenKen (Mathdoku / Calcdoku) puzzle has at most one solution without trying every permutation and then checking if two different permutations both solve the puzzle?

If not, is there a way to generate such a puzzle so that it can only have one solution?

An obvious way to check if there is only one solution would be to solve it and check if there are at least two solutions (e.g. with backtracking algorithms), but with large grids this becomes unfeasible.

From what I've noticed it seems that from one solution you can create another one by swapping columns and/or rows (column and row constraints won't be broken) and hope that the cage constraint isn't broken.
This would take n!^4 operations, with n being the size of the grid (column/row length).

Also checking for symmetry in cage disposition could be a possible approach, even though, from various attempts I made, it seems inconclusive.

Best Answer

I don't have any mathematical proofs or references, but I highly doubt there is an efficient algorithm to do this.

First, solving partially filled Latin squares is known to be NP-complete, and given the close relationship between KenKen and Latin Squares, I therefore highly suspect solving KenKen puzzles is NP-complete. In fact, you could treat every clue cell for the Latin square as its own region with that number as the clue for a KenKen puzzle, so if this is the kind of KenKen p[uzzles where you are allowed to have regions without any clue number, then you can just treat all other cells as their own clue-less region as well.

Second, generating a puzzle with a unique solution is probably as hard as solving solving. For example, I know that many Sudoku-generating algorithms simply either add more and more clues to an empty grid, or subtract more and more clues from a full grid, and use a solver to check for uniqueness. Note that this is brute force and there is nothing what I think you mean by 'mathematical' about this.

Now, you could constrain the regions and/or clues to such an extent that sure, a puzzle with a unique solution can be generated very quickly. In the extreme case, we could use the connection with the Latin squares as mentioned earlier to effectively put down a number in each cell except for one or two. But now of course you get highly uninteresting KenKen puzzles.

Indeed, there is a bit of subjectiveness to your question, as I assume your question is really asking about a method to generate interesting KenKen puzzles with a unique solution, and 'interesting' is hard to define mathematically.

Of course, the really 'interesting' Sudoku puzzles are made by hand, and same goes for KenKen puzzles. If only we could translate the ingenuity of those puzzle creators into an algorithm!

Related Solutions

[Math] Minimally inconsistent Sudoku puzzle

123|   |   
   |4  |  
___|___|4__
   |   |   
   |   |   
___|___|___
   |   |   
   |   |   
   |   |

[Math] Upper bound on minimum number of moves to solve the $m\times n$ sliding puzzle

As noted in the comments, the asymptotic bound is precisely $\Theta(n^3)$ (For the general case, with $m\geq n$, it's actually $\Theta(m^2n)$; for clarity's sake I'm just considering $m=n$ but it's easy to adapt most of these arguments to the general case). The '180 flip' position establishes the lower bound, since there are $n^2-(\frac{n}{3})^2 = \frac{8}{9}n^2$ tiles in the outer third of rows and columns (that is, with $x$ or $y$ coordinate either $\lt n/3$ or $\gt 2n/3$) and each of those tiles must move at least $n/3$ places to get to its final positions. Any one move can only change the distance-from-target of one tile by one unit, so that sets the $O(n^3)$ lower bound.

The upper bound comes from the standard 'fill cells one by one' approach. Since each tile is no more than $2n$ cells from its final position and moving it a single square takes $O(1)$ moves (for instance, to move a cell into an empty square above it and leave the empty square above it, move the empty square D,R,U,U,L) we can fill all but one of the squares in a row in $O(n^2)$ time without having to displace any already-set tiles. The final square in a row takes more care, but that one can be filled by shifting the leftmost tile in a row down, shifting the rest of the row right, setting the final tile into either of the two rightmost squares (without disturbing any of the other cells in the row) and then shifting the rest of the row back; this is a complicated process but only adds $O(n)$ moves per row. A similar approach sets the bottom row once the rest of the puzzle is complete: $O(n)$ moves suffice to move any three tiles from the bottom row into a 'canonical position' in the bottom-right corner, perform a standard 3-cycle on them, and then undo the movements to bring them back to their original locations. Since any even permutation of the tiles in the bottom row can be expressed as a product of $O(n)$ 3-cycles, this adds $O(n^2)$ time to the total effort. In the $m\geq n$ case, the above procedure should yield $O(m^2n)$, the same as your estimate.

'All' that's left at this point is the hardest part of the problem: establishing the constant on the $n^3$ term...

Best Answer

Related Solutions

[Math] Minimally inconsistent Sudoku puzzle

[Math] Upper bound on minimum number of moves to solve the $m\times n$ sliding puzzle

Related Question