1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ Hey and welcome to MSE! would you like to share with us what a KenKen puzzle is? Also add any personal thoughts? $\endgroup$ – Vinyl_cape_jawa Mar 11 '20 at 14:46
  • $\begingroup$ Yes, sorry. I updated the post. $\endgroup$ – Alessandro Nerla Mar 11 '20 at 14:56
2
$\begingroup$

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!

Improve this answer
$\endgroup$
  • $\begingroup$ I think I found a way to generate KenKen Puzzles so that, for the great majority of cases, there is only one solution. It is mostly to avoid having smaller grid sizes with multiple solutions. For example, for 2x2 grids, any grid with 2 cages of size 2 has 2 solutions, while if there is 1 cage of size 1 and 1 of size 3 there is only one solution. $\endgroup$ – Alessandro Nerla Mar 11 '20 at 17:17
  • $\begingroup$ @AlessandroNerla OK, but this would only be for 2x2 grids ... highly constrained! $\endgroup$ – Bram28 Mar 11 '20 at 17:42
  • 1
    $\begingroup$ @Bram28 Your second paragraph is incorrect from my general understanding of both puzzles. Sudoku aren't just Latin Squares; they also have the constraint on individual 3x3 grids that AFAIK can't readily be mapped into a KenKen constraint. Both puzzles are fairly similar, but there's no containment in either direction. $\endgroup$ – Steven Stadnicki Mar 11 '20 at 18:05
  • 1
    $\begingroup$ @StevenStadnicki Ah yes, you're absolutely right .. I was indeed treating them as Latin squares! Still, they are similar enpugh that I'll eat my shoes if one of them turns out to have a polynomial time general solver and generator and the other one does not. $\endgroup$ – Bram28 Mar 11 '20 at 18:10
  • 1
    $\begingroup$ Oh, for sure — in fact, I think both are known hard from a complexity theory perspective via reductions from Partial Latin Squares. Interestingly, though, that doesn't necessarily imply that the uniqueness question is hard (again, as I understand it; I haven't looked closely at the details in these cases). I strongly presume it is, of course; I'm just not certain and don't have references to hand. $\endgroup$ – Steven Stadnicki Mar 11 '20 at 18:17
0
$\begingroup$

If you solve the puzzle using integer linear programming with binary decision variables $x_{i,j,k}$ that indicate whether cell $(i,j)$ contains value $k$, you can check uniqueness of a given solution $\hat{x}$ by introducing a "no-good" constraint that disallows that solution. Let $S=\{(i,j,k): \hat{x}_{i,j,k} = 1\}$. The constraint is: $$\sum_{(i,j,k)\in S} (1 - x_{i,j,k}) \ge 1$$ The idea is that at least one variable must change value from 1 to 0. The puzzle has a unique solution if and only if the resulting problem is infeasible.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.