According to Slate, there’s a push afoot to popularize a Sudoku-like game named KenKen. Since it’s already been demonstrated that Sudoku falls easily to a little programming, I thought it would be interesting to (informally) compare and contrast the two games, with an eye to developing a solver for KenKen.
Constraints
Sudoku and KenKen both seem to place exactly three constraints on each cell:
- Cells must be unique in their row
- Cells must be unique in their column
- Cells must be unique in their box (Sudoku) or satisfy some mathematical requirement of their cage (KenKen)
Sudoku is much “smoother”, in that it has only one type of constraint (two, if you consider cells with fixed values to be constraints). KenKen is “lumpy”, in that it features 5 different types of constraints (+, -, /, *, and uniqueness). This means that a KenKen solver will need more robust constraint propogation code that that seen in Norvig’s Sudoku code, which (quite elegantly) is able to handle propogation inside a single function.
Furthermore, Sudoku constraints are the same for every puzzle of a given size; e.g. the upper-left cell of a 9×9 puzzle must always be unique with respect to the same 20 other cells. KenKen constraints, on the other hand, vary from one puzzle to another.
Representation and Layout
Sudoku puzzles can be nicely represented by a simple string of numbers. KenKen is inherently ugly to represent, since the cages can (in principle) wander nearly arbitrarily over a 2D grid. This is probably a more significant difference than the introduction of mathematical constraints.
Posing a KenKen puzzle is also a minor exercises in drawing, since the cages must be laid out. This is in contrast to Sudoku, which requires the puzzle designer only to place numbers in a grid. This complication, once again, strikes me as significant.
Coming Attractions
The preceding differences notwithstanding, I see no reason Norvig’s general propogation-and-search approach wouldn’t work just fine for KenKen. Therefore, over the next few days, I’ll build up a KenKen solver in Python. It seems like it will be a diverting little exercise.
