KenKen

Some weeks ago, I discovered the Sudoku-like puzzle KenKen^® (registered trademark of Nextoy LLC). In Japanese, Ken means ‘clever’. I say ‘Sudoku-like’ because it consists of a grid to be filled with digits. Like with Sudoku, every digit can only appear once within its row and once within its column. But, instead of square boxes, KenKen^® contains cages, which can hold between one and seven (the largest cage I have encountered) contiguous cells. There are no initial clues, but for every cage, the puzzle provides a number and an operation with which the number is to be achieved.

Here is an example of an empty KenKen^® grid:

For example, the cage marked 36x and located smack in the middle of the puzzle must be filled with two numbers whose product is 36. As the side of the puzzle has a side length of nine cells, it means that the numbers must be between 1 and 9 (you can make puzzles of any size). Clearly, there are only two possible pairs that can solve the cage: (4 9) and (9 4). Another example: the 4-cell cage marked with 162x in the top row can only contain one of the combinations (1 3 6 9) and (2 3 3 9). It can contain two 3s because they can be placed in such a way that they don’t share either row or column. A third (and last) example: the two cells close to the bottom-left corner marked 4: can contain any of the combinations (1 4), (2 8), (4 1), and (8 2).

If you are interested in trying it out, you will find a new daily puzzle posted at www.kenken.com/playnow.html.

Some strategies are similar to those used to solve Sudoku, but the more complex Sudoku strategies don’t play any role with KenKen^®.

Obviously, as soon as I discovered KenKen^®, I decided at once to write a program to generate my own puzzles. The puzzle you see in this post is one of those I generated. Note that I cannot call it KenKen^® because that name is trademarked. It was not an easy task to generate a KenKen^®-like puzzle and I am quite proud of the result.

A tricky hurdle was to ensure that the puzzles I generated only admitted a single solution. Look for example at the following partial puzzle:

You could swap the 8 and 2 in the two cages and obtain a valid solution. I did fix this problem with a specific check, but I then realised that it was not sufficient to guarantee unicity. Here is an example that shows why checking for pair swaps is not enough:

Clearly, you can solve the puzzle by placing in the three pairs of cells either one of the two permutations [(2 3) (3 8) (8 2)] and [(3 2) (8 3) (2 8)].

Further, you can also imagine much more complex permutations of several cells. The only way to ensure the unicity of the solution was a brute approach rather than an analytical one: try all possible permutations of all cages.

Implemented the check for unicity, I was able to generate CleverClever puzzles. Unfortunately, the fact that the puzzles were correct and admitted a single solution didn’t make them enjoyable. When I tried to solve the puzzle you see at the beginning of this post, I discovered that there were too many combinations that remained after applying all analytical strategies I had practised on the puzzles made available by kenken.com over a period of a few weeks.

That’s when I decided to give it a rest and go back to it in a while, with a fresh mind. I have to understand how the cages interact with each other to reduce the number of possible combinations. I can generate valid CleverClever puzzles, but they are not fun to solve because they require backtracking (i.e., trial and error).Actually,  to be precise, *I* have not fun in solving them because *I* am not able to solve them analytically...