1
$\begingroup$

There are many ways of solving Sudoku puzzles, however two good approaches are the Algorithm X and solving using Linear programming. Is it possible to solve the KenKen puzzle using Algorithm X (turning the problem into an exact cover problem) or using Linear programming and how could that be done if possible?

Edit: Like the Sudoku, the KenKen puzzle has an NxN grid. Each row and column contain the numbers from 1 to N, so that a number can appear only once per row and per column (similar to the standard Sudoku). We define a "cage" to be a group of cells that are connected together and have a target and an operation. The idea is that all the numbers in the cage must be able to produce the target after applying the operation in between the numbers in the cage. There could be more than one instance of a number in a cage. The operations are +, *, -, /. At the beginning the cages are divided from the other cages by thicker lines on the field and the target, together with the operation is shown for each cage. The cages are wmpty, meaning that no of the grid entries are filled. There could exist a cage with only 1 entry - then the cage has no operation and has to be filled with that number. You have to solve this puzzle for a given cages with targets ans operations.

A link to the Wikipedia page of the puzzle, where an example could be seen: https://en.m.wikipedia.org/wiki/KenKen

$\endgroup$
2
  • $\begingroup$ What's the KenKen puzzle? $\endgroup$ – Juho Feb 27 '20 at 5:33
  • $\begingroup$ @Juho I have edited the post to explain the problem and have included a link to the problem where an example could be seen $\endgroup$ – Ivalin Feb 27 '20 at 6:03
1
$\begingroup$

I don't think there's a simple way to express KenKen as an exact cover problem, although it's certainly possible since exact cover is NP-complete.

I think it would probably be easiest to express it as a SAT instance. Expressing Sudoku as a SAT instance is not hard, and the arithmetic constraints can just be expressed as the disjunction of all of the possible values which would satisfy the constraint (which you would then need to convert to CNF).

$\endgroup$
1
  • $\begingroup$ I would guess that creating the exact cover matrix representation will be very difficult because of the arbitrary number of cages, as well as the number of combinations of number satisfying these constraints. For example, a number could appear more than once in the cage. Because of the large number of combinations for the "+" and '*' groups, do you think such a solution will be feasible from modelling and time complexity point of view? $\endgroup$ – Ivalin Feb 27 '20 at 23:55

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.