Cancan
A solver and generator of KenKen puzzles
CanCan is a program that generates and solves KenKen puzzles.
KenKen is a math puzzle in which the objective is to fill in every cell in a square n x n grid with a number. The numbers in all the rows and columns must be unique. (So a solved KenKen puzzle is a Latin Square.) Additionally contiguous cells are grouped into blocks called cages, and the sum, product, quotient or difference of the numbers in each cage must equal a target value. Here is a typical puzzle with its solution.
KenKen can be approached as a problem in constraint satisfaction. Adopting the nomenclature used in (Crook 2009), a markup is an assignment of sets of numbers from 1 to n to each cell. The set of possible markups defines the search space. This space may be visualized as a graph where a directed edge points from one markup to another with a single value assigned to one of the cells. The subgraph for a given permutation of cells defines a tree. Since there are n2(2n-1) possible markups and n3 possible solutions, an exhaustive search of the space is intractable. However, after we cross each edge in the graph (including an initial null edge that leads to the start state) we can apply all the constraints, which eliminates values from the markups. The algorithm to find a solution is therefore a depth-first search of a markup tree with constraint propagation at each step.
KenKen generation primarily an exercise in tiling the square with cages. An algorithm that does this is as follows.
- Generate a random Latin Square as the solution of the puzzle.
- Make an undirected graph whose vertices are cells and whose edges are randomly assigned between adjacent cells.
- Partition this graph into its connected components, limiting each component to a randomly chosen maximum size. These are the cages.
- To each cage randomly assign an arithmetic operator (+, -, ÷, ×) and calculate the corresponding target value. For 1-cell cages, the target value is just the value in the cell.
You need a distribution over cage sizes from which to sample in step (2). Its exact values are manually adjusted to produce a range of cage sizes that makes for interesting puzzles. Note that as a grid gets filled in, larger cages will not fit inside the remaining space, so the resulting empirical distribution of cage sizes will skew smaller than the one used for sampling. It is also easy to end up with puzzles containing a large number of single-cell cages. These tend to be too easy to solve, so it helps to filter out generated puzzles with a proportion of single-cell cages above some maximum. Finally there is no guarantee that a given set of cage constraints will have a unique solution. In order to guarantee uniqueness each puzzle generated in step (4) must then be solved and ones with more than one solution discarded.
KenKen can be thought of as a generalization of Sudoku puzzles. Peter Norvig has a Sudoku solver which uses the same constraint propagation algorithm. Michael Heyeck has written a KenKen solver in Python called neknek. CanCan can write puzzles in the format recognized by neknek.
Here is a set of over 40,000 KenKen puzzles of sizes ranging from 4x4 to 9x9 with unique solutions.